数据结构 | 深度解析二叉树的基本原理

Ne0inhk

— 10 min read
数据结构 | 深度解析二叉树的基本原理

个人主页-爱因斯晨

文章专栏-数据结构

在这里插入图片描述

二叉树是计算机科学中最基础也最常用的数据结构之一，它不仅是理解更复杂树结构（如 AVL 树、红黑树）的基础，也广泛应用于表达式解析、 Huffman 编码、数据库索引等领域。本文将从二叉树的基本概念出发，深入探讨其存储结构、核心操作及实际应用，并通过 C 语言代码示例帮助读者掌握这一重要数据结构。

二叉树的基本概念

二叉树是一种每个节点最多有两个子节点的树状结构，这两个子节点分别被称为左孩子（left child）和右孩子（right child）。根据节点的分布情况，二叉树可以分为以下几种特殊类型：

  • 满二叉树：除叶子节点外，每个节点都有两个子节点，且所有叶子节点都在同一层
  • 完全二叉树：除最后一层外，其余层都是满的，且最后一层的节点都靠左排列
  • 平衡二叉树：左右两个子树的高度差不超过 1 的二叉搜索树

二叉树具有一个重要性质：在非空二叉树中，第 i 层最多有 2^(i-1) 个节点；深度为 k 的二叉树最多有 2^k-1 个节点。

二叉树的存储结构

在 C 语言中，二叉树通常有两种存储方式：顺序存储和链式存储。

顺序存储

顺序存储适用于完全二叉树，使用数组来存储节点，通过索引计算节点间的关系：

  • 若父节点索引为 i，则左孩子索引为 2i+1，右孩子索引为 2i+2
  • 若孩子节点索引为 i，则父节点索引为 (i-1)/2（整数除法）
// 顺序存储二叉树示例#defineMAX_SIZE100typedefchar BTDataType; BTDataType array[MAX_SIZE];int size;// 实际节点数量

顺序存储的优点是访问速度快，但对于非完全二叉树会浪费存储空间。

链式存储

链式存储是二叉树最常用的存储方式，通过指针建立节点间的联系：

// 二叉树节点结构定义typedefchar BTDataType;typedefstructBinaryTreeNode{ BTDataType data;// 节点数据structBinaryTreeNode* left;// 左孩子指针structBinaryTreeNode* right;// 右孩子指针} BTNode;

链式存储的优点是空间利用率高，适合各种类型的二叉树，也是我们接下来实现的重点。

二叉树的基本操作

1. 创建节点

创建新节点是所有操作的基础，需要为节点分配内存并初始化：

// 创建新节点 BTNode*BuyBTNode(BTDataType x){ BTNode* node =(BTNode*)malloc(sizeof(BTNode));if(node ==NULL){printf("malloc failed\n");exit(-1);} node->data = x; node->left =NULL; node->right =NULL;return node;}

2. 构建二叉树

手动构建一个简单的二叉树用于演示：

// 构建示例二叉树 BTNode*CreateBinaryTree(){ BTNode* nodeA =BuyBTNode('A'); BTNode* nodeB =BuyBTNode('B'); BTNode* nodeC =BuyBTNode('C'); BTNode* nodeD =BuyBTNode('D'); BTNode* nodeE =BuyBTNode('E'); BTNode* nodeF =BuyBTNode('F'); nodeA->left = nodeB; nodeA->right = nodeC; nodeB->left = nodeD; nodeB->right = nodeE; nodeC->left = nodeF;return nodeA;}

构建的二叉树结构如下：

 A / \ B C / \ / D E F

3. 遍历操作

遍历是二叉树最核心的操作，分为深度优先遍历和广度优先遍历两大类。

深度优先遍历

深度优先遍历又分为三种方式，区别在于访问根节点的时机：

// 前序遍历：根 -> 左 -> 右voidPreOrder(BTNode* root){if(root ==NULL){printf("NULL ");return;}printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);}// 中序遍历：左 -> 根 -> 右voidInOrder(BTNode* root){if(root ==NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);}// 后序遍历：左 -> 右 -> 根voidPostOrder(BTNode* root){if(root ==NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);}

对于前面构建的二叉树，三种遍历结果分别为：

  • 前序：A B D NULL NULL E NULL NULL C F NULL NULL NULL
  • 中序：NULL D NULL B NULL E NULL A NULL F NULL C NULL
  • 后序：NULL NULL D NULL NULL E B NULL NULL F NULL NULL C A
广度优先遍历（层序遍历）

层序遍历需要借助队列实现，按层次从左到右访问节点：

// 层序遍历voidLevelOrder(BTNode* root){if(root ==NULL)return;// 使用队列存储节点 Queue q;QueueInit(&q);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);}

上述二叉树的层序遍历结果为：A B C D E F

4. 二叉树的其他常用操作

// 计算二叉树节点个数intBinaryTreeSize(BTNode* root){return root ==NULL?0:1+BinaryTreeSize(root->left)+BinaryTreeSize(root->right);}// 计算叶子节点个数intBinaryTreeLeafSize(BTNode* root){if(root ==NULL)return0;// 叶子节点：左右孩子都为空if(root->left ==NULL&& root->right ==NULL)return1;returnBinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);}// 计算二叉树的高度intBinaryTreeHeight(BTNode* root){if(root ==NULL)return0;int leftHeight =BinaryTreeHeight(root->left);int rightHeight =BinaryTreeHeight(root->right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}// 查找值为x的节点 BTNode*BinaryTreeFind(BTNode* root, BTDataType x){if(root ==NULL)returnNULL;if(root->data == x)return root;// 先在左子树查找 BTNode* leftRet =BinaryTreeFind(root->left, x);if(leftRet !=NULL)return leftRet;// 再在右子树查找 BTNode* rightRet =BinaryTreeFind(root->right, x);if(rightRet !=NULL)return rightRet;returnNULL;}// 销毁二叉树voidBinaryTreeDestroy(BTNode** root){if(*root ==NULL)return;// 后序遍历销毁：先销毁孩子节点，再销毁根节点BinaryTreeDestroy(&(*root)->left);BinaryTreeDestroy(&(*root)->right);free(*root);*root =NULL;}

二叉树的应用场景

二叉树作为基础数据结构，有许多重要变种和应用：

  1. 二叉搜索树（BST）：左子树所有节点值小于根节点，右子树所有节点值大于根节点，支持 O (log n) 的插入、删除和查找操作。
  2. 表达式树：用于解析数学表达式，叶子节点是操作数，内部节点是运算符。
  3. Huffman 树：一种带权路径长度最短的二叉树，用于数据压缩算法。
  4. 线索二叉树：通过将空指针指向遍历序列中的前驱或后继节点，提高遍历效率。
  5. 平衡二叉树：如 AVL 树和红黑树，通过自平衡机制保持 O (log n) 的操作复杂度。

完整示例代码

下面是包含队列实现和二叉树所有操作的完整代码：

#include<stdio.h>#include<stdlib.h>#include<assert.h>// 二叉树节点结构定义typedefchar BTDataType;typedefstructBinaryTreeNode{ BTDataType data;structBinaryTreeNode* left;structBinaryTreeNode* right;} BTNode;// 队列结构定义（用于层序遍历）typedef BTNode* QDataType;typedefstructQueueNode{ QDataType data;structQueueNode* next;} QNode;typedefstructQueue{ QNode* head; QNode* tail;} Queue;// 队列操作函数声明voidQueueInit(Queue* q);voidQueueDestroy(Queue* q);voidQueuePush(Queue* q, QDataType x);voidQueuePop(Queue* q); QDataType QueueFront(Queue* q);intQueueEmpty(Queue* q);// 队列操作实现voidQueueInit(Queue* q){assert(q); q->head = q->tail =NULL;}voidQueueDestroy(Queue* q){assert(q); QNode* cur = q->head;while(cur){ QNode* next = cur->next;free(cur); cur = next;} q->head = q->tail =NULL;}voidQueuePush(Queue* q, QDataType x){assert(q); QNode* newNode =(QNode*)malloc(sizeof(QNode));if(newNode ==NULL){printf("malloc failed\n");exit(-1);} newNode->data = x; newNode->next =NULL;if(q->tail ==NULL){ q->head = q->tail = newNode;}else{ q->tail->next = newNode; q->tail = newNode;}}voidQueuePop(Queue* q){assert(q);assert(!QueueEmpty(q)); QNode* next = q->head->next;free(q->head); q->head = next;// 如果队列变空，tail也置空if(q->head ==NULL){ q->tail =NULL;}} QDataType QueueFront(Queue* q){assert(q);assert(!QueueEmpty(q));return q->head->data;}intQueueEmpty(Queue* q){assert(q);return q->head ==NULL;}// 二叉树操作函数 BTNode*BuyBTNode(BTDataType x){ BTNode* node =(BTNode*)malloc(sizeof(BTNode));if(node ==NULL){printf("malloc failed\n");exit(-1);} node->data = x; node->left =NULL; node->right =NULL;return node;} BTNode*CreateBinaryTree(){ BTNode* nodeA =BuyBTNode('A'); BTNode* nodeB =BuyBTNode('B'); BTNode* nodeC =BuyBTNode('C'); BTNode* nodeD =BuyBTNode('D'); BTNode* nodeE =BuyBTNode('E'); BTNode* nodeF =BuyBTNode('F'); nodeA->left = nodeB; nodeA->right = nodeC; nodeB->left = nodeD; nodeB->right = nodeE; nodeC->left = nodeF;return nodeA;}voidPreOrder(BTNode* root){if(root ==NULL){printf("NULL ");return;}printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);}voidInOrder(BTNode* root){if(root ==NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);}voidPostOrder(BTNode* root){if(root ==NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);}voidLevelOrder(BTNode* root){if(root ==NULL)return; Queue q;QueueInit(&q);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);}intBinaryTreeSize(BTNode* root){return root ==NULL?0:1+BinaryTreeSize(root->left)+BinaryTreeSize(root->right);}intBinaryTreeLeafSize(BTNode* root){if(root ==NULL)return0;if(root->left ==NULL&& root->right ==NULL)return1;returnBinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);}intBinaryTreeHeight(BTNode* root){if(root ==NULL)return0;int leftHeight =BinaryTreeHeight(root->left);int rightHeight =BinaryTreeHeight(root->right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;} BTNode*BinaryTreeFind(BTNode* root, BTDataType x){if(root ==NULL)returnNULL;if(root->data == x)return root; BTNode* leftRet =BinaryTreeFind(root->left, x);if(leftRet !=NULL)return leftRet; BTNode* rightRet =BinaryTreeFind(root->right, x);if(rightRet !=NULL)return rightRet;returnNULL;}voidBinaryTreeDestroy(BTNode** root){if(*root ==NULL)return;BinaryTreeDestroy(&(*root)->left);BinaryTreeDestroy(&(*root)->right);free(*root);*root =NULL;}// 测试函数intmain(){ BTNode* root =CreateBinaryTree();printf("前序遍历: ");PreOrder(root);printf("\n");printf("中序遍历: ");InOrder(root);printf("\n");printf("后序遍历: ");PostOrder(root);printf("\n");printf("层序遍历: ");LevelOrder(root);printf("\n");printf("节点总数: %d\n",BinaryTreeSize(root));printf("叶子节点数: %d\n",BinaryTreeLeafSize(root));printf("树的高度: %d\n",BinaryTreeHeight(root)); BTDataType findVal ='E'; BTNode* found =BinaryTreeFind(root, findVal);if(found)printf("找到节点: %c\n", found->data);elseprintf("未找到节点: %c\n", findVal);// 销毁二叉树BinaryTreeDestroy(&root);assert(root ==NULL);printf("二叉树已销毁\n");return0;}

总结

二叉树作为一种灵活的数据结构，其核心价值在于它的递归特性和高效的遍历方式。本文从基本概念出发，详细介绍了二叉树的存储结构和常用操作，并通过完整的 C 语言代码实现了这些功能。

掌握二叉树不仅有助于理解更复杂的数据结构，也能培养递归思维和问题分解能力。在实际开发中，二叉树及其变种（如二叉搜索树、平衡二叉树）在处理动态数据集合时表现出色，能够提供高效的插入、删除和查询操作。

学习二叉树的关键在于理解其递归性质，大部分二叉树操作都可以通过递归优雅地实现。同时，熟练掌握四种遍历方式（前序、中序、后序、层序）对于解决二叉树相关问题至关重要。

Read more

吴恩达《机器学习2022》C1-W2 ： 逻辑回归

定义 逻辑回归是一种用于分类任务的机器学习算法（虽然名字带 “回归”，但实际是分类模型），核心是用 “概率” 的方式判断样本属于某一类别的可能性。 核心特点： 1. 任务类型：解决二分类问题（比如 “肿瘤是否恶性”“邮件是否垃圾邮件”），也可以扩展到多分类。 2. 输出形式：输出 0~1 之间的概率值（比如输出 0.8 代表 “样本属于正类的概率是 80%”）。 3. 模型原理： * 先通过线性组合（z=w⋅x+b）处理特征； * 再用Sigmoid 函数把线性结果映射到 0~1。 1. 损失函数：用对数似然损失（就是你图里分情况的形式），保证优化时能找到全局最优。 简单说：逻辑回归是 “用线性模型 + Sigmoid 函数，

By Ne0inhk
七大排序算法深度解析：从原理到代码实现

七大排序算法深度解析：从原理到代码实现

1.排序 排序算法是计算机科学中最基础的技能之一，无论你是编程新手还是经验丰富的开发者，理解这些算法都能显著提升代码效率。本文将用最简单的方式，带你快速掌握七大经典排序算法的核心原理与实现。 1.1排序概念及其运用 排序是指将一组数据按照特定规则（如升序或降序）重新排列的过程。排序是计算机科学中最基础且重要的操作之一，广泛用于优化数据检索、提高算法效率以及简化复杂问题的处理。 排序的主要应用场景 1. 数据库查询：加速数据检索（如索引排序）。 2. 搜索算法：二分查找要求数据有序。 3. 数据分析：统计、去重、Top-K问题（如排行榜）。 4. 任务调度：按优先级处理任务。 5. 文件系统：按文件名、日期排序文件。 1.2常见排序算法 本次将系统介绍7种经典排序算法，重点从时间复杂度、空间复杂度、稳定性三个维度展开分析，时间复杂度和空间复杂度的概念在之前博客中有所讲解，现在来说明一下排序算法稳定性的概念。 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，

By Ne0inhk
数据结构：单链表(1)

数据结构：单链表(1)

目录 前言  一.单链表的概念 介绍 二.单链表的结构 介绍 链表的打印 核心逻辑解析 链表的销毁 三、实现单链表 1.单链表的尾插 结点的创建 2.单链表的头插 3.单链表的尾删 4.单链表的头删 代码   总结 前言    最近学校事务较多，我又正巧经历社团换届，所以耽误了几天时间，但好在所有投入都有了温暖的回应，留任成功了（虽然是小社团哈），接下来，我将继续更新博客，与大家分享知识。 本篇文章将讲解单链表的知识，包括：单链表的概念，单链表的结构、实现单链表、链表的分类、单链表算法题知识的相关内容，为5大模块，其中为本章节知识的内容。 一.单链表的概念 介绍   在之前我们学习了逻辑结构和物理结构都是线性的顺序表，但是我们会发现顺序表有以下3个比较明显的缺陷：中间/头部的插入删除，

By Ne0inhk
【动态规划】01背包与完全背包问题详解，LeetCode零钱兑换II秒解，轻松解力扣

【动态规划】01背包与完全背包问题详解，LeetCode零钱兑换II秒解，轻松解力扣

👨‍💻程序员三明治：个人主页 🔥 个人专栏: 《设计模式精解》《重学数据结构》 🤞先做到 再看见！ 目录 * 01背包题目分析 * 01背包解决方法 * 完全背包题目分析 * 完全背包解决方法 * LeetCode 518.零钱兑换II * 思路 * 代码实现 01背包题目分析 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n)，这里的n表示物品数量。 所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！ 在下面的讲解，我举一个例子： 物品为： 重量价值物品0115物品1320物品2430 01背包解决方法 递归五部曲： 1. 确定dp数组以及下标的含义：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，

By Ne0inhk