二叉树常见节点操作与统计

若按照前序遍历或者中序遍历的思想，根节点会提前释放，导致左子树和右子树所开辟的空间不能被释放，造成内存泄漏的严重后果。

依照后序遍历的思想，我们可以得出销毁二叉树的逻辑：'先递归处理左子树，再递归处理右子树，最后销毁根节点'。

void TreeDestroy(BTNode** root) {
    if (*root == NULL) return;
    // 销毁左树
    TreeDestroy((*root)->left);
    // 销毁右树
    TreeDestroy((*root)->right);
    // 销毁根
    free(*root);
    *root = NULL;
}

三、二叉树的结点统计与高度计算

温馨提示：下文中对如图所示的二叉树进行节点与高度的计算。

3.1 二叉树节点总数的统计

思路一：通过定义计数变量，通过遍历整棵二叉树进行统计节点个数。

思路二：利用分治思想，结合递归函数，将大问题化成若干个子问题。

整棵树的结点总数 = 左子树结点数 + 右子树结点数 + 1（根结点），空树结点数为 0。

思路一看似很合理，但实际上会出现问题

具体问题如下：

①若使用局部变量：递归遍历左 / 右子树时，每层递归的局部计数变量会被重新初始化，无法累计整棵树的节点数。

②若使用全局 / 类成员变量：虽然能累计计数，但多次调用统计函数时，全局变量不会自动重置，会导致后续统计结果错误。

例如：统计了 A 树的节点个数，再统计 B 树的节点个数就会因没重置计数变量，而导致统计结果错误。

下面基于思路二的思想进行代码展示：

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

3.2 叶子节点的计算

思路：①由叶子结点是'左、右子树均为空'的结点，得出判断条件。

②由分治思想，将大问题化成若干个子问题，整棵树的叶子结点数 = 左子树叶子结点数 + 右子树叶子结点数。

// 叶子节点个数
int TreeLeafSize(BTNode* root) {
    // 若根节点为空，直接返回 0
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

3.3 第 k 层节点的数量

思路：①由分治思想，将大问题化成若干个子问题，第 k 层节点数 = 左子树的第 k-1 层节点数 + 右子树的第 k-1 层节点数。

②明确最小子问题：若树为空（根节点 null）或 k < 1 → 第 k 层节点数为 0；若 k = 1 → 只有根节点，数量为 1。

int TreeLevelKSize(BTNode* root, int k) {
    // 第 k 层的节点数 -> 第 k-1 层的节点数 -> 第 k-1 层左子树 + 第 k-1 层右子树的节点数
    if (root == NULL || k < 0) return 0;
    // 第一层的节点数为 1
    if (k == 1) return 1;
    return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

3.4 二叉树的高度测量

思路：由分治思想，将大问题化成若干个子问题，二叉树的高度=max( 左子树 , 右子树 ）+ 1。

写法一：

// 树的高度
int TreeHeight(BTNode* root) {
    if (root == NULL) return 0;
    return max(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}

写法二：

// 树的高度
int TreeHeight(BTNode* root) {
    if (root == NULL) return 0;
    int leftHeight = TreeHeight(root->left);
    int rightHeight = TreeHeight(root->right);
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

错误写法：因为没有记录左右子树的高度，导致需要进行多次重复冗余的递归，使得增加栈溢出的风险。

// 树的高度
int TreeHeight(BTNode* root) {
    if (root == NULL) return 0;
    return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}

3.5 节点的查找

思路：①由分治思想，将大问题化成若干个子问题，将在整棵树查找节点 -> 根查找 -> 左子树查找 -> 右子树查找。

②边界条件：遇到空子树返回 NULL，遇到值等于查找目标返回该节点。

③温馨提示：在查找到目标节点需要进行保存后，逐层返回。

BTNode* TreeFind(BTNode* root, BTDataType x) {
    // 查找到空节点直接返回
    if (root == NULL) return NULL;
    // 查找到目标节点的判定
    if (root->data == x) return root;
    BTNode* retleft = TreeFind(root->left, x);
    // 在左子树找到，保存并直接返回
    if (retleft) return retleft;
    BTNode* retright = TreeFind(root->right, x);
    // 在右子树找到，保存并直接返回
    if (retright) return retright;
    // 左右子树都没找到
    return NULL;
}

3.6 测试函数功能

void TestFun() {
    char a[] = "ABD##E#H##CF##G##";
    int sz = sizeof(a) / sizeof(char);
    int i = 0;
    BTNode* root = BinaryTreeCreate(a, sz, &i);
    // 测试各功能
    printf("节点总数为：%d\n", TreeSize(root)); // 预期 8
    printf("叶子节点数为：%d\n", TreeLeafSize(root)); // 预期 4（D、H、F、G）
    printf("树的高度为：%d\n", TreeHeight(root)); // 预期 4（A→B→E→H）
    printf("第 3 层的节点数：%d\n", TreeLevelKSize(root, 3)); // 预期 4（D、E、F、G）
    // 测试查找功能
    BTNode* findNode = TreeFind(root, 'H');
    if (findNode) {
        printf("找到节点：%c\n", findNode->data);
    } else {
        printf("未找到节点\n");
    }
    // 销毁二叉树
    TreeDestroy(root);
    root = NULL;
}