C语言：二叉树（上）

文章目录1. 树概念及结构1.1 树的核心概念1.3 树的表示2. 二叉树2.1 二叉树的概念2.2 特殊的二叉树2.2.1 满二叉树2.2.2 完全二叉树2.3 二叉树的性质2.4 二叉树的存储结构3. 二叉树的顺序结构及实现3.1 堆3.2 堆的实现3.2.1 heap.c3.2.2 heap.c3.3.3 test.c4. 堆排序1. 树概念及结构树是一种非线性的数据结构区别于数组、链表、栈、队列等线性结构它由 nn≥0个有限节点组成一个具有层次关系的集合像现实中的 “树”有一个根树根向下分出多个分支子树每个分支又可以再分分支最后是叶子核心特征有且仅有一个根节点n0 时除根外每个节点有且仅有一个父节点没有父节点的是根没有子节点的是叶子。如下图1.1 树的核心概念如下根节点树中唯一没有父节点的节点是树的层级起点n0 时必存在。节点的度单个节点拥有的直接子节点的个数子节点为直接下层节点非间接。树的度树中所有节点的度数的最大值决定树为几叉树如度为 2 则为二叉树。叶子节点度为 0的节点也叫终端节点无任何直接子节点是树的层级终点。分支节点度≥1的节点也叫非终端节点包含根节点和所有有子节点的中间节点。父 / 子节点若节点 A 是节点 B 的直接上层节点A 为 B 的父节点B 为 A 的子节点子节点有且仅有一个父节点。兄弟节点同一父节点的多个子节点互为兄弟节点。节点的层次从根节点开始计数根为第 1 层根的子节点为第 2 层依次向下递增。树的高度 / 深度树中所有节点的最大层次数是树的整体层级深度。子树树中任意一个节点及其所有后代节点构成的集合根节点的子树为整棵树叶子节点无子树。森林m≥0 棵互不相交的树的集合将树的根节点删除根的所有子树即构成森林。1.3 树的表示树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。孩子兄弟表示法的核心是给每个树节点只定义两个指针一个指向该节点的第一个孩子左指针一个指向该节点的右兄弟右指针。// 孩子兄弟表示法的节点结构体typedefstructCSNode{// 1. 节点存储的数据如int、char等DataType data;// 2. 左指针指向当前节点的第一个直接子节点structCSNode*firstChild;// 3. 右指针指向当前节点的右侧第一个兄弟节点structCSNode*rightBrother;}CSNode,*CSTree;// CSTree是指向CSNode的指针代表树/子树2. 二叉树2.1 二叉树的概念二叉树是树的特殊类型也是实际开发中最常用的树结构核心特征是每个节点的度≤2即任意节点最多有两个直接子节点且二叉树为有序树子节点有明确的左右次序不能随意交换。2.2 特殊的二叉树2.2.1 满二叉树定义所有分支节点度 2 都有左、右两个孩子且所有叶子节点都在同一层的二叉树空二叉树也可视为特殊的满二叉树。核心特征节点数公式高度为h的满二叉树节点总数n2h−1比如 h3 时n7h4 时n15)层数特征第k层节点数 2k−1每层都满无空缺叶子节点位置全部集中在最后一层且数量2h−1。2.2.2 完全二叉树定义除最后一层外每一层的节点数都达到最大值且最后一层的叶子节点依次靠左排列无空缺的二叉树。核心特征满二叉树是特殊的完全二叉树最后一层也满节点数范围高度为h的完全二叉树2h−1≤n≤2h−1编号规则根节点编号为 1C 语言数组存储的核心1.节点i的左孩子 2i右孩子 2i12.节点i的父节点 i/2整数除法如 i5 的父节点是 23.若2in则节点i无左孩子若2i1n则无右孩子。叶子节点位置仅出现在最后一层或倒数第二层且最后一层的叶子从左到右连续。还有斜二叉树平衡二叉树等这里不过多解释了2.3 二叉树的性质性质 1第 k 层的最大节点数二叉树第 k 层k≥1根为第 1 层的最大节点数为 2k−1。例第 1 层最多 1 个、第 2 层最多 2 个、第 3 层最多 4 个、第 5 层最多 16 个每层节点数呈 2 倍递增。性质 2高度为 h 的二叉树最大总节点数高度为 hh≥1的二叉树总节点数的最大值为 2h−1。该值为满二叉树的节点数每层都达到最大节点数例高度 3 的满二叉树节点数 7高度 4 的满二叉树节点数 15。性质 3叶子节点与度 2 节点的核心关系必考公式任意非空二叉树中叶子节点数n0​ 度为 2 的节点数n2​ 1即 n0​n2​1。补充总节点数 nn0​n1​n2​n1​ 为度 1 的节点数可联立公式互相推导。例某二叉树有 8 个度 2 节点则叶子节点数一定为 9有 5 个叶子节点则度 2 节点数一定为 4。性质 4空 / 单节点二叉树的特殊值空二叉树高度为 0节点数为 0仅根节点的二叉树高度为 1n0​1、n1​0、n2​0符合n0​n2​1。性质 5高度的计算方式有n个节点的完全二叉树高度h⌊log2​n⌋1⌊log2​n⌋ 表示对log2​n向下取整。例n6时log2​6≈2.58向下取整为 2高度 3n7时log2​7≈2.8高度 3n8时log2​83高度 4。2.4 二叉树的存储结构二叉树的存储结构分为顺序存储数组 和链式存储二叉链和三叉链两类核心区别在于 “是否连续存储”适配不同的二叉树类型和操作场景。一、顺序存储结构基于数组定义用一组连续的存储单元数组按层级顺序存储二叉树的节点核心依赖 “完全二叉树的节点编号规则” 映射数组下标。存储规则节点按层序从 1 开始编号根为 1数组通常从下标 1 开始存储下标 0 弃用简化计算编号为i的节点存储在数组下标i的位置若节点不存在非完全二叉树的空缺位置数组对应下标留空 / 填特殊值如 - 1。核心特征优点随机访问效率高O (1)无需额外存储指针空间利用率高缺点仅适合完全二叉树 / 满二叉树非完全二叉树会出现大量空位置浪费空间关键映射关系同完全二叉树编号规则1.下标i的节点父节点下标为⌊i/2⌋2.左孩子下标为2i右孩子下标为2i13.若数组长度则无左孩子数组长度则无右孩子。适用场景完全二叉树 / 满二叉树的存储如堆、优先队列的底层实现对访问效率要求高、节点数量固定的场景。二、链式存储结构最通用分二叉链表 / 三叉链表二叉链表最常用定义每个节点包含 “数据域 两个指针域”分别指向左孩子和右孩子是二叉树的标准存储方式。节点结构数据域存储节点的数值 / 数据左指针lchild指向当前节点的左孩子无左孩子则为 NULL右指针rchild指向当前节点的右孩子无右孩子则为 NULL。核心特征优点适配所有类型二叉树包括斜二叉树、非完全二叉树插入 / 删除操作灵活无空间浪费缺点需额外存储指针每个节点占 2 个指针空间无法直接访问父节点空间复杂度O(n)n 为节点数每个节点仅 2 个指针。适用场景任意类型二叉树的存储如二叉搜索树、平衡二叉树需频繁插入 / 删除节点、节点数量动态变化的场景如动态查找树3. 二叉树的顺序结构及实现3.1 堆堆是基于完全二叉树实现的优先队列也是二叉树顺序存储数组的核心应用本质可概括为满足特定值规则的完全二叉树且仅通过数组存储、仅支持堆顶的高效操作。3.2 堆的实现依旧分为三个部分heap.h , heap.c , test.c。3.2.1 heap.c#pragmaonce#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintHPDataType;typedefstructHeap{HPDataType*a;intsize;intcapacity;}Hp;voidHeapInit(Hp*php);// 堆的销毁voidHeapDestory(Hp*php);// 堆的插入voidHeapPush(Hp*php,HPDataType x);// 堆的删除voidHeapPop(Hp*php);// 取堆顶的数据HPDataTypeHeapTop(Hp*php);// 堆的数据个数intHeapSize(Hp*php);// 堆的判空boolHeapEmpty(Hp*php);voidAdjustUp(HPDataType*a,intchild);voidAdjustDown(HPDataType*a,intn,intparent);voidSwap(HPDataType*a,HPDataType*b);voidHeapSort(int*a,intn);3.2.2 heap.c#define_CRT_SECURE_NO_WARNINGS#includeHeap.hvoidHeapInit(Hp*php){assert(php);php-aNULL;php-capacityphp-size0;}// 堆的销毁voidHeapDestory(Hp*php){assert(php);free(php-a);php-aNULL;php-capacityphp-size0;}voidSwap(HPDataType*a,HPDataType*b){HPDataType tmp*a;*a*b;*btmp;}voidAdjustUp(HPDataType*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;}}}// 堆的插入voidHeapPush(Hp*php,HPDataType x){assert(php);if(php-capacityphp-size){intnphp-capacity0?4:php-capacity*2;HPDataType*tmp(HPDataType*)realloc(php-a,sizeof(int)*n);if(tmpNULL){perror(realloc fail);return;}php-atmp;php-capacityn;}php-a[php-size]x;php-size;AdjustUp(php-a,php-size-1);}voidAdjustDown(HPDataType*a,intn,intparent){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;}}}//// 堆的删除voidHeapPop(Hp*php){assert(php);assert(php-size0);Swap(php-a[0],php-a[php-size-1]);php-size--;AdjustDown(php-a,php-size,0);}//// 取堆顶的数据HPDataTypeHeapTop(Hp*php){assert(php);assert(php-size0);returnphp-a[0];}//// 堆的数据个数intHeapSize(Hp*php){assert(php);returnphp-size;}//// 堆的判空boolHeapEmpty(Hp*php){assert(php);returnphp-size0;}3.3.3 test.c#define_CRT_SECURE_NO_WARNINGS#includeHeap.hvoidtestHeap1(){inta[]{4,2,8,1,5,6,9,7};for(size_ti0;isizeof(a)/sizeof(a[0]);i){AdjustUp(a,i);}intendsizeof(a)/sizeof(a[0])-1;while(end){Swap(a[0],a[end]);AdjustDown(a,end,0);end--;}for(size_ti0;isizeof(a)/sizeof(a[0]);i){printf(%d ,a[i]);}}voidHeapSort(int*a,intn){for(inti(n-2)/2;i0;i--){AdjustDown(a,n,i);}intendn-1;while(end){Swap(a[0],a[end]);AdjustDown(a,end,0);end--;}for(inti0;in;i){printf(%d ,a[i]);}}voidtestHeap2(){inta[]{4,2,8,1,5,6,9,7};HeapSort(a,sizeof(a)/sizeof(a[0]));}intmain(){testHeap2();Hp ph;HeapInit(ph);HeapPush(ph,4);HeapPush(ph,2);HeapPush(ph,8);HeapPush(ph,1);HeapPush(ph,5);HeapPush(ph,6);HeapPush(ph,9);HeapPush(ph,7);HeapPop(ph);for(inti0;iph.size;i){printf(%d ,ph.a[i]);}return0;}4. 堆排序上面代码中有一个堆排序大家可能看不懂这是一个比较厉害的排序我在这分析一下先分析向下调整voidAdjustDown(HPDataType*a,intn,intparent){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;}}}最坏的时间复杂的是O(logn)即logn层。再来分析堆排voidHeapSort(int*a,intn){for(inti(n-2)/2;i0;i--){AdjustDown(a,n,i);}intendn-1;while(end){Swap(a[0],a[end]);AdjustDown(a,end,0);end--;}for(inti0;in;i){printf(%d ,a[i]);}为什么int i (n-2)/2呢最下一层是不需要向下调整的故找到倒二层最后一个节点就行最后一个节点是n-1其父节点就是((n-1)-1)/2,即(n-2)/2。为什么end n -1 ?最后一个节点不用调整了原理找到最小值移至根节点end–,根节点后移(续二叉树链式结构实现较多下一篇博客将仔细阐述,谢谢观看