【初探数据结构】二叉树的链式结构——分治的暴力美学

我想吃余

已于 2025-03-22 18:10:05 修改

阅读量1.4k

点赞数 40

分类专栏：数据结构篇文章标签：数据结构 kotlin android 算法链表 c语言

于 2025-03-22 15:04:44 首次发布

本文链接：https://blog.csdn.net/Surplus886/article/details/146440437

版权

数据结构篇专栏收录该内容

16 篇文章

订阅专栏

💬 欢迎讨论：在阅读过程中有任何疑问，欢迎在评论区留言，我们一起交流学习！
👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏，并分享给更多对数据结构感兴趣的朋友

文章目录

引言

二叉树是数据结构中的重要概念，广泛应用于算法和程序设计中。本文将基于C语言实现二叉树的核心操作，并通过代码解析帮助读者理解其原理。

1. 二叉树节点定义

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

使用左右指针实现树形结构
data字段存储节点值（示例中为char类型）

2.遍历算法

2.1 前序遍历：根->左->右

访问结点
递归左子树，直至为空子树时（递归结束条件），回归
递归右子树，直至为空子树时，回归
前序遍历图解：

void BinaryTreePrevOrder(BTNode* root)
{
    if (root == NULL)
        return;

    printf("%c ", root->data);//根
    BinaryTreePrevOrder(root->left);//左子树
    BinaryTreePrevOrder(root->right);//右子树
}

当我们对递归代码理解模糊时，可以画出代码的递归图，能够帮助我们很好的理清代码逻辑。
如下为前序遍历的代码递归图：

在这里插入图片描述

2.2 中序遍历：左->根->右

递归左子树，直至为空子树时（递归结束条件），回归
访问结点
递归右子树，直至为空子树时，回归

void BinaryTreeInOrder(BTNode* root)
{
    if (root == NULL)
        return;
    
    BinaryTreeInOrder(root->left);//左子树
    printf("%c ", root->data);//根
    BinaryTreeInOrder(root->right);//右子树
}

2.3 后序遍历：左->右->根

递归左子树，直至为空子树时（递归结束条件），回归
递归右子树，直至为空子树时，回归
访问结点

void BinaryTreePostOrder(BTNode* root)
{
    if (root == NULL)
        return;

    BinaryTreePostOrder(root->left);//左子树
    BinaryTreePostOrder(root->right);//右子树
    printf("%c ", root->data);//根
}

2.4 层序遍历：使用队列辅助实现

思路：创建一个队列，如果二叉树不为空，入根节点，之后遵循一个逻辑：队列每出一个结点，就将这个结点的孩子节点都入队列。 如此往复循环，直至队列为空时，遍历结束。
这里所需要用到的队列不再赘述，如有疑问，建议读者去学习我过去的文章~
🚀传送门:【初探数据结构】线性表——栈与队列（代码实现与详解）

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if (root)
        QueuePush(&q, root);
    while (!QueueEmpty(&q)) {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        printf("%c ", front->data);
        if (front->left)
            QueuePush(&q, front->left);
        if (front->right)
            QueuePush(&q, front->right);
    }
    
    QueueDestroy(&q);
}

2.4.1 层序遍历应用实例：判断完全二叉树

核心思想：通过层序遍历检测空节点后是否出现非空节点

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
    //完全二叉树的所有节点都是连续的，判断节点是否连续即可
    Queue q;
    QueueInit(&q);
    if(root)
        QueuePush(&q, root);
    //将二叉树用层序遍历入队列，直到遇到空节点跳出循环
    while (!QueueEmpty(&q)) {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front == NULL) {
            break;
        }
        else {
            QueuePush(&q, front->left);
            QueuePush(&q, front->right);
        }
    }
    //遍历检查空节点后是否存在非空节点
    while (!QueueEmpty(&q)) {
        BTNode* Nfront = QueueFront(&q);
        QueuePop(&q);
        if (Nfront) {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

3. 二叉树创建

通过前序遍历字符串（如"ABD##E#H##CF##G##"）构建二叉树

#表示空节点，示例树结构如下：

    A
   / \
  B   C
 / \ / \
D  E F G
   \
    H

BTNode* BinaryTreeCreate(BTDataType* a, int* pi) {
    if (a[*pi] == '#') {
        (*pi)++;
        return NULL;
    }
    // 递归创建节点
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    if (root == NULL) {
        perror("malloc fail");
        exit(-1);
    }
    root->data = a[(*pi)++];
    root->left = BinaryTreeCreate(a, pi);
    root->right = BinaryTreeCreate(a, pi);

    return root;
}

4.分治算法

4.1 分治算法核心思想

分治（Divide and Conquer）是一种将复杂问题分解为多个子问题独立解决，再合并子问题结果的算法策略。其核心步骤为：

分解（Divide）：将原问题划分为多个结构相似的子问题。
解决（Conquer）：递归求解子问题。若子问题规模足够小，则直接求解。
合并（Combine）：将子问题的解合并为原问题的解。

在二叉树操作中，由于树的递归定义（每个结点可视为子树的根），分治思想天然适用。

4.2分治实现二叉树的实用功能

4.2.1 计算二叉树深度（`BinaryTreeDepth`）

int BinaryTreeDepth(BTNode* root) {
    if (root == NULL) return 0;
    int Ldep = BinaryTreeDepth(root->left);  // 分解左子树
    int Rdep = BinaryTreeDepth(root->right); // 分解右子树
    return max(Ldep, Rdep) + 1;             // 合并结果
}

分解：分别计算左、右子树的深度。
合并：取左右子树深度的最大值，加上当前层深度（+1）。

4.2.2 统计节点数（`BinaryTreeSize`）

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

分解：将问题拆解为左子树节点数和右子树节点数的计算。
合并：将左右子树节点数相加，并加上当前节点（+1）。

4.2.3 查找节点（`BinaryTreeFind`）

BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
    if (root == NULL) return NULL;
    if (root->data == x) return root;// 直接解决最小问题
    BTNode* left = BinaryTreeFind(root->left, x);// 分解左子树
    if (left) return left;
    return BinaryTreeFind(root->right, x);// 分解右子树
}

分解：若当前节点不匹配，则分别在左、右子树中递归查找。
合并：优先返回左子树找到的结果，若未找到再返回右子树结果。

4.3 分治与普通递归的区别

并非所有递归都是分治，但分治必须通过递归或迭代实现分解。关键区别在于：

分治必须有明确的子问题合并步骤。例如，计算深度时取最大值是合并，而单纯的前序遍历仅是递归，没有合并操作。
分治常用于解决可分解的优化问题，如最大值、最小值、统计总数等。

5. 内存管理

BinaryTreeDestory使用后序遍历递归释放内存
确保无内存泄漏

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
    if (*root == NULL)
        return;
    BinaryTreeDestory(&(*root)->left);
    BinaryTreeDestory(&(*root)->right);
    free(*root);
    *root = NULL;
}

💡：这里也可以不用二级指针，但是测试的时候不要忘记将释放的指针置空哦(❁´◡`❁)（避免野指针）

6. 示例验证

运行主函数：

int main() {
    char* a = "ABD##E#H##CF##G##";
    BTNode* root = BinaryTreeCreate(a, &i);
    // 输出验证...
}

预期结果：

前序遍历：A B D E H C F G 
节点总数：8
树深度：4
查找'H'：成功
叶子节点数：3
第3层节点数：4
是否为完全二叉树：false

总结

本文实现了二叉树的创建、遍历、统计等核心操作。读者可通过完整代码进一步实验。二叉树作为基础数据结构，其思想可延伸至AVL树、红黑树等高级结构，值得深入学习。

希望这篇博客能帮助你更好地理解二叉树操作！