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

二叉树从入门到精通一篇搞定数据结构中的“树”读完这篇文章你将彻底掌握二叉树的核心概念、性质、实现和应用前言在计算机科学中数据结构就像程序员的“武器库”。而二叉树无疑是这个武器库中最重要、最基础的“兵器”之一。无论是数据库索引、文件系统组织还是算法竞赛中的各类问题二叉树都扮演着不可或缺的角色。今天就让我们一起来彻底搞懂二叉树一、树是什么为什么叫“树”1.1 树的定义树是一种非线性的数据结构它由 nn≥0个有限结点组成一个具有层次关系的集合。之所以叫“树”是因为它长得像一棵倒挂的树——根朝上叶朝下。根结点 / | \ 子结点 子结点 子结点 / \ | ... ... ...1.2 树的关键概念概念解释例子结点的度结点拥有的子树个数结点A有3个子树度3叶结点度为0的结点没有孩子的结点父结点有子结点的结点A是B的父结点子结点父结点的下属结点B是A的子结点兄弟结点相同父结点的结点B和C是兄弟树的度树中最大的结点度最大度为6树的度6树的深度/高度结点的最大层次数根为第1层最深到第4层高度4森林m棵互不相交的树的集合多棵树组成森林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 二叉树的核心性质性质内容性质1第 i 层最多有2^(i-1)个结点性质2深度为 h 的二叉树最多有2^h - 1个结点性质3叶结点数 n0 度为2的结点数 n2 1性质4满二叉树深度 h log₂(n1)⭐性质3的证明是面试重点设总结点数 N n0 n1 n2从边的角度N - 1 n1 2×n2每个结点向上有1条边根除外两式相减可得n0 n2 12.4 完全二叉树的编号规律对于按从上到下、从左到右编号的完全二叉树根结点编号为00 / \ 1 2 / \ / \ 3 4 5 6需求公式双亲结点(i - 1) / 2左孩子2i 1需 n右孩子2i 2需 n三、二叉树的存储结构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){intparentroot;intchildparent*21;// 左孩子while(childn){// 选出左右孩子中较大的大根堆if(child1na[child1]a[child]){child;}if(a[child]a[parent]){Swap(a[child],a[parent]);parentchild;childparent*21;}else{break;}}}向上调整AdjustUp用于插入元素后的调整voidAdjustUp(int*a,intchild){intparent(child-1)/2;while(child0){if(a[child]a[parent]){Swap(a[child],a[parent]);childparent;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-sizehp-capacity){// 扩容intnewCapacityhp-capacity0?4:hp-capacity*2;HPDataType*tmprealloc(hp-a,sizeof(HPDataType)*newCapacity);hp-atmp;hp-capacitynewCapacity;}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 堆排序堆排序分为两步建堆升序建大堆降序建小堆排序每次把堆顶元素换到最后再向下调整voidHeapSort(int*a,intn){// 建堆 O(N)for(inti(n-1-1)/2;i0;i--){AdjustDown(a,n,i);}// 排序 O(N log N)intendn-1;while(end0){Swap(a[0],a[end]);AdjustDown(a,end,0);end--;}}时间复杂度O(N log N)空间复杂度O(1)5.2 Top-K 问题问题从 N 个数据中找出最大或最小的前 K 个N 极大如 100 亿。解法用前 K 个元素建堆找最大建小堆找最小建大堆遍历剩余 N-K 个元素比堆顶大则替换并向下调整最后堆中的 K 个元素就是答案voidPrintTopK(int*a,intn,intk){// 1. 用前k个元素建小堆for(inti(k-2)/2;i0;i--){AdjustDown(a,k,i);}// 2. 遍历剩余元素for(intik;in;i){if(a[i]a[0]){a[0]a[i];AdjustDown(a,k,0);}}// 3. 打印结果for(inti0;ik;i){printf(%d ,a[i]);}}时间复杂度O(N log K)空间复杂度O(K)六、二叉树的遍历6.1 四种遍历方式遍历方式顺序结果图示二叉树前序遍历根 → 左 → 右1 2 3 4 5 6中序遍历左 → 根 → 右3 2 1 5 4 6后序遍历左 → 右 → 根3 2 5 6 4 1层序遍历逐层从左到右1 2 4 3 5 66.2 递归实现简洁优雅// 前序遍历voidPreOrder(BTNode*root){if(rootNULL)return;printf(%d ,root-data);PreOrder(root-left);PreOrder(root-right);}// 中序遍历voidInOrder(BTNode*root){if(rootNULL)return;InOrder(root-left);printf(%d ,root-data);InOrder(root-right);}// 后序遍历voidPostOrder(BTNode*root){if(rootNULL)return;PostOrder(root-left);PostOrder(root-right);printf(%d ,root-data);}6.3 层序遍历使用队列voidLevelOrder(BTNode*root){if(rootNULL)return;Queue q;QueueInit(q);QueuePush(q,root);while(!QueueEmpty(q)){BTNode*frontQueueFront(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){returnrootNULL?0:1BinaryTreeSize(root-left)BinaryTreeSize(root-right);}7.2 求叶子结点个数intBinaryTreeLeafSize(BTNode*root){if(rootNULL)return0;if(root-leftNULLroot-rightNULL)return1;returnBinaryTreeLeafSize(root-left)BinaryTreeLeafSize(root-right);}7.3 求第k层结点个数intBinaryTreeLevelKSize(BTNode*root,intk){if(rootNULL)return0;if(k1)return1;returnBinaryTreeLevelKSize(root-left,k-1)BinaryTreeLevelKSize(root-right,k-1);}7.4 二叉树的高度intBinaryTreeHeight(BTNode*root){if(rootNULL)return0;intleftHeightBinaryTreeHeight(root-left);intrightHeightBinaryTreeHeight(root-right);return(leftHeightrightHeight?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十、总结知识点核心要点树的概念递归定义根朝上叶朝下二叉树性质n0 n2 1第i层最多2^(i-1)个结点完全二叉树适合顺序存储父子结点有公式关系堆大根堆/小根堆向下调整O(log N)堆排序O(N log N)空间O(1)不稳定Top-K建小堆找最大K个O(N log K)遍历前中后序递归层序队列二叉树是学习更复杂数据结构如二叉搜索树、AVL树、红黑树、B树的基石。掌握好二叉树你就拿到了通往高级数据结构的钥匙本文代码均为纯C实现易于理解可直接运行测试。希望这篇文章对你有所帮助如有疑问欢迎在评论区留言讨论