devbox
人工智能uu
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

手撕数据结构之二叉树

作者：人工智能uu | 2024-08-09 09:53:06

赞

踩

手撕数据结构之二叉树

 

1.树

树的基本概念与结构

树是⼀种⾮线性的数据结构，它是由 n（n>=0） 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。

• 有⼀个特殊的结点，称为根结点，根结点没有前驱结点。

• 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有 0 个或多个后继。因此，树是递归定义的。

下面的A就是根节点，没有前驱节点的

 非树形结构：

• ⼦树是不相交的（如果存在相交就是图了，图以后得课程会有讲解）

• 除了根节点外，每个节点有且仅有一个父节点

• 一棵N个节点的数有N-1条边

树相关术语

 

2.二叉树

•⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点； 如上图：A是B的⽗结点

•⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点； 如上图：B是A的孩⼦结点•结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，F的度为2，K的度为0

•树的度：⼀棵树中，最⼤的结点的度称为树的度； 如上图：树的度为 6

•叶⼦结点/终端结点：度为 0 的结点称为叶结点； 如上图： B、C、H、I… 等结点为叶结点

•分⽀结点/⾮终端结点：度不为 0 的结点； 如上图： D、E、F、G… 等结点为分⽀结点

•兄弟结点：具有相同⽗结点的结点互称为兄弟结点(亲兄弟)； 如上图： B、C 是兄弟结点

•结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推；

•树的⾼度或深度：树中结点的最⼤层次； 如上图：树的⾼度为 4

•结点的祖先：从根到该结点所经分⽀上的所有结点；如上图： A 是所有结点的祖先

•路径：⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列；⽐如A到Q的路径为： A-E-J-Q；H到Q的路径H-D-A-E-J-Q

•⼦孙：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图：所有结点都是A的⼦孙

•森林：由 m（m>0） 棵互不相交的树的集合称为森林；

树的表示

孩子兄弟表示法：

树结构相对线性表就⽐较复杂了，要存储表⽰起来就⽐较⿇烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表⽰⽅式如：双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表⽰法

  1. struct TreeNode
  2. {
  3. struct Node* child; // 左边开始的第⼀个孩⼦结点
  4. struct Node* brother; // 指向其右边的下⼀个兄弟结点
  5. int data; // 结点中的数据域
  6. }

 

 

我们不用提前知道有多少个节点，通过这种结构体我们就能找到所有的节点

树形结构实际运用场景

⽂件系统是计算机存储和管理⽂件的⼀种⽅式，它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中，树结构被⼴泛应⽤，它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联。

 

2.二叉树

二叉树是树形结构的一种

在树形结构中，我们最常⽤的就是⼆叉树，⼀棵⼆叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空

从上图可以看出⼆叉树具备以下特点：

  1. ⼆叉树不存在度⼤于 2 的结点

  2. ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树

注意：对于任意的⼆叉树都是由以下⼏种情况复合⽽成的

满二叉树

⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为 K ，且结点总数是 2k - 1 ，则它就是满⼆叉树。

完全二叉树

完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K 的，有 n 个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。

假设二叉树层次为K

除了第K层外，每层节点的个数达到了最大节点数，第K层节点个数不一定达到最大节点数

对于下面的图，因为完全二叉树节点的顺序是从左到右的，

那么下面的就不是一个完全二叉树

完全二叉树就是从左到右节点依次增加

满二叉树是完全二叉树的一种，但是完全二叉树不一定是满二叉树

当完全二叉树的节点最大时，那么这个完全二叉树就是满二叉树了

满二叉树一定是完全二叉树

但是完全二叉树不一定是满二叉树

二叉树的性质

根据满⼆叉树的特点可知：

1）若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有 2^(i-1) 个结点

2）若规定根结点的层数为 1 ，则深度为 h 的⼆叉树的最⼤结点数是 2^h - 1

3）若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度 ( log以2为底， n+1 为对数)

对于这个性质三来说的话，2^h-1=n 那么我们就能得到性质三

 

二叉树存储结构

⼆叉树⼀般可以使⽤两种结构存储，⼀种顺序结构，⼀种链式结构。

顺序结构

顺序结构存储就是使⽤数组来存储，⼀般使⽤数组只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费，完全⼆叉树更适合使⽤顺序结构存储。

现实中我们通常把堆（⼀种⼆叉树）使⽤顺序结构的数组来存储，需要注意的是这⾥的堆和操作系统虚拟进程地址空间中的堆是两回事，⼀个是数据结构，⼀个是操作系统中管理内存的⼀块区域分段

链式结构

⼆叉树的链式存储结构是指，⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址 。链式结构⼜分为⼆叉链和三叉链，当前我们学习中⼀般都是⼆叉链。后⾯课程学到⾼阶数据结构如红⿊树等会⽤到三叉链。

3.实现顺序结构二叉树

⼀般堆使⽤顺序结构的数组来存储数据，堆是⼀种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备其他的特性

堆的概念与结构

堆分为小堆和大堆 

小堆我们也称之为小根堆

堆具有以下性质：

• 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；

• 堆总是⼀棵完全⼆叉树。

父节点比孩子节点大就是大根堆

子节点比父节点大就是小根堆

小根堆的堆顶是最小值

大根堆的堆顶是最大值

将堆中的数据存储到数组中，数组不一定是有序的，因为数的排序是从左到右的

对于下面的二叉树

对于15，就是这个数组下标为1的数据，根据性质一我们得到(1-1)/2=0

那么这个节点的双亲节点的下标是0，就是上面的10

对于56，就是这个数组下标为2的数据，根据性质一我们得到(2-1)/2=0

那么这个节点的父节点是下标为0的10

对于25，就是这个数下标为3的数据，根据性质一我们得到(3-1)/2=1

那么这个节点的父节点是下标为1的15

所以我们通过子节点下标就能求出父节点

对于父节点：

左节点：2i+1

右节点: 2i+2

如果右节点的2i+2超过了n，那么就越界了

堆的向上调整算法

我们向堆中插入一个数据16，但是插入之后就不是小堆了

所以我们要进行调整了

 

我们通过(i-1)/2能够找到刚刚插入的16的父节点56

找到之后我们进行两个数据的比较，谁小谁就进行向上调整

那么我们就将16和56交换位置

然后16就从i=6的位置换到i=2的位置，

我们用16找到父节点10

进行两个数据的比较，因为10<16，那么我们就不用做出调整了，最终的结果就是下图

那么这个就是堆的向上调整算法

 如果插入的是6的话，那么最后的结果就是

 

向下调整算法

出堆：删除数据

出的是堆顶的数据，就是下标为0的数据，但是不好删除

但是假如我们删除的是最后一个数据的话就很好解决

直接size--

将70和10的位置进行换一下，然后size--得到了：

那么现在我们只需要将这个堆变成小堆就行了

现在的70是父节点，我们通过2i+1得到左边的子节点，比较左右的两个子节点，挑选出小的，

然后将小的子节点和父节点进行交换，那么最后我们就得到了：

对于25和30来说的话，现在的70是父节点，因为我们的小堆需要父节点小于子节点

那么我们需要挑选出小的子节点和父节点进行交换

那么最后我们就得到了小堆

出堆的过程：先将下标为0的数据和最后一个数据进行交换，然后我们进行size--删除这个要删除的数据

然后我们进行一系列的操作将这个堆变成小堆

那么我们这里用到了向下调整算法

堆排序

排升序--大堆

排降序--小堆

  1. //冒泡排序
  2. //时间复杂度为O(N^2)
  3. void BubbleSort(int* arr, int n)//数组以及数组中的有效数据个数
  4. {
  5.     for (int i = 0; i < n; i++)
  6.     {
  7.         int exchange = 0;
  8.         for (int j = 0; j < n - i - 1; j++)
  9.         {
  10.             //升序
  11.             if (arr[j] > arr[j + 1])//大的在后面，那么我们就进行交换
  12.             {
  13.                 exchange = 1;
  14.                 Swap(&arr[j], &arr[j + 1]);
  15.             }
  16.  
  17.         }
  18.         if (exchange == 0)
  19.         {
  20.             //那么就说明我们经历了一趟内循环，我们的exchange并没有改变，就说明这个数组可能之前就是有序的
  21.             break;
  22.         }
  23.     }
  24. }
  25. /*
  26. 向上调整算法的时间复杂度和层次有关的
  27. 2^k-1=n     n是总节点个数
  28. 那么k=log(n+1)
  29.  
  30. 那么向上调整算法的最差的情况是log(N)
  31. 因为我们向上调整算法在这里的外面还有层循环，那么时间复杂度是Nlog(N)
  32.  
  33.  
  34. 向上调整算法的时间复杂度也是log(N)
  35.  
  36.  
  37. 那么这里的堆排序的时间复杂度是O(n*log n)
  38. */
  39. //堆排序
  40. //期望空间复杂度是O(1) ，不额外的开辟空间
  41. //时间复杂度是O()
  42. void HeapSort(int* arr, int n)
  43. {
  44.     //根据数组来建堆,那么我们就需要便利数组
  45.     //建小堆---降序
  46.     for (int i = 0; i < n; i++)
  47.     {
  48.         AdjustUp(arr, i);//我们给的参数是i,就是开始 调整数字的 下标，我们是从数组第一个元素进行调整的，i=0开始的
  49.     }
  50.     //循环将堆顶数据跟最后位置的数据（会变化，每次减小一个数据）进行交换
  51.     int end = n - 1;//n是数组的有效个数，那么最后一个数据的下标是n-1
  52.     while (end>0)//end会一直--，但是end必须大于0
  53.     {
  54.         Swap(&arr[0], &arr[end]);//将第一个数据和最后一个数据进行交换
  55.         //那么我们就要对现在的剩下的堆进行调整
  56.         //我们采用向下调整的方法
  57.         AdhustDown(arr, 0, end);//我们从根进行调整，那么第二个参数就是0
  58.             //n-1=end,就是我们只需要对剩下的n-1个数据进行向下调整，那么第三个参数就是我们调整的有效数据n-1个
  59.         end--;
  60.     }
  61. }
  62. /*
  63. 我们先用向上调整法将给的数组进行建小堆的操作
  64. 然后建完小堆之后我们利用循环将堆顶的数据和最后一个数据进行交换
  65. 循环停止的条件是end>0
  66.  
  67. 在循环中，我们先利用交换函数将堆顶数据和堆尾数据进行交换
  68. 然后利用我们的向下排序的方法进行正确的小堆排序
  69. 然后进行end--的操作
  70.  
  71. 每次我们通过上面的操作就能将堆顶的最小的数据放到后面，然后剩下的就是较大的数字
  72. 最后我们就实现了降序的操作
  73.  
  74.  
  75.  
  76. */

向上调整法

  1. //堆的向上调整算法
  2.  
  3. //下面的代码是建小堆的
  4. //如果我们要建大堆的话，我们需要将循环里面的条件语句的条件进行改变
  5. //if (arr[child] > arr[parent])
  6. //将大的数据往上放
  7. void AdjustUp(HPDataType* arr, int child)//调整的是一个数组，第二个参数是要调整的数据的下标，将孩子往父亲的位置进行调整
  8. {
  9.     int parent = (child - 1) / 2;//根据孩子求父亲的下标
  10.  
  11.     //不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
  12.     while (child >  0)//当child<0我们就停止向上调整了，因为上面就没有父节点了
  13.     {
  14.         if (arr[child] > arr[parent])//如果孩子比父亲小的话，那么就进行换位置
  15.         {
  16.             //使用交换函数进行数据的交换
  17.             Swap(&arr[parent], &arr[child]);
  18.             child = parent;//进行完上面的交换操作之后，我们之前的child已经变成了parent了
  19.             //那么我们接着进行判断，判断现在的位置和父节点的大小，
  20.             //我们利用现有的child进行父节点的寻找
  21.  
  22.             //现在的child就是之前我们的parent的位置,是下标，child到了parent下标的位置
  23.             //我们利用新的child找新的父节点
  24.  
  25.             //child走到parent的位置，parent走到(child - 1) / 2这个位置
  26.             parent = (child - 1) / 2;
  27.         }
  28.         else//child位置的值比parent位置的值大
  29.         {
  30.             break;
  31.             //我们不不用调整了,直接跳出
  32.         }
  33.     }
  34.  
  35. }
  36. /*
  37. 进行交换函数之后，我们原先的child变成了parent了，就是位置变了
  38. 然后我们这个位置的数据相较于上面的数据还是子节点
  39. 我们要利用这个子节点去寻找上面的父节点
  40. child = parent;
  41. parent = (child - 1) / 2;
  42. 这两句代码
  43. 假如我们插入的数据是6
  44. 那么我们进行完交换函数之后这个6就是新的parent
  45. 但是对于现在6的父节点来说,6还是子节点，只不过子节点有了新的位置
  46. 我们一开始的parent是下标，那么现在的child就是之前我们的parent的位置
  47. */

向下调整法

  1. //向下调整法
  2. //如果我们建大堆的话，我们需要将循环内条件语句的条件进行改变
  3. //如果右孩子比左孩子要大，我们就进行child++操作
  4. //if (child + 1 < n && arr[child] < arr[child + 1])
  5. //除了要改变这个，我们还要if (arr[child] > arr[parent])
  6. //将大的孩子放上面去
  7.  
  8.  
  9. void AdhustDown(HPDataType*arr, int parent, int n)
  10. //第一个数据是我们要调整的数组，第二个参数是父节点，就是我们开始进行调整的位置的下标对应的元素，第三个是数组中有效的元素个数
  11. {
  12.     //我们已知Parent，那么我们能够通过2i+1或者2i+2找到这个父节点的左右子节点
  13.     int child = parent * 2 + 1;//左孩子
  14.     while (child<n)//我们不能让child因为++操作导致越界
  15.     {
  16.         //找左右孩子中最小的那个，我们与父节点进行交换操作
  17.         if (child+1<n && arr[child] < arr[child + 1])
  18.         {
  19.     //假设我们的子节点只有一个左节点的话，那么我们就可以通过child+1<n      
  20.     //这个条件避免child++，避免了越界访问，我们直接让左节点和父节点进行交换
  21.             //child+1必须小于n我们才能往下进行调整操作，避免越界访问
  22.             //假设左边的是56，右边的是15
  23.             child++;//我们进行child++操作，然后child就跑到了15的位置，然后我们将15和父节点进行交换
  24.         }
  25.         if (arr[child] > arr[parent])//如果子节点小于父节点的话我们就进行交换
  26.         {
  27.             Swap(&arr[child], &arr[parent]);
  28.             //交换完成之后我们让parent走到child的位置
  29.             parent =child ;
  30.             //child走到当前位置的左孩子的位置
  31.             child = parent * 2 + 1;
  32.         }
  33.         else//如果Parent比child小的话，那么我们就没必要向下进行调整了
  34.         {
  35.             break;//我们直接跳出
  36.         }
  37.     }
  38. }

我们不仅能用向上调整算法建堆，还能用向下调整算法建堆，那么我们该怎么做呢

我们先从i这个位置开始，就是最后一个节点的父节点开始进行向下调整

下面的堆是我们最开始的数组的样子，就是保持无序的状态

进行完操作之后我们让i--,那么i就跑到20的位置了

然后我们让20向下调整，因为子节点都比20小，那么我们就不进行操作了

因为20比17大，那么我们将20往上放，17往下放

然后因为19比17大，那么将17往下放

那么经过这么一系列的操作，我们就得到了一个大堆

那么究竟是向上建堆好还是向下建堆好呢？

关于计算向下和向下两种调整算法建堆时间复杂度

向下调整算法建堆的时间复杂度

那么最后我们得到的

向下调整算法建堆时间复杂度是O(N)

向上调整算法建堆的时间复杂度

总结

向上调整：

节点数量多的层*调整次数多

节点数量少的层*调整的次数少

向下调整：

节点数量多的层*调整次数少

节点数量少的层*调整次数多

建议是使用向下调整算法进行建堆

建堆的时间复杂度是O(N)

下面的调整得物时间复杂度是O(N*logN)

那么堆排序的时间复杂度是O(N*logN)

TOP-K问题

TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。 ⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了(可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决，基本思路如下：

找最大的前k个数据：

取到的数据和堆顶比较，比较堆顶数据，谁大谁就跟堆顶交换（堆向下进行调整）

那么小堆中的k个数据就是N个数据中的最大的前k个数据

我们先拿k个数据进行建堆，那么在建堆操作之后我们要将剩下的N-K个数据拿过来进行向下调整的操作

那么这种排序的时间复杂度就是O(N)

  1. void CreateNDate()
  2. {
  3.     // 造数据
  4.     int n = 100000;
  5.     srand(time(0));
  6.     const char* file = "data.txt";
  7.     FILE* fin = fopen(file, "w");
  8.     if (fin == NULL)
  9.     {
  10.         perror("fopen error");
  11.         return;
  12.     } 
  13.     for (int i = 0; i < n; ++i)
  14.     {
  15.         int x = (rand() + i) % 1000000;
  16.         fprintf(fin, "%d\n", x);
  17.     } 
  18.     fclose(fin);
  19. }
  20.  
  21. void TOPK()
  22. {
  23.     int k = 0;
  24.     printf("请输入k：");
  25.     scanf_s("%d", &k);
  26.  
  27.     //从文件中读取前k个数据，建堆
  28.     const char* file = "data.txt";
  29.  
  30.     FILE* fout = fopen(file, "r");
  31.     if (fout == NULL)//打开失败
  32.     {
  33.         perror("fopen fail!");
  34.         exit(1);
  35.     }
  36.     //创建一个大小为k的数组,建小堆，找前k个最大的数据
  37.     int* minHeap = (int*)malloc(k*sizeof(int));
  38.     //往堆内放数据
  39.     if (minHeap == NULL)
  40.     {
  41.         perror("malloc fail!");
  42.         exit(2);
  43.     }
  44.     //循环读取文件内的数据
  45.     //从文件中读取前K个数据，
  46.     for (int i = 0; i < k; i++)
  47.     {
  48.         //从fout进行读取，读取的数据类型是%d,将读取到的数据往数组内进行存储
  49.         fscanf_s(fout, "%d", &minHeap[i]);
  50.     }
  51.  
  52.     //向下调整算法，建小堆
  53.     //调整建堆//我们从最后一个数的父节点进行调整，最后一个数的下标是k-1
  54.     for (int i = (k - 1 - 1) / 2; i>= 0; i--)
  55.     {
  56.         AdhustDown(minHeap, i, k);
  57.         //我们从最后一个节点的父节点进行向上调整操作
  58.         //一开始我们的i就被定义成了这个父节点的下标的大小
  59.     }
  60.  
  61.     //那么我们建好堆之后我们就接着读取文件中剩下的N-K个数据
  62.     //我们进行循环读取
  63.     int x = 0;//我们创建一个x变量，将每次读取的数据存在x中与堆顶的数据进行循环比较
  64.     while (fscanf(fout,"%d",&x)!=EOF)//直到读到文件末尾
  65.     {
  66.         //读取到的数据与堆顶的数据进行比较
  67.         //如果比对顶值大，交换入堆
  68.         if (x > minHeap[0])
  69.         {
  70.             minHeap[0] = x;//直接将x放到堆顶
  71.  
  72.             //经过上面的操作之后，那么这个堆就不是一个小堆了
  73.             //我们利用向下调整算法重新将这个堆变成小堆
  74.             AdhustDown(minHeap, 0, k);
  75.  
  76.         }
  77.     }
  78.  
  79.     //走到这里我们已经读完了,那么这个堆剩下的数据就是这个文件前K个最大的数据了
  80.     for (int  i = 0; i < k; i++)
  81.     {
  82.         printf("%d ", minHeap[i]);
  83.     }
  84.     fclose(fout);
  85. }

找最小的前k个数据

建大堆

取到的数据和堆顶比较，比较堆顶数据，谁小谁就跟堆顶交换（堆向下进行调整）

  1. void CreateNDate()
  2. {
  3.     // 造数据
  4.     int n = 100000;
  5.     srand(time(0));
  6.     const char* file = "data.txt";
  7.     FILE* fin = fopen(file, "w");
  8.     if (fin == NULL)
  9.     {
  10.         perror("fopen error");
  11.         return;
  12.     } 
  13.     for (int i = 0; i < n; ++i)
  14.     {
  15.         int x = (rand() + i) % 1000000;
  16.         fprintf(fin, "%d\n", x);
  17.     } 
  18.     fclose(fin);
  19. }
  20.  
  21. void TOPK()
  22. {
  23.     int k = 0;
  24.     printf("请输入k：");
  25.     scanf_s("%d", &k);
  26.  
  27.     //从文件中读取前k个数据，建堆
  28.     const char* file = "data.txt";
  29.  
  30.     FILE* fout = fopen(file, "r");
  31.     if (fout == NULL)//打开失败
  32.     {
  33.         perror("fopen fail!");
  34.         exit(1);
  35.     }
  36.     //创建一个大小为k的数组,建小堆，找前k个最大的数据
  37.     int* minHeap = (int*)malloc(k*sizeof(int));
  38.     //往堆内放数据
  39.     if (minHeap == NULL)
  40.     {
  41.         perror("malloc fail!");
  42.         exit(2);
  43.     }
  44.     //循环读取文件内的数据
  45.     //从文件中读取前K个数据，
  46.     for (int i = 0; i < k; i++)
  47.     {
  48.         //从fout进行读取，读取的数据类型是%d,将读取到的数据往数组内进行存储
  49.         fscanf_s(fout, "%d", &minHeap[i]);
  50.     }
  51.  
  52.     //向下调整算法，建小堆
  53.     //调整建堆//我们从最后一个数的父节点进行调整，最后一个数的下标是k-1
  54.     for (int i = (k - 1 - 1) / 2; i>= 0; i--)
  55.     {
  56.         AdhustDown(minHeap, i, k);
  57.         //我们从最后一个节点的父节点进行向上调整操作
  58.         //一开始我们的i就被定义成了这个父节点的下标的大小
  59.     }
  60.  
  61.     //那么我们建好堆之后我们就接着读取文件中剩下的N-K个数据
  62.     //我们进行循环读取
  63.     int x = 0;//我们创建一个x变量，将每次读取的数据存在x中与堆顶的数据进行循环比较
  64.     while (fscanf(fout,"%d",&x)!=EOF)//直到读到文件末尾
  65.     {
  66.         //读取到的数据与堆顶的数据进行比较
  67.         //如果比对顶值大，交换入堆
  68.         if (x < minHeap[0])
  69.         {
  70.             minHeap[0] = x;//直接将x放到堆顶
  71.  
  72.             //经过上面的操作之后，那么这个堆就不是一个小堆了
  73.             //我们利用向下调整算法重新将这个堆变成小堆
  74.             AdhustDown(minHeap, 0, k);
  75.  
  76.         }
  77.     }
  78.  
  79.     //走到这里我们已经读完了,那么这个堆剩下的数据就是这个文件前K个最大的数据了
  80.     for (int  i = 0; i < k; i++)
  81.     {
  82.         printf("%d ", minHeap[i]);
  83.     }
  84.     fclose(fout);
  85. }

两个代码的最大的区别就是如果我们要找前k个最大的数据

那么我们就让这个数和堆顶的数进行比较，如果这个数大于堆顶的数的话，我们就将堆顶数据赋值为这个数

如果我们找前k个最大的数据的话，那么就是相反

谁小就去堆顶

改变这个条件就行了

顺序结构的二叉树的具体实现

Heap.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. #include <stdbool.h>
  6. #include <time.h>
  7.  
  8.  
  9. //定义堆的结构---底层结构是数组
  10. typedef int HPDataType;
  11. typedef struct Heap
  12. {
  13.     int* arr;
  14.     int size;//有效的数据个数
  15.     int capacity;//空间大小
  16. }HP;
  17.  
  18.  
  19. //堆的初始化
  20. void HPInit(HP*php);
  21.  
  22. //堆的销毁
  23. void HPDestroy(HP* php);
  24.  
  25. //插入数据
  26. void HPPush(HP* php, HPDataType x);
  27.  
  28. //删除数据
  29. void HPPop(HP* php);
  30.  
  31.  
  32. //取堆顶数据
  33. HPDataType HPTop(HP* php);//将堆顶数据拿出来，但是我们不出堆
  34.  
  35. //判断堆是否为空
  36. bool HPEmpty(HP* php);
  37.  
  38. //交换函数
  39. void Swap(int* x, int* y);//一定要传地址才能进行交换了
  40.  
  41. //堆的向上调整算法
  42. void AdjustUp(HPDataType* arr, int child);//调整的是一个数组，第二个参数是要调整的数据的下标，将孩子往父亲的位置进行调整
  43.  
  44. //向下调整法
  45. void AdhustDown(HPDataType* arr, int parent, int n);

Heap.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "Heap.h"
  3.  
  4. //堆的初始化
  5. void HPInit(HP* php)
  6. {
  7.     assert(php);
  8.     php->arr = NULL;
  9.     php->size = php->capacity = 0;
  10. }
  11.  
  12. //堆的销毁
  13. void HPDestroy(HP* php)
  14. {
  15.     assert(php);
  16.     if (php->arr)//不为空的话我们就进行销毁操作
  17.     {
  18.         free(php->arr);
  19.     }
  20.     php->arr = NULL;
  21.     php->size = php->capacity = 0;
  22. }
  23.  
  24. //交换函数
  25. void Swap(int* x, int* y)//一定要传地址才能进行交换了
  26. {
  27.     int tmp = *x;
  28.     *x = *y;
  29.     *y = tmp;
  30. }
  31.  
  32. //堆的向上调整算法
  33.  
  34. //下面的代码是建小堆的
  35. //如果我们要建大堆的话，我们需要将循环里面的条件语句的条件进行改变
  36. //if (arr[child] > arr[parent])
  37. //将大的数据往上放
  38. void AdjustUp(HPDataType* arr, int child)//调整的是一个数组，第二个参数是要调整的数据的下标，将孩子往父亲的位置进行调整
  39. {
  40.     int parent = (child - 1) / 2;//根据孩子求父亲的下标
  41.  
  42.     //不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
  43.     while (child >  0)//当child<0我们就停止向上调整了，因为上面就没有父节点了
  44.     {
  45.         if (arr[child] < arr[parent])//如果孩子比父亲小的话，那么就进行换位置
  46.         {
  47.             //使用交换函数进行数据的交换
  48.             Swap(&arr[parent], &arr[child]);
  49.             child = parent;//进行完上面的交换操作之后，我们之前的child已经变成了parent了
  50.             //那么我们接着进行判断，判断现在的位置和父节点的大小，
  51.             //我们利用现有的child进行父节点的寻找
  52.  
  53.             //现在的child就是之前我们的parent的位置,是下标，child到了parent下标的位置
  54.             //我们利用新的child找新的父节点
  55.  
  56.             //child走到parent的位置，parent走到(child - 1) / 2这个位置
  57.             parent = (child - 1) / 2;
  58.         }
  59.         else//child位置的值比parent位置的值大
  60.         {
  61.             break;
  62.             //我们不不用调整了,直接跳出
  63.         }
  64.     }
  65.  
  66. }
  67. /*
  68. 进行交换函数之后，我们原先的child变成了parent了，就是位置变了
  69. 然后我们这个位置的数据相较于上面的数据还是子节点
  70. 我们要利用这个子节点去寻找上面的父节点
  71. child = parent;
  72. parent = (child - 1) / 2;
  73. 这两句代码
  74. 假如我们插入的数据是6
  75. 那么我们进行完交换函数之后这个6就是新的parent
  76. 但是对于现在6的父节点来说,6还是子节点，只不过子节点有了新的位置
  77. 我们一开始的parent是下标，那么现在的child就是之前我们的parent的位置
  78. */
  79.  
  80.  
  81.  
  82. //插入数据
  83. void HPPush(HP* php, HPDataType x)
  84. {
  85.     assert(php);
  86.     //在插入之前我们需要判断底层空间是否足够
  87.     if (php->size == php->capacity)//说明空间是不够的
  88.     {
  89.         //空间不够我们就进行扩容操作
  90.         int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
  91.         HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
  92.         if (tmp == NULL)
  93.         {
  94.             perror("ralloc,fail!");
  95.             exit(1);
  96.         }
  97.         //申请成功
  98.         php->arr = tmp;//将申请到的空间给数组
  99.         php->capacity = newcapacity;//将capacity进行更新
  100.  
  101.     }
  102.  
  103.     //插入数据
  104.     php->arr[php->size] = x;
  105.  
  106.     //一开始的size是0，那么我们就往数组中下标为0的位置进行插入数据
  107.  
  108.     //我们要进行堆的向上调整，保证这个堆是小堆
  109.     //我们这里是一个个数据进行插入的，所以一开始的size是0
  110.     AdjustUp(php->arr, php->size);
  111.  
  112.     php->size++;
  113.     //插入完数据之后我们需要进行size++操作，因为我们多了一个有效数据
  114. }
  115.  
  116. //向下调整法
  117. //如果我们建大堆的话，我们需要将循环内条件语句的条件进行改变
  118. //如果右孩子比左孩子要大，我们就进行child++操作
  119. //if (child + 1 < n && arr[child] < arr[child + 1])
  120. //除了要改变这个，我们还要if (arr[child] > arr[parent])
  121. //将大的孩子放上面去
  122.  
  123.  
  124. void AdhustDown(HPDataType*arr, int parent, int n)
  125. //第一个数据是我们要调整的数组，第二个参数是父节点，就是我们开始进行调整的位置的下标对应的元素，第三个是数组中有效的元素个数
  126. {
  127.     //我们已知Parent，那么我们能够通过2i+1或者2i+2找到这个父节点的左右子节点
  128.     int child = parent * 2 + 1;//左孩子
  129.     while (child<n)//我们不能让child因为++操作导致越界
  130.     {
  131.         //找左右孩子中最小的那个，我们与父节点进行交换操作
  132.         if (child + 1 < n && arr[child] > arr[child + 1])
  133.         {
  134.     //假设我们的子节点只有一个左节点的话，那么我们就可以通过child+1<n      
  135.     //这个条件避免child++，避免了越界访问，我们直接让左节点和父节点进行交换
  136.             //child+1必须小于n我们才能往下进行调整操作，避免越界访问
  137.             //假设左边的是56，右边的是15
  138.             child++;//我们进行child++操作，然后child就跑到了15的位置，然后我们将15和父节点进行交换
  139.         }
  140.         if (arr[child] < arr[parent])//如果子节点小于父节点的话我们就进行交换
  141.         {
  142.             Swap(&arr[child], &arr[parent]);
  143.             //交换完成之后我们让parent走到child的位置
  144.             parent =child ;
  145.             //child走到当前位置的左孩子的位置
  146.             child = parent * 2 + 1;
  147.         }
  148.         else//如果Parent比child小的话，那么我们就没必要向下进行调整了
  149.         {
  150.             break;//我们直接跳出
  151.         }
  152.     }
  153. }
  154.  
  155. //删除数据
  156. void HPPop(HP* php)
  157. {
  158.     assert(php&&php->size);//传的数据不能为0并且数组内有效的数据要大于0我们才能进行删除操作
  159.  
  160.     //现在第一步我们将堆顶的数据和最后一个数据进行交换
  161.     Swap(&php->arr[0], &php->arr[php->size - 1]);
  162.     //那么我们现在就已将将原先的堆顶数据删除了
  163.     //下面我们就需要解决将交换数据后的堆变成一个有效的小堆
  164.     php->size--;
  165.     //我们现在进行堆顶的向下调整操作
  166.     AdhustDown(php->arr, 0,php->size);//我们调整的是这个数组，我们从堆顶开始进行调整，堆顶对应的下标数据为0,我们还要将堆里面的有效数据个数传过去
  167.  
  168. }
  169.  
  170. //判断堆是否为空
  171. bool HPEmpty(HP* php)
  172. {
  173.     assert(php);
  174.     return php->size == 0;//如果size是0的话，那么这个堆就是空的，返回值就是true
  175. }
  176.  
  177. //取堆顶数据
  178. HPDataType HPTop(HP* php)
  179. {
  180.     assert(php&&php->size);//传过来的数据不能为空并且堆里面要有数据存在
  181.  
  182.     return php->arr[0];//直接返回堆顶元素
  183. }

test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include "Heap.h"
  3.  
  4. //冒泡排序
  5. //时间复杂度为O(N^2)
  6. void BubbleSort(int* arr, int n)//数组以及数组中的有效数据个数
  7. {
  8.     for (int i = 0; i < n; i++)
  9.     {
  10.         int exchange = 0;
  11.         for (int j = 0; j < n - i - 1; j++)
  12.         {
  13.             //升序
  14.             if (arr[j] > arr[j + 1])//大的在后面，那么我们就进行交换
  15.             {
  16.                 exchange = 1;
  17.                 Swap(&arr[j], &arr[j + 1]);
  18.             }
  19.  
  20.         }
  21.         if (exchange == 0)
  22.         {
  23.             //那么就说明我们经历了一趟内循环，我们的exchange并没有改变，就说明这个数组可能之前就是有序的
  24.             break;
  25.         }
  26.     }
  27. }
  28. /*
  29. 向上调整算法的时间复杂度和层次有关的
  30. 2^k-1=n     n是总节点个数
  31. 那么k=log(n+1)
  32.  
  33. 那么向上调整算法的最差的情况是log(N)
  34. 因为我们向上调整算法在这里的外面还有层循环，那么时间复杂度是Nlog(N)
  35.  
  36.  
  37. 向上调整算法的时间复杂度也是log(N)
  38.  
  39.  
  40. 那么这里的堆排序的时间复杂度是O(n*log n)
  41. */
  42. //堆排序
  43. //期望空间复杂度是O(1) ，不额外的开辟空间
  44. //时间复杂度是O()
  45. void HeapSort(int* arr, int n)
  46. {
  47.     //根据数组来建堆,那么我们就需要便利数组
  48.     //建小堆---降序
  49.     // 向上调整算法建堆
  50.     //for (int i = 0; i < n; i++)
  51.     //{
  52.     //  AdjustUp(arr, i);//我们给的参数是i,就是开始 调整数字的 下标，我们是从数组第一个元素进行调整的，i=0开始的
  53.     //}
  54.  
  55.     //向下调整算法建堆
  56.     //我们需要通过最后一个元素的下标n-1找到他的父节点，从这个点开始进行操作
  57.     //父节点：（n-1  -1）/2
  58.     for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  59.     {
  60.         AdhustDown(arr, i, n);//我们从i这个位置开始向下调整
  61.     //i一开始的位置就是最后一个数据的父节点，我们从这个父节点开始向下操作
  62.  
  63.     }
  64.  
  65.     //循环将堆顶数据跟最后位置的数据（会变化，每次减小一个数据）进行交换
  66.     int end = n - 1;//n是数组的有效个数，那么最后一个数据的下标是n-1
  67.     while (end>0)//end会一直--，但是end必须大于0
  68.     {
  69.         Swap(&arr[0], &arr[end]);//将第一个数据和最后一个数据进行交换
  70.         //那么我们就要对现在的剩下的堆进行调整
  71.         //我们采用向下调整的方法
  72.         AdhustDown(arr, 0, end);//我们从根进行调整，那么第二个参数就是0
  73.             //n-1=end,就是我们只需要对剩下的n-1个数据进行向下调整，那么第三个参数就是我们调整的有效数据n-1个
  74.         end--;
  75.     }
  76. }
  77. /*
  78. 我们先用向上调整法将给的数组进行建小堆的操作
  79. 然后建完小堆之后我们利用循环将堆顶的数据和最后一个数据进行交换
  80. 循环停止的条件是end>0
  81.  
  82. 在循环中，我们先利用交换函数将堆顶数据和堆尾数据进行交换
  83. 然后利用我们的向下排序的方法进行正确的小堆排序
  84. 然后进行end--的操作
  85.  
  86. 每次我们通过上面的操作就能将堆顶的最小的数据放到后面，然后剩下的就是较大的数字
  87. 最后我们就实现了降序的操作
  88.  
  89.  
  90.  
  91. */
  92. void test01()
  93. {
  94.     HP hp;//创建变量
  95.     //初始化
  96.     HPInit(&hp);
  97.  
  98.     int arr[] = { 17,20,10,13,19,15 };
  99.  
  100.     for (int  i = 0; i < 6; i++)
  101.     {
  102.         //将这个数组内的数据循环入堆
  103.           HPPush(&hp, arr[i]);
  104.      }
  105.  
  106.     //删除数据（出堆）
  107.     //HPPop(&hp);
  108.  
  109.     while (!HPEmpty(&hp))//堆不为空的话，那么我们就打印堆顶数据
  110.     {
  111.         printf("%d ", HPTop(&hp));
  112.         HPPop(&hp);//删除堆顶数据，换下一个数据
  113.     }
  114.  
  115.  
  116.     //销毁
  117.     HPDestroy(&hp);
  118. }
  119.  
  120. void CreateNDate()
  121. {
  122.     // 造数据
  123.     int n = 100000;
  124.     srand(time(0));
  125.     const char* file = "data.txt";
  126.     FILE* fin = fopen(file, "w");
  127.     if (fin == NULL)
  128.     {
  129.         perror("fopen error");
  130.         return;
  131.     } 
  132.     for (int i = 0; i < n; ++i)
  133.     {
  134.         int x = (rand() + i) % 1000000;
  135.         fprintf(fin, "%d\n", x);
  136.     } 
  137.     fclose(fin);
  138. }
  139.  
  140. void TOPK()
  141. {
  142.     int k = 0;
  143.     printf("请输入k：");
  144.     scanf_s("%d", &k);
  145.  
  146.     //从文件中读取前k个数据，建堆
  147.     const char* file = "data.txt";
  148.  
  149.     FILE* fout = fopen(file, "r");
  150.     if (fout == NULL)//打开失败
  151.     {
  152.         perror("fopen fail!");
  153.         exit(1);
  154.     }
  155.     //创建一个大小为k的数组,建小堆，找前k个最大的数据
  156.     int* minHeap = (int*)malloc(k*sizeof(int));
  157.     //往堆内放数据
  158.     if (minHeap == NULL)
  159.     {
  160.         perror("malloc fail!");
  161.         exit(2);
  162.     }
  163.     //循环读取文件内的数据
  164.     //从文件中读取前K个数据，
  165.     for (int i = 0; i < k; i++)
  166.     {
  167.         //从fout进行读取，读取的数据类型是%d,将读取到的数据往数组内进行存储
  168.         fscanf_s(fout, "%d", &minHeap[i]);
  169.     }
  170.  
  171.     //向下调整算法，建小堆
  172.     //调整建堆//我们从最后一个数的父节点进行调整，最后一个数的下标是k-1
  173.     for (int i = (k - 1 - 1) / 2; i>= 0; i--)
  174.     {
  175.         AdhustDown(minHeap, i, k);
  176.         //我们从最后一个节点的父节点进行向上调整操作
  177.         //一开始我们的i就被定义成了这个父节点的下标的大小
  178.     }
  179.  
  180.     //那么我们建好堆之后我们就接着读取文件中剩下的N-K个数据
  181.     //我们进行循环读取
  182.     int x = 0;//我们创建一个x变量，将每次读取的数据存在x中与堆顶的数据进行循环比较
  183.     while (fscanf(fout,"%d",&x)!=EOF)//直到读到文件末尾
  184.     {
  185.         //读取到的数据与堆顶的数据进行比较
  186.         //如果比对顶值大，交换入堆
  187.         if (x < minHeap[0])
  188.         {
  189.             minHeap[0] = x;//直接将x放到堆顶
  190.  
  191.             //经过上面的操作之后，那么这个堆就不是一个小堆了
  192.             //我们利用向下调整算法重新将这个堆变成小堆
  193.             AdhustDown(minHeap, 0, k);
  194.  
  195.         }
  196.     }
  197.  
  198.     //走到这里我们已经读完了,那么这个堆剩下的数据就是这个文件前K个最大的数据了
  199.     for (int  i = 0; i < k; i++)
  200.     {
  201.         printf("%d ", minHeap[i]);
  202.     }
  203.     fclose(fout);
  204. }
  205.  
  206.  
  207. int main()
  208. { 
  209.     //test01();
  210.  
  211.     //给定一个数组，对数组中的数据进行排序
  212.     //int arr[] = { 17,20,10,13,19,15 };
  213.  
  214.     BubbleSort(arr, 6);//冒泡排序
  215.     //HeapSort(arr, 6);//堆排序
  216.     //for (int i = 0; i < 6; i++)
  217.     //{
  218.     //  
  219.     //  printf("%d ",arr[i]);
  220.     //}
  221.     //printf("\n");
  222.     //CreateNDate();//创建一个有10w个数据的文件
  223.     TOPK();
  224.     return 0;
  225. }

4.实现链式结构二叉树

遍历规则

按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：

1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前

访问顺序为：根结点、左⼦树、右⼦树

2）中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）

访问顺序为：左⼦树、根结点、右⼦树

3）后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后

访问顺序为：左⼦树、右⼦树、根结点

遍历规则解释：

前序遍历：

一开始遍历的是1，那么我们遍历完1之后，进行1的打印，然后箭头移动，箭头指向了2，打印了2

因为2是个头节点，那么我们继续往下遍历，箭头指向了4，那么打印了4，最后箭头指向了3，打印了3，规则就是先根再左右

最后打印的就是1 2 4 3

中序遍历:

我们遍历的顺序是左子树、根节点、右子树

那么我们先遍历左子树，那么箭头指向了2，那么对于2来说，4是左子树，那么箭头来到了4

那么我们将4打印，那么对于4的话，已经没有子节点了，那么箭头就回到了2

我们打印根节点2，打印完这个根节点，我们的箭头就应该指向以2为顶点的树的右子树

但是2没有右子树

所以我们的箭头回到了1，对于1这个根节点来说，左子树已经打印完了，我们就该开始打印根节点1了，打印完根节点之后我们就开始打印右节点了，那么箭头就指向了3了

那么最后打印的就是4 2 1 3

后序遍历：

后续遍历的顺序是左子树、右子树、根节点

一开始的箭头指向1,2是1的左子树，因为4是2的左子树，那么箭头就来到了4的位置，将4进行打印

因为2没有右子树，那么我们的箭头就直接跳到了2这个根节点的位置了，将2进行打印

对于1这颗二叉树来说的话，我们的左子树已经全部打印完成了，那么就开始右子树的打印了，箭头指向了3的位置，将3打印完成之后，我们的箭头回到根节点1的位置，最后打印根节点

那么最后打印的就是4 2 3 1

对于这个二叉树来说的话

前序遍历：1 2 4 6 5 3

中序遍历：4 6 2 5 1 3

后续遍历：6 4 5 2 3 1

解释前序遍历的代码中的递归

 

我们用这张图进行解释

一开始我们的的root节点是1，判断节点不为空，那么我们就进行条件语句下面的代码

我们将root节点内的数据打印，就是1

然后我们进入到了root的左节点的递归里面了，root→left是2

当2是root节点时

我们先判断传过来的root不是空节点

那么我们将2进行打印，然后右进入到2的子节点的递归中，子节点就是4

当4是root节点时

我们先判断传过来的root是不是空的，然后我们进行打印4

我们进入到了root→left

发现4没有左节点，那么传的就是空值，我们直接退出

4同样没有右节点，我们依然退出

那么我们就原路返回了

对于root=2时，我们的左节点递归已经结束了，那么我们进行2的右节点递归，但是2的右节点是空的，所以我们直接退出

那么2这个树我们已经递归完成了

我们就回到了1是root了

对于1来说，左节点已经递归完了，那么就进行右节点的递归了

就是3

当3是root的时候，我们将3进行打印，打印完进入左递归，是空值，返回

然后进入右递归，是空值，返回

那么最后我们打印的就是1 2 4 3

整个递归的流程图如下：

第四种遍历方法：层序遍历\

对于这么一个二叉树来说，我们通过层序遍历最后得到的是1 2 3 4

这里我们是不能通过递归来实现的

但是我们可以借助队列来实现这么一个结构

队列的结构是先进先出

恰好我们队列的底层结构就是链表来实现的，和这里的链式二叉树一样的

我们将之前写的Queue.c文件和Queue.h文件复制到我们链式二叉树的文件夹里面

typedef struct BinaryTreeNode* QDataType;

struct BinaryTreeNode*这个就是我们要保存在队列中的数据类型

之前的在队列中保存的数据类型是int类型

队列中存储的是堆节点的地址

那么存储的就是节点的指针，那么我们将这个类型重新定义

  1. //层序遍历---借助数据结构（队列）
  2. void Levelorder(BTNode* root)
  3. {
  4.     //创建一个队列结构
  5.     Queue q;
  6.     QueueInit(&q);//进行初始化
  7.     //第一步：让根节点直接入队列
  8.     QueuePush(&q,root);//往队列中push根节点
  9.     while (!Queuempty(&q))//只要队列不为空，我们就一直取队头数据
  10.     {
  11.         //取队头数据
  12.         BTNode*front=QueueFront(&q);//将队头取出，返回值是节点的地址
  13.         //打印对头
  14.         printf("%d ", front->data);
  15.         //让队头出队列
  16.         QueuePop(&q);//那么此时的队列是空的
  17.  
  18.         //将队头节点的左右孩子入队列
  19.         if (front->left)//如果这个节点的左孩子不是空的，那么我们将这个节点往队列中入
  20.         {
  21.             QueuePush(&q, front->left);
  22.         }
  23.         if (front->right)//如果这个节点的右孩子不是空的，那么我们将这个节点往队列中入
  24.         {
  25.             QueuePush(&q, front->right);
  26.         }
  27.  
  28.  
  29.     }
  30.  
  31.     QueueDestroy(&q);//销毁
  32. }

判断是否为完全二叉树

除了最后一层，其它层的节点数达到最大，那么这个数就是完全二叉树

这里涉及到每层，那么这里还是要借助队列这么一个结构的

我们先取根节点放进队列，队列不为空，我们将队列中的节点取出来

然后将这个节点的左右孩子一起放进队列中去

我们再将队头取出，将队头的左右孩子放进去，如果孩子为空放个NULL进去

如果我们队列剩下的都是NULL的话，我们将队列中第一个NULL取出

那么我们取到的数据为空，取到为空的情况我们就跳出循环

那么最后就是这么个情况

如果我们的二叉树现在是非完全二叉树是个什么情况呢？

那么会有很明显的不同的

如果是完全二叉树，跳出第一个循环之后，队列中全是NULL节点

如果不是完全二叉树，跳出一个循环之后，那么队列还有一个非空节点

如果是上面这张图的话，4是2的右节点，那么这个数就不是一个完全二叉树，因为没有遵循从左到右的原则

但是如果4是2的左节点的话，那么这个数就是一个完全二叉树

二叉树链式结构的实现

这里我们用到了队列里面的相关知识

test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"tree.h"
  3.  
  4. BTNode* buyNode(BTDataType x)//创建一个节点
  5. {
  6.  
  7.     BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
  8.     if (newnode == NULL)
  9.     {
  10.         perror("malloc fail!");
  11.         exit(1);
  12.     }
  13.     newnode->data = x;
  14.     newnode->left = newnode->right = NULL;
  15.     return newnode;
  16. }
  17. void test01()
  18. {
  19.     BTNode* node1 = buyNode(1);
  20.     BTNode* node2 = buyNode(2);
  21.     BTNode* node3 = buyNode(3);
  22.     BTNode* node4 = buyNode(4);
  23.     /*BTNode* node5 = buyNode(5);
  24.     BTNode* node6 = buyNode(6);*/
  25.  
  26.     node1->left = node2;
  27.     node1->right = node3;
  28.     node2->left = node4;
  29.     /*node2->right = node5;
  30.     node3->left = node6;*/
  31.     前序遍历
  32.     //PreOrder(node1);// 1 2 4 3
  33.  
  34.     //printf("\n");
  35.     中序遍历
  36.     //InOrder(node1);// 4 2 1 3
  37.  
  38.     二叉树节点的个数
  39.     //printf("size:%d\n", BinaryTreeSize(node1));//4
  40.     printf("size:%d\n", BinaryTreeSize(node2));//2
  41.  
  42.     二叉树叶子结点的个数
  43.     //printf("leaf size:%d\n", BinaryTreeLeafSize(node1));
  44.  
  45.     第k层节点的个数
  46.     //printf("k size:%d\n", BinaryTreeLevelKSize(node1, 3));
  47.  
  48.     二叉树的高度
  49.     //printf("depth/height :%d\n", BinaryTreeDepth(node1));
  50.  
  51.     查找值为x的节点
  52.     //BTNode*find=BinaryTreeFind(node1, 5);
  53.     //printf("%s\n", find == NULL ? "没找到":"找到了");
  54.  
  55.     //层序遍历
  56.     /*Levelorder(node1);*/
  57.  
  58.     //判断是否为完全二叉树
  59.     bool ret=BinaryTreeComplete(node1);
  60.     printf("%s\n", ret == false ?"不是完全二叉树" : "是完全二叉树");
  61.  
  62.     //二叉树的销毁
  63.     BinaryTreeDestory(&node1);
  64.  
  65. }
  66. int main( )
  67. {
  68.     test01();
  69.     return 0;
  70. }

tree.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"tree.h"
  3. #include"Queue.h"
  4. //前序遍历    根左右
  5. void PreOrder(BTNode* root)//我们传个根节点就行了，我们是从根节点开始遍历的
  6. {
  7.     if (root == NULL)
  8.     {
  9.         return;
  10.     }
  11.     printf("%d ", root->data);
  12.     PreOrder(root->left);//遍历左子树
  13.     PreOrder(root->right);//遍历右子树
  14.  
  15. }
  16.  
  17. //中序遍历   左根右
  18. void InOrder(BTNode* root)
  19. {
  20.     if (root == NULL)
  21.     {
  22.         return;
  23.     }
  24.     InOrder(root->left);
  25.     printf("%d ", root->data);
  26.     InOrder(root->right);
  27.  
  28. }
  29.  
  30. //后序遍历   左右根
  31. void PostOrder(BTNode* root)
  32. {
  33.     if (root == NULL)
  34.     {
  35.         return;
  36.     }
  37.     PostOrder(root->left);
  38.     PostOrder(root->right);
  39.     printf("%d ", root->data);
  40. }
  41.  
  42. // ?叉树结点个数
  43.  
  44. //第一种方法（不可行）
  45. //int size = 0;
  46. //void BinaryTreeSize(BTNode* root)
  47. //{
  48. //    if (root == NULL)
  49. //    {
  50. //        return 0;
  51. //    }
  52. //    //说明当前节点不为空
  53. //    size++;
  54. //    //遍历整个二叉树的 左右节点
  55. //    BinaryTreeSize(root->left);
  56. //    BinaryTreeSize(root->right);
  57. //    return size;
  58. //    
  59. //}
  60. //
  61. 第二种方法（不可行，有弊端，每次调用函数要提前将size置为0）
  62. //void BinaryTreeSize(BTNode* root,int *psize)
  63. //{
  64. //    if (root == NULL)
  65. //    {
  66. //        return 0;
  67. //    }
  68. //    //说明当前节点不为空
  69. //    (*psize)++;
  70. //    //遍历整个二叉树的 左右节点
  71. //    BinaryTreeSize(root->left,psize);
  72. //    BinaryTreeSize(root->right,psize);
  73. //    
  74. //    //不是空节点点我们就进行计数
  75. //
  76. //    /*
  77. //    * 我们的想法（错的）
  78. //    如果我们在函数内设置size的话，我们在进行完1 2 4 3 这个堆的时候
  79. //    我们递归完左子树，size++已将isze变为3了
  80. //
  81. //    上面这种想法就是错的
  82. //    但是当我们开始递归1的右子树的时候，我们传的size仍然是1，
  83. //    
  84. //    解释为什么：
  85. //    因为我们传的wsize是值，不是地址
  86. //    递归函数内的size++并不能将size的大小直接改变
  87. //    所以我们在右子树的递归的时候我们的size就是1
  88. //
  89. //    因为我们在每个递归中的size都是传的值，所以我们不能将size进行改变
  90. //    */
  91. //    /*
  92. //    ，假设我们每次传的是值的话，我们将这块地址取出来，这块地址里面存的就是size，我们进行++
  93. //    不管是在左子树还是右子树的递归中，我们每次调用的时候，都要先取这个地址里面的数据
  94. //    这个数据是可以进行改变的
  95. //    
  96. //    此次递归的psize地址指向的size的大小就是上次递归的size加加后的大小
  97. //    */
  98. //    //但是这种方法有个弊端，每次我们在调用求节点个数的这个函数的时候
  99. //    //我们都要将size重新置为0
  100. //}
  101.  
  102.  
  103. // 二叉树结点个数
  104. //第三种方法：
  105. int  BinaryTreeSize(BTNode* root)
  106. {
  107.     if (root == NULL)
  108.     {
  109.         return 0;
  110.     }
  111.     return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
  112. }
  113. /*
  114. 堆：1 2 4 3
  115. 4的左子树和右子树都是0，那么我们就return 1 + 0+ 0
  116. 回到2，因为2的左节点4返回的指是1，但是没有右节点，所以右节点返回的是0
  117. 那么对于2的话，return 1+ 1 +0
  118. 对于1的话，左节点2的返回值是2,1的右节点3的返回值因为没有左右子节点
  119. 所以3的返回值是1
  120. 那么1的返回值就是1+2+1=4
  121. 那么这个4就是我们这个堆的节点数
  122. */
  123.  
  124.  
  125. // ?叉树叶?结点个数
  126. //所谓的叶子节点就是没有子节点的节点
  127. int BinaryTreeLeafSize(BTNode* root)
  128. {
  129.     if (root == NULL)
  130.     {
  131.         return 0;
  132.     }
  133.     if (root->left == NULL && root->right == NULL)//说明这个节点就是叶子节点，没有子节点
  134.     {
  135.         return 1;
  136.     }
  137.     //进行递归
  138.     return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
  139.     //直接将左子树的叶子结点的个数和右子树叶子节点的个数进行返回
  140. }
  141.  
  142. // ?叉树第k层结点个数
  143. //左子树第k层节点的个数+右子树第k层节点个数
  144. int BinaryTreeLevelKSize(BTNode* root, int k)
  145. {
  146.     //递归一定要有结束条件
  147.     if (root == NULL)
  148.     {
  149.         return 0;
  150.     }
  151.  
  152.     //判断是不是第k层
  153.     if (k == 1)//就是第k层
  154.     {
  155.         return 1;
  156.     }
  157.     return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
  158. }
  159. //这里我们采用的是传值操作，左右子树的操作不会因为k受到影响
  160.  
  161.  
  162. //?叉树的深度/?度
  163. int BinaryTreeDepth(BTNode* root)
  164. {
  165.     if (root == NULL)
  166.     {
  167.         return 0;
  168.     }
  169.  
  170.     //当前节点不为空，那么我们对左子树和右子树进行遍历
  171.     int leftDep=BinaryTreeDepth(root->left);
  172.     int rightDep = BinaryTreeDepth(root->right);
  173.  
  174.     return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
  175.     //因为是个递归代码，我们从左后一个节点进行思考
  176.     /*
  177.     1 2 4 3
  178.     对于左子树的话，4是最后一个节点
  179.     那么我们从4开始
  180.     因为左右节点都是空的，那么左节点和右节点的大小都是0
  181.     那么在返回的时候对于2的话，4这个节点返回了1
  182.     所以2的左节点返回值是1，因为右节点是空，返回0
  183.     那么对于1的话，2这个节点的返回值是1+1
  184.      对于1的话，左节点返回值是2，右节点是3
  185.      因为3这个节点的左右节点都是空，那么就返回1
  186.      那么因为左节点返回的是2
  187.      右节点返回的是1
  188.      2>1
  189.      所以对于节点1的话，返回的值是1+2=3
  190.      那么最终的话我们的层数是3层
  191.     */
  192. }    
  193.  
  194.  
  195. // ?叉树查找值为x的结点
  196. //找到对应节点就返回这个节点，没有找到就返回空
  197. BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
  198. {
  199.     //要么出现在左子树，要么出现在右子树
  200.     if (root == NULL)
  201.     {
  202.         return 0;
  203.     }
  204.     if (root->data == x)
  205.     {
  206.         return root;
  207.     }
  208.     //走到这这里说明，root不为空，值不为x,那么我们继续进行递归
  209.     BTNode* leftFind=BinaryTreeFind(root->left, x);
  210.     if (leftFind)//在左子树中找到了这个节点,我们就直接返回，就不用在右子树中进行寻找了
  211.     {
  212.         return leftFind;
  213.     }
  214.     BTNode* rightFind = BinaryTreeFind(root->right, x);
  215.     if (rightFind)//在左子树中找到了这个节点
  216.     {
  217.         return rightFind;
  218.     }
  219.     //左子树和右子树都没找到，那么我们直接返回NULL
  220.     return NULL;
  221. }
  222.  
  223.  
  224. // ?叉树销毁
  225. void BinaryTreeDestory(BTNode** root)//传来的是root的地址，我们用二级指针进行接收
  226. {
  227.     //销毁一个堆的话，我们要先将左子树和右子树先销毁，最后再将根进行销毁
  228.     if (*root == NULL)//已经是空的，就没必要进行销毁了
  229.     {
  230.         return;
  231.     }
  232.     BinaryTreeDestory(&((*root)->left));//对*root进行解引用我们才能找到left,这里的root是二级指针
  233.     //*root指向第一个节点的指针，再取成员left,然后对整体取地址
  234.     //上面的是左子树
  235.     BinaryTreeDestory(&((*root)->right));///右子树
  236.  
  237.     //销毁根节点
  238.     free(*root);
  239.     *root = NULL;
  240.     /*
  241.     堆：1 2 4 3
  242.     当节点在4的时候，我们对4的左节点和右节点都进行递归了
  243.     因为都是空的，我们返回到了4这个节点，然后将4这个节点销毁了
  244.     销毁完就回到了2这个节点，因为2的左节点已经销毁了
  245.     那么就进行2的右节点的销毁了，右节点是空的，所以返回的是空
  246.     那么我们就将2销毁了
  247.     2销毁完就回到1这个节点了
  248.     对于1这个节点来说的话，左节点2已经销毁完了
  249.     那么我们的头结点就跑到了1的右节点3那里了
  250.     对于3这个头结点来说，左右节点都是空的，那么就直接返回，那么就进行3这个节点的销毁了
  251.     那么对于1的话，左右节点都销毁了
  252.     那么就将销毁1了
  253.     */
  254. }
  255.  
  256.  
  257. //层序遍历---借助数据结构（队列）
  258. void Levelorder(BTNode* root)
  259. {
  260.     //创建一个队列结构
  261.     Queue q;
  262.     QueueInit(&q);//进行初始化
  263.     //第一步：让根节点直接入队列
  264.     QueuePush(&q,root);//往队列中push根节点
  265.     while (!Queuempty(&q))//只要队列不为空，我们就一直取队头数据
  266.     {
  267.         //取队头数据
  268.         BTNode*front=QueueFront(&q);//将队头取出，返回值是节点的地址
  269.         //打印对头
  270.         printf("%d ", front->data);
  271.         //让队头出队列
  272.         QueuePop(&q);//那么此时的队列是空的
  273.  
  274.         //将队头节点的左右孩子入队列
  275.         if (front->left)//如果这个节点的左孩子不是空的，那么我们将这个节点往队列中入
  276.             QueuePush(&q, front->left);
  277.         {
  278.         }
  279.         if (front->right)//如果这个节点的右孩子不是空的，那么我们将这个节点往队列中入
  280.         {
  281.             QueuePush(&q, front->right);
  282.         }
  283.  
  284.  
  285.     }
  286.  
  287.     QueueDestroy(&q);//销毁
  288. }
  289.  
  290. //判断二叉树是否为完全二叉树
  291. //借助队列
  292. bool BinaryTreeComplete(BTNode* root)
  293. {
  294.     Queue q;
  295.     QueueInit(&q);//进行初始化
  296.  
  297.     //将二叉树根节点入队列
  298.     QueuePush(&q, root);//往队列中push根节点
  299.  
  300.     while (!Queuempty(&q))//队列不为空，我们就循环取队头
  301.     {
  302.         BTNode* front = QueueFront(&q);//将队头取出
  303.  
  304.         QueuePop(&q);//让队头出队，保证下次取到的是最新的队头数据
  305.  
  306.  
  307.         //如果我们取到的front是空的话
  308.         if (front == NULL)//如果此时的队头是空的，那么我们就取不到左右孩子
  309.         {
  310.             break;
  311.         }
  312.  
  313.         //将队头的左右孩子取出放到队列中
  314.         QueuePush(&q, front->left);
  315.         QueuePush(&q, front->right);
  316.     }
  317.  
  318.     //此时队列不一定为空
  319.     while (!Queuempty(&q))//只要队列不为空
  320.     {
  321.         BTNode* front = QueueFront(&q);//取队头
  322.         QueuePop(&q);//出队列
  323.         //如果我们在队列中剩下的节点中遇到了节点的话，那么这个树就不是一个完全二叉树了
  324.         if (front != NULL)
  325.         {
  326.             QueueDestroy(&q);//销毁
  327.             return false;
  328.         }
  329.     }
  330.  
  331.  
  332.     QueueDestroy(&q);//销毁
  333.  
  334.     //到这里就说明没有找到完全二叉树
  335.     return true;
  336. }
  337. /*
  338. 如果是完全二叉树，跳出第一个循环之后，队列中全是NULL节点
  339.  
  340. 如果不是完全二叉树，跳出一个循环之后，那么队列还有一个非空节点
  341.  
  342.  
  343. */

tree.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. #include <stdbool.h>
  6.  
  7.  
  8. //定义二叉树的链式结构
  9. //二叉树节点的结构
  10. typedef int BTDataType;
  11. typedef struct BinaryTreeNode
  12. {
  13.     BTDataType data;
  14.     struct BinaryTreeNode* left;//指向左孩子节点的指针
  15.     struct BinaryTreeNode* right;//指向右孩子节点的指针
  16.  
  17. }BTNode;
  18.  
  19. //前序遍历
  20. void PreOrder(BTNode*root);//我们传个根节点就行了，我们是从根节点开始遍历的
  21.  
  22. //中序遍历
  23. void InOrder(BTNode* root);
  24.  
  25. //后序遍历
  26. void PostOrder(BTNode* root);
  27.  
  28.  
  29. // ⼆叉树结点个数
  30. int  BinaryTreeSize(BTNode* root);
  31.  
  32.  
  33. // ⼆叉树结点个数
  34. //void  BinaryTreeSize(BTNode* root, int* psize);
  35.  
  36.  
  37. // ⼆叉树叶⼦结点个数
  38. int BinaryTreeLeafSize(BTNode* root);
  39.  
  40. // ⼆叉树第k层结点个数
  41. int BinaryTreeLevelKSize(BTNode* root, int k);
  42.  
  43. //⼆叉树的深度/⾼度
  44. int BinaryTreeDepth(BTNode* root);
  45.  
  46. // ⼆叉树查找值为x的结点
  47. BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
  49. // ⼆叉树销毁
  50. void BinaryTreeDestory(BTNode** root);
  51.  
  52. //层序遍历
  53. void Levelorder(BTNode* root);
  54.  
  55. //判断二叉树是否为完全二叉树
  56. bool BinaryTreeComplete(BTNode* root);

Queue.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"Queue.h"
  3.  
  4. //初始化
  5. void QueueInit(Queue* pq)
  6. {
  7.     assert(pq);//传过来的不能是空指针 
  8.  
  9.     pq->phead = pq->ptail = NULL;//空的队列
  10.     pq->size = 0;
  11. }
  12.  
  13. //判断队列是否为空
  14. bool Queuempty(Queue* pq)
  15. {
  16.     assert(pq);
  17.  
  18.     return pq->phead == NULL && pq->ptail == NULL;
  19.     //如果后面的表达式成立，那么就是真，返回的是true
  20.  
  21.     //就是说如果这里的是空队列的话，那么就返回的是true
  22. }
  23.  
  24. //入队列，队尾   插入数据
  25. void QueuePush(Queue* pq, QDataType x)
  26. {
  27.     assert(pq);
  28.  
  29.     //申请新节点
  30.     QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//申请一个节点大小的空间
  31.     if (newnode == NULL)
  32.     {
  33.         perror("malloc dail!");
  34.         exit(1);
  35.     }
  36.     //对newnode进行初始化操作
  37.     newnode->data = x;
  38.     newnode->next = NULL;
  39.     if (pq->phead == NULL)//说明队列为空
  40.     {
  41.         pq->phead = pq->ptail = newnode;//那么此时的newnode不仅是头结点也是尾节点
  42.     }
  43.     else//队列不为空
  44.     {
  45.         pq->ptail->next = newnode;
  46.         //那么此时的newnode 就是新的ptail
  47.         pq->ptail = newnode;
  48.     }
  49.     pq->size++;
  50. }
  51.  
  52. //出队列,队头    删除数据    从头结点开始删除数据
  53. void QueuePop(Queue* pq)
  54. {
  55.     assert(pq);
  56.     //队列为空（不可删除数据，因为没有数据）
  57.     //队列不为空（可删除数据）
  58.  
  59.     assert(!Queuempty(pq));//队列为空白的话就报错
  60.  
  61.     //处理只有一个节点的情况，避免ptail变成野指针
  62.     //判断只有一个节点的情况
  63.     if (pq->ptail == pq->phead)//头尾指针相同，说明只有一个节点
  64.     {
  65.         free(pq->phead);//随便释放
  66.         pq->phead = pq->ptail = NULL;
  67.     }
  68.     else//处理多个节点的情况
  69.     {
  70.         //删除队头元素
  71.     //那么我们现将下个节点的位置进行保存
  72.         QueueNode* next = pq->phead->next;
  73.         //存储好之后我们直接将头结点进行释放
  74.         free(pq->phead);
  75.         pq->phead = next;//那么之前存的next就是新的头结点了
  76.     }
  77.     pq->size--;
  78. }
  79.  
  80. //取队头数据
  81. QDataType QueueFront(Queue* pq)//返回队头数据
  82. {
  83.     assert(pq);
  84.     assert(!Queuempty(pq));//队列不为空
  85.  
  86.     return pq->phead->data;//将队头里面的数据直接返回就行了
  87. }
  88.  
  89. //取队尾数据
  90. QDataType QueueBack(Queue* pq)
  91. {
  92.     assert(pq);
  93.     assert(!Queuempty(pq));//队列不为空
  94.  
  95.     return pq->ptail->data;
  96. }
  97.  
  98. //队列有效元素个数
  99. int QueueSize(Queue* pq)
  100. {
  101.     assert(pq);
  102.     //下面这种遍历的话效率太低了
  103.     //int size = 0;
  104.     定义一个指针进行遍历
  105.     //QueueNode* pcur = pq->phead;//指向队列的头结点
  106.     //while (pcur)//pcur不为空就往后走
  107.     //{
  108.     //  size++;
  109.     //  pcur = pcur->next;
  110.     //}
  111.     //return size;
  112.     return pq->size;
  113. }
  114.  
  115. //队列的销毁
  116. void QueueDestroy(Queue* pq)
  117. {
  118.     assert(pq);
  119.     //assert(!Queuempty(pq));//队列不为空
  120.     //遍历
  121.     QueueNode* pcur = pq->phead;
  122.     while (pcur)
  123.     {
  124.         //销毁之前先把下个节点进行保存
  125.         QueueNode* next = pcur -> next;
  126.         free(pcur);
  127.         //将Pcur销毁之后，那么之前保存的next就是新的头结点
  128.         pcur = next;
  129.     }
  130.     pq->phead = pq->ptail = NULL;
  131.     pq->size = 0;
  132. }

Queue.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #include<stdbool.h>
  6.  
  7.  
  8. //定义队列结构
  9. //typedef int QDataType;
  10.  
  11. typedef struct BinaryTreeNode* QDataType;
  12. //struct BinaryTreeNode*这个就是我们要保存在队列中的数据类型
  13. //struct BinaryTreeNode*这个是个数据类型，和之前的
  14. //之前的在队列中保存的数据类型是int类型
  15. //因为我们在tree.h中将结构体类型重命名了
  16. //那么我们可以这么写
  17. //typedef struct BTNode* QDataType;
  18.  
  19. typedef struct QueueNode
  20. {
  21.     QDataType data;
  22.     struct QueueNode* next;
  23.  
  24. }QueueNode;
  25.  
  26. typedef struct Queue
  27. {
  28.     QueueNode*phead;//指向头节点的指针---队头--删除数据
  29.     QueueNode*ptail;//指向尾节点的指针---队尾--插入数据
  30.     int size;//保存队列有效个数
  31. }Queue ;
  32.  
  33.  
  34. //初始化
  35. void QueueInit(Queue* pq);
  36.  
  37. //入队列，队尾   插入数据
  38. void QueuePush(Queue* pq, QDataType x);
  39.  
  40. //出队列,队头    删除数据
  41. void QueuePop(Queue* pq);
  42.  
  43. //判断队列是否为空
  44. bool Queuempty(Queue* pq);
  45.  
  46. //取队头数据
  47. QDataType QueueFront(Queue* pq);
  48.  
  49. //取队尾数据
  50. QDataType QueueBack(Queue* pq);
  51.  
  52. //队列有效元素个数
  53. int QueueSize(Queue* pq);
  54.  
  55. //队列的销毁
  56. void QueueDestroy(Queue* pq);

5.二叉树算法题

1.单值二叉树

  1. /**
  2.  * Definition for a binary tree node.定义好的二叉树节
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     struct TreeNode *left;
  6.  *     struct TreeNode *right;
  7.  * };
  8.  */
  10.  /*思路：
  11.  递归
  12.  
  13.  我们用根节点先与左节点进行比较，如果相同的话
  14.  我们进行根节点和有几点的比较
  15.  如果不行同的话，就return false
  16.  如果相同的话，我们就递归下去
  17.  */
  19.  //递归是要存在结束条件的 
  20. typedef struct TreeNode TreeNode;
  21. bool isUnivalTree(struct TreeNode* root)
  22. {
  23.      //递归是要存在结束条件的 
  24.  
  25.     if(root==NULL)
  26.     {
  27.         return true;
  28.     }
  29.  
  30.     //说明此时root不为空，那么我们进行左孩子和右孩子的比较
  31.     if(root->left&&root->left->val!=root->val)
  32.     {
  33.         //如果左孩子存在并且左孩子里面的值与根节点的值不等
  34.         return false;
  35.     }
  36.     //走到这里说明根节点的值和左孩子的值是相同的
  37.     if(root->right&&root->right->val!=root->val)
  38.     {
  39.         //如果右孩子存在并且左孩子里面的值与根节点的值不等
  40.         return false;
  41.     }
  42.     //走到这里说明根节点的值和左右孩子节点的值相同
  43.  
  44.     //那么我们接着递归这整个二叉树的左子树和右子树
  45.     //左子树和右子树都满足条件的话那么这个树就是单值二叉树了
  46.     return isUnivalTree(root->left)&&isUnivalTree(root->right);
  47. }

 

2.相同的树

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     struct TreeNode *left;
  6.  *     struct TreeNode *right;
  7.  * };
  8.  */
  10.  //不仅要判断节点值相不相等，而且还要判断两个二叉树的结构是不是一样的
  11.  //这里我们不需要借助数组，也不需要借助数列
  12.  //我们采用递归的方式
  13.  //两棵树都为空树的话，那么我们返回true
  14. //如果其中一个树为空树的话，那么就不相同
  15.  
  16.  
  17. //想要判断两个二叉树是不是相同的树，那么我们就要进行同步递归
  18. typedef struct TreeNode TreeNode;
  19.  
  20. bool isSameTree(struct TreeNode* p, struct TreeNode* q) //参数是指向两个二叉树根节点的指针
  21. {
  22.     //判断是否为空树
  23.     if(p==NULL&&q==NULL)
  24.     {
  25.         return true;//两个树都是空的，那么我们直接返回true
  26.     }
  27.     //或者其中一个为空
  28.     if(p==NULL||q==NULL)
  29.     {
  30.         return false;
  31.     }
  32.     //走到这里就说明都不为空,就说明整体结构是相同的，那么我们下面就对节点的数据进行判断是否相同
  33.     if(p->val!=q->val)
  34.     {
  35.         return false;
  36.     }
  37.     //走到这里说明两个二叉树结构相同，值也相同
  38.  
  39.     //那么我们就递归这两个二叉树的左子树和右子树
  40.     return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
  41. //只要前面的左子树返回的是true，那么我们才能进行后面的右子树的判断
  42. }

我们先判断两个数的结构是否相同

再判断节点的值是否相同

3.对称二叉树

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     struct TreeNode *left;
  6.  *     struct TreeNode *right;
  7.  * };
  8.  */
  10.  bool isSameTree(struct TreeNode* p, struct TreeNode* q) //参数是指向两个二叉树根节点的指针
  11. {
  12.     //判断是否为空树
  13.     if(p==NULL&&q==NULL)
  14.     {
  15.         return true;//两个树都是空的，那么我们直接返回true
  16.     }
  17.     //或者其中一个为空
  18.     if(p==NULL||q==NULL)
  19.     {
  20.         return false;
  21.     }
  22.     //走到这里就说明都不为空,就说明整体结构是相同的，那么我们下面就对节点的数据进行判断是否相同
  23.     if(p->val!=q->val)
  24.     {
  25.         return false;
  26.     }
  27.     //走到这里说明两个二叉树结构相同，值也相同
  28.  
  29.     //那么我们就递归这两个二叉树的左子树和右子树
  30.     return isSameTree(p->left,q->right)&&isSameTree(p->right,q->left);
  31. //只要前面的左子树返回的是true，那么我们才能进行后面的右子树的判断
  32. }
  33. bool isSymmetric(struct TreeNode* root)
  34. {
  35.     //将这个二叉树看成是两棵树
  36.     return isSameTree(root->left,root->right);
  37. }

我们将这么一棵二叉树看成是两个数，左子树和右子树

我们先调用上面相同树的代码

判断这两个数是否为空

然后因为是对称的，所以我们判断左子树的左节点和右子树的右节点

以及右子树的左节点和左子树的右节点是否相等

满足了这么几个条件那么这个二叉树就是对称二叉树了

 

4.另一棵树的子树

 

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     struct TreeNode *left;
  6.  *     struct TreeNode *right;
  7.  * };
  8.  */
  9. typedef struct TreeNode TreeNode;
  10.  
  11. bool isSameTree(struct TreeNode* p, struct TreeNode* q) //参数是指向两个二叉树根节点的指针
  12. {
  13.     //判断是否为空树
  14.     if(p==NULL&&q==NULL)
  15.     {
  16.         return true;//两个树都是空的，那么我们直接返回true
  17.     }
  18.     //或者其中一个为空
  19.     if(p==NULL||q==NULL)
  20.     {
  21.         return false;
  22.     }
  23.     //走到这里就说明都不为空,就说明整体结构是相同的，那么我们下面就对节点的数据进行判断是否相同
  24.     if(p->val!=q->val)
  25.     {
  26.         return false;
  27.     }
  28.     //走到这里说明两个二叉树结构相同，值也相同
  29.  
  30.     //那么我们就递归这两个二叉树的左子树和右子树
  31.     return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
  32. //只要前面的左子树返回的是true，那么我们才能进行后面的右子树的判断
  33. }
  34. bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
  35. {
  36.     if(root==NULL)//如果root是空树的话，那么我们就没必要进行比较了
  37.     {
  38.         return false;
  39.     }
  40.     if(isSameTree(root,subRoot))//判断这两个树是不是相同的，根据一开始的根节点进行判断
  41.     {
  42.         return true;
  43.     }
  44.     //走到这里说明root和subRoot不是相同的树
  45.     //那么我们还要递归root的左子树是不是和subRoot相等的
  46.     //如果不相等的话，我们还要递归root的右子树
  47.     return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
  48. //我们这里用的是或，因为假如的话我们递归左子树的时候就判断出相等，那么就没必要递归右子树了
  49. //但是左子树不相等的话，那么我们就进行右子树的递归
  50. }
  51. /*
  52. 我们先判断的是根节点和subRoot是否相等
  53. 不相等的话我们进行根节点的左子树和右子树与subRoot是否相等的判断
  54. */

5.二叉树的前序遍历

 

 

 

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     struct TreeNode *left;
  6.  *     struct TreeNode *right;
  7.  * };
  8.  */
  9. /**
  10.  * Note: The returned array must be malloced, assume caller calls free().
  11.  */
  12.  //返回的是整型数组，数组必须是动态开辟的
  13.  
  14.  /*
  15.  求二叉树节点的个数就是这个二叉树左子树节点和右子树节点的个数的总和*/
  16.  typedef struct TreeNode TreeNode;
  17.  int TreeSize(TreeNode* root)
  18. {
  19.     if(root==NULL)
  20.     {
  21.         return 0;
  22.     }
  23.     return 1+TreeSize(root->left)+TreeSize(root->right);
  24.     //左子树节点的个数和右子树节点的个数
  25. }
  26.  
  27. void _preorderTraversal(TreeNode* root,int *arr,int* pi)//进行递归的函数//第一个参数是根节点，第二个参数是存储的数组，将结果存储在数组中
  28. {
  29.     if(root==NULL)//如果节点为空的话，那么我们就不需要保存当前节点的值
  30.     {
  31.         return;
  32.     }
  33.     //走到这里说明当前节点不为空，那么我们将当前节点的值保存在数组中
  34.  
  35.     //题目中说的是前序遍历，那么就是根左右
  36.     arr[(*pi)++]=root->val;
  37.     _preorderTraversal(root->left,arr,pi);
  38.     _preorderTraversal(root->right,arr,pi);
  39.  
  40. }
  41.  
  42. int* preorderTraversal(struct TreeNode* root, int* returnSize)
  43. {
  44.     //第一步：先求出二叉树节点的个数
  45.     //将节点个数放到* returnSize里面
  46.     * returnSize=TreeSize(root);
  47.     //第二步：动态申请内存--arr的大小
  48.     //这个数组存放二叉树内节点的值
  49.     int*returnArr=(int*)malloc(sizeof(int)*(* returnSize));
  50.     int i=0;
  51.     _preorderTraversal(root,returnArr,&i);
  52.  
  53.     return returnArr;
  54. }
  55. /*
  56. 我们需要先知道二叉树节点的个数
  57. 知道节点个数之后我们进行数组的动态内存的开辟
  58.  
  59. 然后我们又创建了一个函数专门进行递归，将节点中的数据存储在数组中
  60. 在这个函数中，我们传过去的有根节点，数组，还有i的地址
  61.  
  62. 在函数内，如果节点为空的话，那么我们直接返回
  63.  
  64. 然后我们进行数组内元素的赋值
  65. 我们利用传的指针作为下标
  66. 为什么i要传地址呢？
  67. 因为我们的i作为下标要一直进行++
  68. 如果不传地址的话，传值的话，那么对于这个函数内的两个递归
  69. 进行完左递归之后我们的i是不会有变化的
  70. 所以我们要进行传地址操作
  71.  
  72. 我们将节点数值依次放到数组中,*pi一直在++操作，下标一直在变化
  73.  
  74. 我们先遍历左子树的值，再遍历右子树的值，那么i就要一直进行变化；
  75. 最后我们还要返回数组的地址
  76.  
  77. */

6.二叉树的中序遍历

  1. typedef struct TreeNode TreeNode;
  2.  
  3. int TreeSize(TreeNode* root) {
  4.     if (root == NULL) {
  5.         return 0;
  6.     }
  7.     return 1 + TreeSize(root->left) + TreeSize(root->right);
  8. }
  9.  
  10. void _inorderTraversal(TreeNode* root, int *arr, int* pi) {
  11.     if (root == NULL) {
  12.         return;
  13.     }
  14.     _inorderTraversal(root->left, arr, pi); // 先遍历左子树
  15.     arr[(*pi)++] = root->val; // 访问根节点
  16.     _inorderTraversal(root->right, arr, pi); // 再遍历右子树
  17. }
  18.  
  19. int* inorderTraversal(struct TreeNode* root, int* returnSize) {
  20.     *returnSize = TreeSize(root);//求节点个数
  21.     int* returnArr = (int*)malloc(sizeof(int) * (*returnSize));//开辟空间
  22.     int i = 0;
  23.     _inorderTraversal(root, returnArr, &i);//递归函数
  24.     return returnArr;//返回存储数据的数组的指针
  25. }

7.二叉树的后续遍历

  1. typedef struct TreeNode TreeNode;
  2.  
  3. int TreeSize(TreeNode* root) {
  4.     if (root == NULL) {
  5.         return 0;
  6.     }
  7.     return 1 + TreeSize(root->left) + TreeSize(root->right);
  8. }
  9.  
  10. void _inorderTraversal(TreeNode* root, int *arr, int* pi) {
  11.     if (root == NULL) {
  12.         return;
  13.     }
  14.     _inorderTraversal(root->left, arr, pi); // 先遍历左子树
  15.  
  16.     _inorderTraversal(root->right, arr, pi); // 再遍历右子树
  17.     arr[(*pi)++] = root->val; // 访问根节点
  18. }
  19.  
  20. int* postorderTraversal(struct TreeNode* root, int* returnSize) {
  21.     *returnSize = TreeSize(root);//求节点个数
  22.     int* returnArr = (int*)malloc(sizeof(int) * (*returnSize));//开辟空间
  23.     int i = 0;
  24.     _inorderTraversal(root, returnArr, &i);//递归函数
  25.     return returnArr;//返回存储数据的数组的指针
  26. }

8.二叉树的构建以及遍历

 

  1. #include <stdio.h>
  2. /*
  3. 读取用户输入，保存在数组中，这个字符串的内容刚好是二叉树的前序遍历
  4.  
  5. 我们根据这个前序遍历的结果来创建二叉树
  6.  
  7. 再对二叉树进行中序遍历，输出中序遍历的结果
  8. */
  9. /*
  10. abc##de#g##f###
  11. 对于这个字符串，c是b的左子树，b是a的左子树
  12. */
  13.  
  14.  
  15. /*
  16. 若遍历中没有给出NULL节点的情况，是不能根据某一个遍历来创建二叉树的
  17.  
  18.  
  19. */
  20. typedef struct BinaryTreeNode//定义二叉树节点结构类型
  21. {
  22.     char data;
  23.     struct BinaryTreeNode*left;
  24.     struct BinaryTreeNode*right;
  25.  
  26. }BTNode;
  27.  
  28. BTNode*buyNode(char x)//创建节点
  29. {
  30.     BTNode*newnode=(BTNode*)malloc(sizeof(BTNode));
  31.     newnode->data=x;
  32.     newnode->left=newnode->right=NULL;
  33.  
  34.     return newnode;
  35. }
  36.  
  37. BTNode*createTree(char*arr,int*pi)//创建二叉树，返回根节点,第一个参数是字符串，第二个参数是下标
  38. {
  39.     if(arr[*pi]=='#')
  40.     {
  41.         (*pi)++;//不要忘了往后面接着走
  42.         return NULL;
  43.     }
  44.     BTNode*root=buyNode(arr[(*pi)++]);//将数组中的数据存储在二叉树中，将数组中的数据传到二叉树节点内
  45.     root->left=createTree(arr,pi); //然后进行二叉树左节点的创建
  46.     root->right=createTree(arr,pi); //二叉树右节点的创建
  47.  
  48.     return root;//返回根节点
  49. }
  50. void InOeder(BTNode*root)
  51. {
  52.     if(root==NULL)
  53.     {
  54.         return;
  55.     }
  56.     InOeder(root->left);//递归左子树
  57.     printf("%c ",root->data);//打印根节点
  58.     InOeder(root->right);//递归右子树
  59.  
  60. }
  61. int main()
  62. {
  63.     //读取用户输入的字符串保存在字符数组中
  64.     char arr[100];
  65.     scanf("%s",arr);
  66.  
  67.     //根据字符串（前序遍历）创建二叉树
  68.     int i=0;
  69.     BTNode*root=createTree(arr,&i);
  70. //这里的root是创建的二叉树的根节点
  71.     //输出二叉树的中序遍历
  72.     InOeder(root);
  73.     return 0;
  74. }
  75. /*
  76. 当pi=0时，我们创建了根节点a，然后创建a的左子树
  77. 然后pi指向b，然后创建了根节点b，然后pi++,pi指向c，
  78. 创建了根节点c,然后pi++,pi指向了#，为空，那么我们就return 了
  79. 然后创建c的右子树
  80. 那么pi++指向了#，那么就是空
  81. 那么就返回，回到了b这颗树，那么b的左子树就创建完成，那么就进行b的右子树的创建了
  82. pi++指向了d,那么我们创建根节点d,然后pi++指向e，然后我们创建b的左节点e
  83. pi++,指向#，所以为空，那么我们就返回了，进行e的右节点的创建
  84. pi++指向了g，创建了根节点g pi++,指向了# 所以我们在创建g的左节点的时候返回了
  85. 那么我们就创建g的右节点
  86. pi++指向了#，所以为空，那么我们就返回了。返回到d,d的左子树已经创建好了
  87. 那么我们就创建d的右子树
  88. pi++指向了f
  89. 我们创建根节点f
  90. 然后pi++,指向#，创建f的左节点，因为为空，所以我们返回，然后创建f的右节点，，Pi++,指向了#，为空，那么我们就返回了
  91. 那么d的左右子树都已经创建完成了
  92. 那么我们就返回到a了
  93. 在a这棵树里面，a的左子树b已经创建好了
  94. 那么我们就进行a的右子树的创建了
  95. pi++,指向了#，那么为空，我们就返回
  96. 到这里，a这颗二叉树就创建好了
  97.  
  98.  
  99. */

可以参考这个图片里面的二叉树

6.二叉树选择题

 

证明上述性质：假设⼀个⼆叉树有 a 个度为2的节点， b 个度为1的节点， c 个叶节点，则这个⼆叉树的边数是2a+b

另⼀⽅⾯，由于共有 a+b+c 个节点，所以边数等于 a+b+c-1

结合上⾯两个公式：

2a+b = a+b+c-1 ，即： a = c-1

就是度为2节点的个数等于叶子节点的个数-1

二叉树性质的题目：

  1. 某⼆叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该⼆叉树中的叶⼦结点数为（B ）

A 不存在这样的⼆叉树

B 200 叶子节点的个数=节点数为2的节点的个数+1 n0=n2+1

C 198

D 199

2.在具有 2n 个结点的完全⼆叉树中，叶⼦结点个数为（A ）

A n n0+n1+n2=2N 因为n0=n2+1 所以n0+n1+n0-1=2n0+n1-1=2N

B n+1 完全二叉树中有多少个度为1的节点呢？度为1的节点只可能为1个或者是0个

C n-1 那么我们带进去的话，当节点为0的时候，算出来的是小数，节点是1的时候，那么得

D n/2 到的就是n

3.⼀棵完全⼆叉树的结点数位为531个，那么这棵树的⾼度为（ ）

A 11

B 10 2^h-1=531 那么得到的h=log532 那么得到的只能是10层，9层是不够的

C 8

D 12

4.⼀个具有767个结点的完全⼆叉树，其叶⼦结点个数为（B）

A 383

B 384

C 385

D 386

这个题和第二题是差不多的

2n0+n1-1=767

n1只有1和0两种可能

那么我们得到的n0=384

二叉树遍历题目

1.某完全⼆叉树按层次输出（同⼀层从左到右）的序列为 ABCDEFGH 。该完全⼆叉树的前序序列为（A）

A ABDHECFG

B ABCDEFGH

C HDBEAFCG

D HDEBFGCA

2.⼆叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则⼆叉树根结点为（A）

A E

B F

C G

D H

3.设⼀课⼆叉树的中序遍历序列：badce，后序遍历序列：bdeca，则⼆叉树前序遍历序列为D。

A adbce 后序遍历的根节点肯定在最后面，那么a肯定是根节点，a的左节点是b,

B decab 根据后续遍历我们知道a的右节点是c

C debac 那么结合中序遍历来说，d是c的左子树，e是c的右子树

D abcde

4.某⼆叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同⼀层从左到右）的序列为（A）

A FEDCBA

B CBAFED

C DEFCBA

D ABCDEF

从后序遍历我们知道根节点是F

但是中序遍历中F在最后，那么说明F没有右子树，只有左子树

从中序遍历和后序遍历我们能知道E是F的左节点

E的左子树是D，D的左子树是C，C的左子树是B，B的左子树是A

那么最后的图形就是一根直线，最下面的是A

根据题目问题，那么最后得到的就是A

证明上述性质：假设⼀个⼆叉树有 a 个度为2的节点， b 个度为1的节点， c 个叶节点，则这个⼆叉树的边数是2a+b

另⼀⽅⾯，由于共有 a+b+c 个节点，所以边数等于 a+b+c-1

结合上⾯两个公式：

2a+b = a+b+c-1 ，即： a = c-1

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/人工智能uu/article/detail/952644
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号