树节点与结构
使用指针建模节点。
树节点与结构 是 CoddyKit 上的免费 C Academy 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。
什么是二叉树
二叉树是一种层次结构，其中每个节点存储一个值，并且最多连接两个子节点：左子节点和右子节点。
位于最上方的节点是根节点。没有子节点的节点称为叶节点。这种结构非常适合快速搜索、排序和递归处理。
Node 结构体
在 C 语言中，我们使用一个结构体来表示节点，其中存储数据以及两个指向自身类型的指针。
每个指针都指向另一个 Node；如果对应方向没有子节点，则指向 NULL。
struct Node {
int value;
struct Node *left;
struct Node *right;
};为何使用自引用指针
节点不能按值包含另一个完整节点，因为这会需要无限的存储空间。相反，它会保存指向子节点的指针。
指针的大小固定，因此结构体的大小仍然是已知的，同时还可以连接到堆上的其他节点。
struct Node {
int value;
struct Node *left; /* 8 bytes on 64-bit */
struct Node *right; /* 8 bytes on 64-bit */
};为方便使用而定义 typedef
到处输入 struct Node 很繁琐。使用 typedef 后，我们只需写 Node。
在结构体内部仍然需要使用标签，因为此时该类型还没有完全定义。
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;分配 Node
节点位于堆上，使用 malloc 创建。我们设置其值，并将两个子节点指针都初始化为 NULL。
使用这块内存之前，请始终检查 malloc 是否返回了 NULL。
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (n == NULL) return NULL;
n->value = value;
n->left = NULL;
n->right = NULL;
return n;
}手动构建一棵小树
为了理解这些连接，请让我们手动连接三个节点：一个根节点和两个子节点。
这个程序会构建这棵树并打印各个值；在实际情况下，通常还应释放它（稍后介绍）。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;
Node *create_node(int v) {
Node *n = malloc(sizeof(Node));
n->value = v; n->left = NULL; n->right = NULL;
return n;
}
int main(void) {
Node *root = create_node(10);
root->left = create_node(5);
root->right = create_node(15);
printf("%d %d %d\n", root->left->value, root->value, root->right->value);
return 0;
}访问孙节点
您可以通过连续使用箭头运算符在树中导航。root->left->right 会先移动到左子节点，再移动到它的右子节点。
跟随指针之前，请确认它不是 NULL，否则程序会崩溃。
/* root
* \
* right (15)
* \
* right->right (20)
*/
if (root->right != NULL && root->right->right != NULL)
printf("%d\n", root->right->right->value);递归计算节点数量
递归非常适合处理树。要计算节点数量，空子树包含零个节点；否则，就将当前节点和两个子树的节点数量相加。
NULL 检查是终止递归的基本情况。
int count_nodes(Node *root) {
if (root == NULL) return 0;
return 1 + count_nodes(root->left)
+ count_nodes(root->right);
}测量高度
树的高度是从根节点向下到叶节点的最长路径长度，以边数计。
我们取两个子树高度中较大的一个，再加一。空树的高度设为 -1，这样单节点树的高度就是 0。
int height(Node *root) {
if (root == NULL) return -1;
int l = height(root->left);
int r = height(root->right);
return 1 + (l > r ? l : r);
}识别叶节点
叶节点是没有子节点的节点：left 和 right 都是 NULL。
这个小型辅助函数在许多遍历和计数过程中都很有用。
int is_leaf(Node *n) {
return n != NULL && n->left == NULL && n->right == NULL;
}让结构发挥作用
这里会构建一棵小树，并使用递归辅助函数报告它的节点数量和高度。
请注意，这些辅助函数从不假设固定的结构；由于递归遵循实际的指针连接，它们适用于任何树。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *nn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int height(Node *r){ if(!r) return -1; int l=height(r->left),x=height(r->right); return 1+(l>x?l:x); }
int main(void){
Node *root = nn(10);
root->left = nn(5); root->right = nn(15);
root->left->left = nn(2);
printf("nodes=%d height=%d\n", count(root), height(root));
return 0;
}快速检查
请测试您对节点结构的理解。
回顾
二叉树节点存储一个值和两个自引用指针（left、right）；没有对应子节点时，指针设为 NULL。
我们使用 malloc 分配节点，手动连接它们，并以递归方式处理它们。对于节点计数、高度计算和叶节点测试，NULL 检查始终是基本情况。
常见问题解答
「树节点与结构」课时是免费的吗？
是的 — 「树节点与结构」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。
「树节点与结构」这节课中我会学到什么？
使用指针建模节点。 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 C Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「树节点与结构」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 C Academy 课中编写并运行代码吗？
能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。