二叉树高频节点问题解析

链式二叉树定义

本文所描述的二叉树均为链式结构，其定义如下：

typedef char BTDataType;
typedef struct BinaryTree {
    BTDataType data;
    struct BinaryTree* left;
    struct BinaryTree* right;
} BTNode;

二叉树的创建及销毁

通过前序遍历的数组构建二叉树，其中'#'表示该节点为 NULL。例如使用数组 "ABD##E#H##CF##G##" 构建。

前序遍历的思想为：先访问根节点 -> 再访问左子树 -> 最后访问右子树。核心构建逻辑为：'先处理当前节点，再递归构建左子树，最后递归构建右树'。

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

对于二叉树的销毁，需要按照后序遍历的思想：先访问左子树 -> 再访问右子树 -> 最后访问根节点。若按照前序或中序遍历，根节点会提前释放，导致左右子树空间无法释放，造成内存泄漏。

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