C / C++ / 系统课时
用结构体定义二叉树节点
用结构体定义二叉树节点
二叉树在 C 语言中并没有内置类型,通常用结构体保存节点数据,并用两个指针连接左、右子节点。本节会定义一个可动态分配的节点类型,手动连接出一棵简单二叉树,并正确释放申请的内存。
学习目标
- 用结构体表示二叉树节点的数据、左孩子和右孩子
- 使用
malloc动态创建节点并用指针建立父子关系 - 在树不再使用时递归释放全部节点
节点为什么要保存两个指针
一个二叉树节点最多有两个直接子节点,因此结构体通常包含一个数据字段,以及分别指向左孩子和右孩子的指针。某个方向没有孩子时,对应指针使用 NULL。
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;这里不能把 left 和 right 直接定义成 TreeNode 对象,否则一个节点内部又需要完整包含两个节点,结构体大小将无法确定。使用指针后,节点自身大小固定,树的连接关系则在运行时建立。

动态创建并连接节点
实际程序通常不会提前知道树有多少节点,因此节点经常通过 malloc 动态创建。创建函数负责申请内存、写入数据,并把两个孩子指针初始化为 NULL,避免使用未初始化指针。
下面的完整程序创建根节点 10,再连接值为 5 和 20 的左右孩子。
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode *create_node(int data) {
TreeNode *node = malloc(sizeof(TreeNode));
if (node == NULL) {
fprintf(stderr, "内存分配失败\n");
exit(EXIT_FAILURE);
}
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
void free_tree(TreeNode *root) {
if (root == NULL) {
return;
}
/* 先释放两个子树,再释放当前节点。 */
free_tree(root->left);
free_tree(root->right);
free(root);
}
int main(void) {
TreeNode *root = create_node(10);
root->left = create_node(5);
root->right = create_node(20);
printf("根节点: %d\n", root->data);
printf("左孩子: %d\n", root->left->data);
printf("右孩子: %d\n", root->right->data);
free_tree(root);
return 0;
}预期输出
根节点: 10
左孩子: 5
右孩子: 20代码中的三个 malloc 分别创建三个互相独立的节点,随后通过 root->left 和 root->right 保存地址,树的结构由这些地址关系形成,而不是由节点在内存中的物理相邻位置决定。
指针访问时要注意什么
只有确认指针不是 NULL 时,才能通过 -> 访问节点成员。例如叶子节点没有左孩子时,node->left 为 NULL,继续访问 node->left->data 会产生未定义行为,常见结果是程序崩溃。
free_tree 采用先处理左右子树、再释放当前节点的方式。这样每个节点都只释放一次,而且不会在父节点已经释放后再尝试读取它保存的孩子指针。
从节点定义到一棵树
结构体解决的是“一个节点长什么样”,左右指针解决的是“节点之间怎样连接”。只要持续创建节点并把地址赋给某个节点的 left 或 right,就可以扩展出任意形状的二叉树;后续遍历、查找和删除操作,本质上也都是沿这些指针访问节点。