目录
1 简介
在数据结构中，二叉树（Binary Tree）是一种结构非常灵活且应用广泛的非线性结构，广泛用于排序、检索、表达式树、图像处理等领域。本文将使用 C 语言实现一个简单的二叉搜索树（BST），完成其插入、中序遍历、前序遍历、后序遍历以及树的释放等基本操作，为后续掌握平衡树、红黑树等高级树结构打下基础。
2 二叉树的基本概念
二叉树：每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉搜索树（BST）：左子树中所有节点的值都小于根节点，右子树中所有节点的值都大于根节点。
遍历方式：
中序遍历：左 -> 根 -> 右（常用于排序）
前序遍历：根 -> 左 -> 右
后序遍历：左 -> 右 -> 根
3 代码实现
// node.c
// 二叉树的基本操作
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int val;
struct node *left;
struct node *right;
} Node;
Node *insert(Node *root, int val);
void pre_order(Node *root);
void in_order(Node *root);
void post_order(Node *root);
void free_tree(Node *root);
void delete_tree(Node *root);
int main(int argc, char const *argv[])
{
Node *root = NULL;
root = insert(root, 42);
root = insert(root, 9);
root = insert(root, 72);
root = insert(root, 32);
root = insert(root, 17);
in_order(root);
printf("\n");
free_tree(root);
in_order(root); // 释放后，root指向的内存已经被释放，不能再访问
return 0;
}
// 删除树
void delete_tree(Node *root)
{
if (root == NULL) return;
delete_tree(root->left);
delete_tree(root->right);
free(root);
}
// 释放树
void free_tree(Node *root)
{
delete_tree(root);
}
// 插入节点
Node *insert(Node *root, int val)
{
if (root == NULL)
{
root = malloc(sizeof(Node));
root->val = val;
root->left = NULL;
root->right = NULL;
return root;
}
if (val < root->val)
{
// 小于当前节点值，插入左子树
root->left = insert(root->left, val);
}
if (val > root->val)
{
// 大于当前节点值，插入右子树
root->right = insert(root->right, val);
}
return root;
}
// 中序遍历
void in_order(Node *root)
{
if (root == NULL) return;
in_order(root->left); // 先中序打印左子树
printf("%d, ", root->val); // 打印根
in_order(root->right); // 再中序打印右子树
}
// 先序遍历
void pre_order(Node *root)
{
if (root == NULL) return;
printf("%d, ", root->val);
pre_order(root->left);
pre_order(root->right);
}
// 后序遍历
void post_order(Node *root)
{
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d, ", root->val);
}4 代码解析
4.1 节点结构体
typedef struct node
{
int val;
struct node *left;
struct node *right;
} Node;
定义了二叉树节点结构，包含整数值 val，指向左子节点和右子节点的指针 left 和 right，构成了树的基本元素。
4.2 插入节点
Node *insert(Node *root, int val)
{
if (root == NULL)
{
root = malloc(sizeof(Node));
root->val = val;
root->left = NULL;
root->right = NULL;
return root;
}
if (val < root->val)
{
root->left = insert(root->left, val);
}
if (val > root->val)
{
root->right = insert(root->right, val);
}
return root;
}
该函数用于向二叉搜索树插入新节点。如果当前树为空，创建新节点作为根节点。若插入值小于当前节点，递归插入左子树。若插入值大于当前节点，递归插入右子树。返回更新后的树根指针。
4.3 中序遍历
void in_order(Node *root)
{
if (root == NULL) return;
in_order(root->left);
printf("%d, ", root->val);
in_order(root->right);
}
中序遍历顺序为：左子树 -> 根节点 -> 右子树。
这使得输出的节点值是升序排列，适用于二叉搜索树的排序输出。
4.4 先序遍历
void pre_order(Node *root)
{
if (root == NULL) return;
printf("%d, ", root->val);
pre_order(root->left);
pre_order(root->right);
}
先序遍历顺序为：根节点 -> 左子树 -> 右子树。
常用于复制树结构或先访问根节点的场景。
4.5 后序遍历
void post_order(Node *root)
{
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d, ", root->val);
}
后序遍历顺序为：左子树 -> 右子树 -> 根节点。
适合用于释放树资源或后序处理子树。
4.6 释放二叉树
void delete_tree(Node *root)
{
if (root == NULL) return;
delete_tree(root->left);
delete_tree(root->right);
free(root);
}
void free_tree(Node *root)
{
delete_tree(root);
}
通过递归后序遍历，先释放左右子树，最后释放根节点，实现安全释放整个树所占内存。
此时的错误说明二叉树的空间已经被释放。
5 核心操作分析
6 总结
本文演示了二叉搜索树的基本实现，包括节点插入和三种常用遍历方式，以及如何释放树内存。代码结构简洁，适合入门学习树形结构操作。理解这些基础操作，为后续实现更复杂的数据结构和算法打下坚实基础。