二叉树从入门到精通：一篇搞定数据结构中的“树”

二叉树从入门到精通：一篇搞定数据结构中的“树”

读完这篇文章，你将彻底掌握二叉树的核心概念、性质、实现和应用

前言

在计算机科学中，数据结构就像程序员的“武器库”。而二叉树，无疑是这个武器库中最重要、最基础的“兵器”之一。无论是数据库索引、文件系统组织，还是算法竞赛中的各类问题，二叉树都扮演着不可或缺的角色。

今天，就让我们一起来彻底搞懂二叉树！

一、树是什么？为什么叫“树”？

1.1 树的定义

树是一种非线性的数据结构，它由 n（n≥0）个有限结点组成一个具有层次关系的集合。

之所以叫“树”，是因为它长得像一棵倒挂的树——根朝上，叶朝下。

根结点 / | \ 子结点 子结点 子结点 / \ | ... ... ...

1.2 树的关键概念

1.3 树的表示方法（孩子兄弟表示法）

typedefintDataType;structNode{structNode*firstChild;// 第一个孩子结点structNode*pNextBrother;// 指向下一个兄弟结点DataType data;// 数据域};

这种表示法的精妙之处在于：任何一棵普通的树都可以用这个结构表示出来，而且不会造成空间浪费。

1.4 树的应用

树在现实生活中最常见的应用就是文件系统的目录结构：

C: ├── Program Files │ ├── Python │ └── Java ├── Users │ ├── Admin │ └── Guest └── Windows └── System32

二、二叉树：每个结点最多有两个孩子

2.1 什么是二叉树？

二叉树是每个结点最多有两个子树的树结构。这两个子树分别称为左子树和右子树，且左右顺序不能颠倒（有序树）。

2.2 特殊二叉树

满二叉树

每一层的结点数都达到最大值。如果层数为 K，总结点数为2^K - 1。

1 / \ 2 3 / \ / \ 4 5 6 7 ← 满二叉树（三层）

完全二叉树

对于深度为 K、有 n 个结点的二叉树，每个结点都与深度为 K 的满二叉树中编号 1~n 的结点一一对应。

满二叉树是完全二叉树的特例。

1 / \ 2 3 / \ / 4 5 6 ← 完全二叉树（缺了7号位置）

2.3 二叉树的核心性质

⭐性质3的证明是面试重点！

设总结点数 N = n0 + n1 + n2

从边的角度：N - 1 = n1 + 2×n2（每个结点向上有1条边，根除外）

两式相减可得：n0 = n2 + 1

2.4 完全二叉树的编号规律

对于按从上到下、从左到右编号的完全二叉树（根结点编号为0）：

0 / \ 1 2 / \ / \ 3 4 5 6

三、二叉树的存储结构

3.1 顺序存储（数组）

使用数组存储二叉树，只适合完全二叉树，否则会造成大量空间浪费。

完全二叉树用数组存： 非完全二叉树用数组存： [1, 2, 3, 4, 5, 6, 7] [1, 2, 3, 空, 空, 4, 5, 空, ...] 紧凑无浪费 大量空洞，浪费空间

💡实际应用：堆（Heap）就是用数组存储的完全二叉树。

3.2 链式存储（最常用）

每个结点包含数据域和左右指针：

typedefintBTDataType;typedefstructBinaryTreeNode{BTDataType data;// 数据域structBinaryTreeNode*left;// 左孩子指针structBinaryTreeNode*right;// 右孩子指针}BTNode;

如果需要频繁访问父结点，可以使用三叉链表（多一个 parent 指针）。

四、堆：一种特殊的完全二叉树

4.1 什么是堆？

堆是一种用数组存储的完全二叉树，分为两种：

4.2 堆的核心操作

向下调整（AdjustDown）

前提：左右子树已经是堆。

voidAdjustDown(int*a,intn,introot){intparent=root;intchild=parent*2+1;// 左孩子while(child<n){// 选出左右孩子中较大的（大根堆）if(child+1<n&&a[child+1]>a[child]){child++;}if(a[child]>a[parent]){Swap(&a[child],&a[parent]);parent=child;child=parent*2+1;}else{break;}}}

向上调整（AdjustUp）

用于插入元素后的调整：

voidAdjustUp(int*a,intchild){intparent=(child-1)/2;while(child>0){if(a[child]>a[parent]){Swap(&a[child],&a[parent]);child=parent;parent=(child-1)/2;}else{break;}}}

4.3 建堆的时间复杂度

建堆的时间复杂度是O(N)，这是一个经典结论。

很多人以为建堆是 O(N log N)，实际上从最后一个非叶子结点开始向下调整，总步数约为 2^h - 1 - h ≈ N。

4.4 堆的代码实现

typedefstructHeap{HPDataType*a;intsize;intcapacity;}Heap;// 堆的插入voidHeapPush(Heap*hp,HPDataType x){if(hp->size==hp->capacity){// 扩容intnewCapacity=hp->capacity==0?4:hp->capacity*2;HPDataType*tmp=realloc(hp->a,sizeof(HPDataType)*newCapacity);hp->a=tmp;hp->capacity=newCapacity;}hp->a[hp->size]=x;hp->size++;AdjustUp(hp->a,hp->size-1);}// 堆的删除（删除堆顶）voidHeapPop(Heap*hp){assert(!HeapEmpty(hp));Swap(&hp->a[0],&hp->a[hp->size-1]);hp->size--;AdjustDown(hp->a,hp->size,0);}

五、堆的两大应用

5.1 堆排序

堆排序分为两步：

1. 建堆：升序建大堆，降序建小堆
2. 排序：每次把堆顶元素换到最后，再向下调整

voidHeapSort(int*a,intn){// 建堆 O(N)for(inti=(n-1-1)/2;i>=0;i--){AdjustDown(a,n,i);}// 排序 O(N log N)intend=n-1;while(end>0){Swap(&a[0],&a[end]);AdjustDown(a,end,0);end--;}}

时间复杂度：O(N log N)
空间复杂度：O(1)

5.2 Top-K 问题

问题：从 N 个数据中找出最大（或最小）的前 K 个，N 极大（如 100 亿）。

解法：

1. 用前 K 个元素建堆（找最大建小堆，找最小建大堆）
2. 遍历剩余 N-K 个元素，比堆顶大则替换并向下调整
3. 最后堆中的 K 个元素就是答案

voidPrintTopK(int*a,intn,intk){// 1. 用前k个元素建小堆for(inti=(k-2)/2;i>=0;i--){AdjustDown(a,k,i);}// 2. 遍历剩余元素for(inti=k;i<n;i++){if(a[i]>a[0]){a[0]=a[i];AdjustDown(a,k,0);}}// 3. 打印结果for(inti=0;i<k;i++){printf("%d ",a[i]);}}

时间复杂度：O(N log K)
空间复杂度：O(K)

六、二叉树的遍历

6.1 四种遍历方式

6.2 递归实现（简洁优雅）

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

6.3 层序遍历（使用队列）

voidLevelOrder(BTNode*root){if(root==NULL)return;Queue q;QueueInit(&q);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);}

七、常见二叉树面试题

7.1 求二叉树结点个数

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

7.2 求叶子结点个数

intBinaryTreeLeafSize(BTNode*root){if(root==NULL)return0;if(root->left==NULL&&root->right==NULL)return1;returnBinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);}

7.3 求第k层结点个数

intBinaryTreeLevelKSize(BTNode*root,intk){if(root==NULL)return0;if(k==1)return1;returnBinaryTreeLevelKSize(root->left,k-1)+BinaryTreeLevelKSize(root->right,k-1);}

7.4 二叉树的高度

intBinaryTreeHeight(BTNode*root){if(root==NULL)return0;intleftHeight=BinaryTreeHeight(root->left);intrightHeight=BinaryTreeHeight(root->right);return(leftHeight>rightHeight?leftHeight:rightHeight)+1;}

7.5 根据遍历序列重建二叉树

关键：前序（或后序）确定根，中序确定左右子树。

例题：已知前序遍历EFHIGJK，中序遍历HFIEJKG，求根结点？

• 前序第一个结点E就是根结点 ✅

八、经典OJ题推荐

九、精选练习题及答案解析

题目1

某二叉树共有399个结点，其中有199个度为2的结点，则叶子结点数为？

答案：B. 200

解析：根据性质n0 = n2 + 1 = 199 + 1 = 200

题目2

下列数据结构中，不适合采用顺序存储结构的是？

A. 非完全二叉树 B. 堆 C. 队列 D. 栈

答案：A

解析：非完全二叉树用顺序存储会产生大量空间浪费。

题目3

在具有2n个结点的完全二叉树中，叶子结点个数为？

答案：A. n

解析：完全二叉树中，叶子结点数 = ⌈n/2⌉，这里总结点数 2n 为偶数，叶子结点 = n。

题目4

一棵完全二叉树的结点数为531个，这棵树的高度为？

答案：B. 10

解析：2^9 - 1 = 511 < 531 ≤ 2^10 - 1 = 1023，所以高度为10。

题目5

一个具有767个结点的完全二叉树，叶子结点个数为？

答案：B. 384

解析：叶子结点 = ⌈767/2⌉ = 384

十、总结

二叉树是学习更复杂数据结构（如二叉搜索树、AVL树、红黑树、B树）的基石。掌握好二叉树，你就拿到了通往高级数据结构的钥匙！

📌本文代码均为纯C实现，易于理解，可直接运行测试。

希望这篇文章对你有所帮助！如有疑问，欢迎在评论区留言讨论～