二叉树与前中后序遍历

Kingcq2026/7/11大约 4 分钟

链表让每个节点指向下一个节点。二叉树让每个节点最多指向两个子节点，于是数据可以形成分支层次。

节点定义

#include <stdlib.h>

typedef struct TreeNode {
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *tree_node_create(int value) {
    TreeNode *node = malloc(sizeof(*node));
    if (node == NULL) return NULL;

    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

二叉树并不要求左边比右边小。那是二叉搜索树附加的顺序规则，下一篇再讲。

基本术语

1 是根；
2 和 3 是 1 的子节点；
4、5、3 是叶节点；
节点 2 与其后代组成一棵子树；
深度通常指从根到节点的边数；
高度通常指节点到最深叶子的最长边数。

不同资料对“空树高度”和“单节点高度”可能采用不同约定，写算法前要先说明。

手动连接一棵树

TreeNode *root = tree_node_create(1);
root->left = tree_node_create(2);
root->right = tree_node_create(3);
root->left->left = tree_node_create(4);
root->left->right = tree_node_create(5);

真实程序必须检查每次分配是否成功。教学示例省略检查时，要知道一旦某次返回空指针，后续解引用就会出错。

前序遍历

顺序：根、左、右。

#include <stdio.h>

void preorder(const TreeNode *root) {
    if (root == NULL) return;
    printf("%d ", root->value);
    preorder(root->left);
    preorder(root->right);
}

输出：1 2 4 5 3。

适合复制树、输出结构前缀表示等场景。

中序遍历

顺序：左、根、右。

void inorder(const TreeNode *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->value);
    inorder(root->right);
}

输出：4 2 5 1 3。对二叉搜索树，中序遍历会得到非递减序列。

后序遍历

顺序：左、右、根。

void postorder(const TreeNode *root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->value);
}

输出：4 5 2 3 1。释放树时必须先释放子树，再释放当前节点，因此天然使用后序顺序。

释放整棵树

void tree_destroy(TreeNode *root) {
    if (root == NULL) return;
    tree_destroy(root->left);
    tree_destroy(root->right);
    free(root);
}

调用后，外部根指针仍保存旧地址。可以提供二级指针版本把它设为空，或要求调用者随后手动写 root = NULL。

统计节点与高度

#include <stddef.h>

size_t tree_size(const TreeNode *root) {
    if (root == NULL) return 0;
    return 1 + tree_size(root->left) + tree_size(root->right);
}

int tree_height(const TreeNode *root) {
    if (root == NULL) return -1; // 约定空树高度为 -1

    int left = tree_height(root->left);
    int right = tree_height(root->right);
    return 1 + (left > right ? left : right);
}