线性结构的故事讲完了，这次来种一棵树。树是一种非线性的数据结构，因为它看起来像一棵倒挂的树——根朝上，叶朝下。除根之外，每个结点有且只有一个前驱，却可以有任意多个后继；子树之间不能有交集，不然长着长着就成了环，那是图的故事了。

先认识几片叶子

树在内存里怎么表示呢？最可爱的方案是左孩子右兄弟：每个结点只记两根指针，一根牵第一个孩子，一根牵右边的兄弟。无论父亲有多少个孩子，都这样安安静静排好。

struct TreeNode3
{
    int data;
    struct TreeNode3* firstChild;  // 指向第一个孩子
    struct TreeNode3* nextBrother; // 指向右边的兄弟
};

二叉树的小规矩

二叉树是度最大为 2 的树，每个结点最多左一个右一个孩子。两位特殊嘉宾要认识：

顺便记一条小性质：度为 0 的叶结点个数为 N0、度为 2 的结点个数为 N2 时，永远有 N0 = N2 + 1。

用数组种树

完全二叉树可以直接住进数组：物理上是一排数字，逻辑上是一棵树。下标 i 的结点，左孩子在 2i+1，右孩子在 2i+2，父亲在 (i-1)/2——一行公式就能在家谱里上下穿梭。

数组里的树王，是堆（注意：数据结构的堆和操作系统的堆是两回事）。大堆里每个父结点 ≥ 孩子，根是最大值；小堆反过来，根是最小值。兄弟之间不比大小，只讲长幼。

向上与向下的温柔调整

堆的灵魂是两个调整动作。向上调整服务插入：新来的数住进数组末尾，然后跟父亲比，不合适就交换着往上爬：

void HeapAdjustUp(int* a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)          // 爬到顶就停
    {
        if (a[parent] > a[child])   // 小堆：父亲该更小
        {
            Swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}

向下调整服务删除：把堆顶换到末尾删掉后，新的堆顶往下沉，每次挑两个孩子里小的那个交换（假设法：先默认左边小，再检查右边）。挑孩子时 child + 1 < n 是防越界的小护栏——最后一个父亲可能只有左孩子。

十万个数字里捞最大的K个

TopK 问题（同类题 力扣 215 数组中的第K个最大元素）：海量的数里找最大的前 K 个。把所有数塞进内存建大堆不现实，可爱又省内存的做法是——用前 K 个数建一个小堆，然后剩下的数逐个和堆顶比较，比堆顶大就顶替它再向下调整。小堆的堆顶是「守门员」，守着 K 强门槛。

// 1. 先把十万个随机数写进 data.txt（还记得文件操作吗）
void test()
{
    int n = 100000;
    srand((unsigned int)time(NULL));
    FILE* fin = fopen("data.txt", "w");
    if (fin == NULL)
    {
        perror("fopen");
        return;
    }
    for (int i = 0; i < n; i++)
    {
        int x = (rand() + i) % 1000000;   // +i 减少数据的重复率
        fprintf(fin, "%d\n", x);
    }
    fclose(fin);
}

// 2. 读前 k 个数建小堆，剩下的数跟堆顶比一比
for (int i = 0; i < k; i++)
    fscanf(fin, "%d", &kminheap[i]);   // 读前k个数
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
    HeapAdjustDown(kminheap, k, i);    // 建k个数的小堆

int x = 0;
while (fscanf(fin, "%d", &x) > 0)      // 剩下的数逐个进门
{
    if (x > kminheap[0])               // 比门槛大
    {
        kminheap[0] = x;               // 顶替守门员
        HeapAdjustDown(kminheap, k, 0);
    }
}

链式二叉树与四种遍历

一般的二叉树用链式结构住：每个结点一根数据、左手、右手。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

为了后面举例方便，先手动搭一棵 6 个结点的小树——就是下面遍历示例里那棵：

BTNode* BuyNode(int x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc");
        return NULL;
    }
    node->data = x;
    node->left = node->right = NULL;
    return node;
}

BTNode* CreatBinaryTree()      // 手动创建一棵小树
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);

    node1->left = node2;       //        1
    node1->right = node4;      //     2     4
    node2->left = node3;       //    3     5 6
    node4->left = node5;
    node4->right = node6;
    return node1;
}

前序 / 中序 / 后序是三个形影不离的姐妹，区别只在「访问根」的时机：

void PrevOrder(BTNode* root)   // 前序
{
    if (root == NULL)
    {
        printf("N ");          // 空也要打印出来，树才完整
        return;
    }
    printf("%d ", root->data);
    PrevOrder(root->left);
    PrevOrder(root->right);
}

另外两位姐妹只是把「访问根」的时机换了换——中序把它夹在中间，后序把它放到最后：

void InOrder(BTNode* root)     // 中序：左 → 根 → 右
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}

void PostOrder(BTNode* root)   // 后序：左 → 右 → 根
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}

而层序遍历（广度优先）得请出老朋友队列帮忙：核心思想是「上一层带下一层」——根先入队，出一个结点，就把它的左右孩子都送进队，于是数据一层一层地流淌出来。

void TreeLevelOrder(BTNode* root)   // 层序遍历
{
    Queue q;
    QueueInit(&q);
    if (root)
        QueuePush(&q, root);        // 根先入队
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        printf("%d ", front->data);
        if (front->left)            // 出队时带上左右孩子
            QueuePush(&q, front->left);
        if (front->right)
            QueuePush(&q, front->right);
    }
    QueueDestroy(&q);
}

分治：把大树拆成小树

统计整棵树的性质时，递归的分治思想最好用：整棵树 = 左子树 + 右子树 + 根。

int TreeSize(BTNode* root)          // 结点总数
{
    if (root == NULL)
        return 0;
    return TreeSize(root->left) + TreeSize(root->right) + 1;
}

int TreeLeafSize(BTNode* root)      // 叶子数
{
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

int TreeLevelKSize(BTNode* root, int k)  // 第k层结点数
{
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    return TreeLevelKSize(root->left, k - 1)
         + TreeLevelKSize(root->right, k - 1);
}

求树高时有个小陷阱：(左 > 右) ? 左 + 1 : 右 + 1 会把子树高度算两遍，数据一大就拖慢速度。先把左右结果存进变量，再挑大的加一，就轻快了。

int TreeHeight(BTNode* root)
{
    if (root == NULL)
        return 0;
    int left = TreeHeight(root->left);    // 先存下来
    int right = TreeHeight(root->right);
    return left > right ? left + 1 : right + 1;
}

查找值为 x 的结点也是同一个套路：先在左子树找，找到了就往上交，找不到再去右子树碰碰运气：

BTNode* TreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
        return NULL;
    if (root->data == x)
        return root;

    BTNode* ret1 = TreeFind(root->left, x);
    if (ret1)
        return ret1;
    BTNode* ret2 = TreeFind(root->right, x);
    if (ret2)
        return ret2;
    return NULL;
}

建一棵树，好好道别

给一串带 # 占位的前序序列，可以递归地把树重新种出来；而销毁时要后序告别——先送走左孩子、右孩子，最后才轮到根。要是先销毁根，往左走完就再也找不到右边啦。

BTNode* CreateTree(char* a, int* pi)   // '#': NULL
{
    if (a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->data = a[(*pi)++];
    root->left = CreateTree(a, pi);
    root->right = CreateTree(a, pi);
    return root;
}

void TreeDestory(BTNode* root)
{
    if (root == NULL)
        return;
    TreeDestory(root->left);
    TreeDestory(root->right);
    free(root);          // 形参改不了实参，在main里置空就好
}

五道树的练习题

树的经典题基本都是递归的套路，顺手整理几道，附上直达链接一起刷：

把其中几位的解法拆开看看，几乎全是「分治 + 递归」的复制粘贴：

// 单值二叉树：每个结点的值都相同
bool isUnivalTree(struct TreeNode* root)
{
    if (root == NULL)
        return true;
    if (root->left && root->left->val != root->val)
        return false;
    if (root->right && root->right->val != root->val)
        return false;
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

// 相同的树：结构和值都要一模一样
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if (p == NULL && q == NULL)      // 都是空，相同
        return true;
    if (p == NULL || q == NULL)      // 一空一非空，肯定不同
        return false;
    if (p->val != q->val)
        return false;
    return isSameTree(p->left, q->left)
        && isSameTree(p->right, q->right);
}

// 对称二叉树：比的是「左的左」vs「右的右」
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
{
    if (p == NULL && q == NULL)
        return true;
    if (p == NULL || q == NULL)
        return false;
    if (p->val != q->val)
        return false;
    return _isSymmetric(p->left, q->right)
        && _isSymmetric(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root)
{
    return _isSymmetric(root->left, root->right);
}

前序遍历那题的小心机是输出型参数：递归时把数组和下标的地址都带上：

int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

void prevOrder(struct TreeNode* root, int* a, int* i)
{
    if (root == NULL)
        return;
    a[(*i)++] = root->val;     // i 要传址，不然递归里的 ++ 出了函数就丢了
    prevOrder(root->left, a, i);
    prevOrder(root->right, a, i);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize = TreeSize(root);
    int* a = (int*)malloc(sizeof(int) * (*returnSize));
    int i = 0;
    prevOrder(root, a, &i);
    return a;
}

「另一棵树的子树」则把 isSameTree 当成了零件——对 root 的每个结点问一句「你和 subRoot 一样吗？」：

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (root == NULL)
        return false;
    if (root->val == subRoot->val && isSameTree(root, subRoot))
        return true;
    return isSubtree(root->left, subRoot)
        || isSubtree(root->right, subRoot);
}

愿当下的花如你所见般美丽