当前位置:   article > 正文

二叉树的基础应用_二叉树应用到实际问题

二叉树应用到实际问题

二叉树

  1. 树概念及结构

1.1树的概念

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

有一个特殊的结点,称为根结点,根节点没有前驱结点

除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继

因此,树是递归定义的。

 1.2树的相关概念

节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6

叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点

非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等节点为分支节点

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点

兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点

树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度或深度:树中节点的最大层次; 如上图:树的高度为4

堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点

节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙

森林:由m(m>0)棵互不相交的树的集合称为森林;

注:子树是不相交的,除根结外,每个结点有且仅有一个父节点,一棵N个结点的树有N-1条边。

  1. 3树的表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间 的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的孩子兄弟表示法(左孩子右兄弟)

  1. typedef int DataType;
  2. struct Node
  3. {
  4. struct Node* _firstChild1; // 第一个孩子结点
  5. struct Node* _pNextBrother; // 指向其下一个兄弟结点
  6. DataType _data; // 结点中的数据域
  7. };

1.4树在实际中的应用

文件系统就是树在实际生活中的应用

2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合,该集合:

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

3 特殊的二叉树:

1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是 说,如果一个二叉树的层数为K,且结点总数是 ,则它就是满二叉树。

2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K 的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树

堆排序—时间复杂度O(N*logN)

Topk---类似点外卖,想吃最好吃的饭,需要在n个里面排序排除最好的。

 

满二叉树就是一个等比数列,从2^0+………+2^(n-1);

等于2^n-1;,

完全二叉树度为1的至多只有1个,高度为h的二叉树,节点范围是2^h-1,(满二叉树可以认为是一个特殊的完全二叉树),高度为h的完全二叉树,节点范围是[2^(h-1),2^h-1]

前h-1的节点个数(前h-1)是满二叉树,计算得2^(h-1)-1,下一层至少有一个节点,所以最小值是2^(h-1)-1+1=2^(h-1);

4 二叉树的性质

1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h-1 .

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有n0 = n2+1

4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log2(n+1) . (ps:log2(n+1) 是log以2 为底,n+1为对数)

5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:

1. 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点

2. 若2i+1=n否则无左孩子

3. 若2i+2=n否则无右孩子

5.二叉树的存储结构

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。

  1. 顺序存储

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空 间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的章节会专门讲解。二叉树顺 序存储在物理上是一个数组,在逻辑上是一颗二叉树。

下标计算父子间的关系:leftchilid=parent*2+1;rightchild=parent*2+2;

Parent=(chilid-1)/2,右孩子是偶数,左孩子是奇数,右孩子减2左孩子减1.对于偶数说-1除2跟-2除2来说得到的结果是相同的,可以看出右孩子-1/2也可以得到,所以把他们的计算形式给统一了一下。

以上的仅时候满二叉树和完全二叉树。非完全二叉树不是不可以拿数组存而是不合适。

2 堆的概念及结构

如果有一个关键码的集合K = { k0,k1 ,k2 ,…,kn-1 },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:ki<=k2*i+1  且 ki<=k2*i+2 (ki >=k2*i+1 且 ki>=k2*i+2 ) i = 0,1, 2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质: 堆中某个节点的值总是不大于或不小于其父节点的值;

堆总是一棵完全二叉树。

 

 堆算法的实现

  1. Heap.h
  2. #pragma once
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<stdbool.h>
  6. #include<assert.h>
  7. typedef int HeapDataType;
  8. typedef struct Heap
  9. {
  10. HeapDataType* array;
  11. int size;
  12. int capicity;
  13. }Heap;
  14. void HeapInit(Heap* p);//初始化
  15. void HeapDestory(Heap* p);//销毁堆
  16. void HeapPush(Heap* p,HeapDataType x);//插入
  17. void HeapPop(Heap* p);//删除
  18. HeapDataType HeapTop(Heap* p);//取堆顶
  19. bool HeapEmpty(Heap* p);//堆是否为空
  20. int HeapSize(Heap* p);//堆的大小
  21. void HeapPrint(Heap* p);//打印堆
  22. void AdjustUp(HeapDataType* a, int child);//向上调整
  23. void AdjustDown(HeapDataType* a, int size, int parent);//向下调整
  24. void HeapSort(HeapDataType* a, int n);//堆排序
  1. Heap.c
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3. #include"Heap.h"
  4. //大堆小堆能做到的是大堆堆顶是最大的,小堆堆顶是最小的,可以用来选数
  5. void HeapInit(Heap* p)
  6. {
  7. assert(p);
  8. p->array = NULL;
  9. p->capicity = p->size = 0;
  10. }
  11. void HeapDestory(Heap* p)
  12. {
  13. assert(p);
  14. free(p->array);
  15. p->array = NULL;
  16. p->capicity = p->size = 0;
  17. }
  18. void Swap(HeapDataType* p1, HeapDataType* p2)
  19. {
  20. HeapDataType tmp = *p1;
  21. *p1 = *p2;
  22. *p2 = tmp;
  23. }
  24. void AdjustUp(HeapDataType* a, int child)//从孩子的位置向上调整(父亲小于等于孩子)
  25. {
  26. int parent = (child - 1 )/ 2;
  27. while (child>0)//最坏是一路调整到根
  28. {
  29. //if (a[child] < a[parent])//(小根堆条件)
  30. if (a[child] > a[parent])//(大根堆条件)
  31. {
  32. Swap(&a[child], &a[parent]);
  33. child = parent;
  34. parent = (child-1)/2;
  35. }
  36. else
  37. {
  38. break;
  39. }
  40. }
  41. }
  42. void HeapPush(Heap* p, HeapDataType x)
  43. {
  44. assert(p);
  45. if(p->capicity==p->size)
  46. {
  47. int newcapicity = p->capicity == 0 ? 4 : 2 * p->capicity;
  48. HeapDataType* tmp = (HeapDataType*)realloc(p->array, newcapicity*sizeof(HeapDataType));
  49. if (tmp == NULL)
  50. {
  51. perror("realloc");
  52. exit(-1);
  53. }
  54. p->array = tmp;
  55. p->capicity = newcapicity;
  56. }
  57. p->array[p->size] = x;
  58. p->size++;
  59. AdjustUp(p->array, p->size - 1);
  60. }
  61. void HeapPrint(Heap* p)
  62. {
  63. for (int i = 0; i < p->size; i++)
  64. {
  65. printf("%d ", p->array[i]);
  66. }
  67. printf("\n");
  68. }
  69. void AdjustDown(HeapDataType*a, int size, int parent)//小堆排序都用的小于号,到时需要大堆排序只需要改成大于号
  70. {
  71. //至少满足左子树是小堆,右子树是小堆才能向下调整
  72. //选出左右孩子小的一个
  73. //小的跟父亲比较,如果比父亲要小则交换,继续向下调整
  74. //如果比父亲大则调整结束
  75. //最多调整到叶子节点就结束了
  76. int child = parent * 2 + 1;
  77. while (child<size)//默认循环开始child都是左孩子
  78. {
  79. //选出左右孩子小的内一个
  80. //if (child+1<size&&a[child + 1] < a[child])//左孩子存在右孩子不一定存在(小根堆条件)
  81. if (child + 1 < size && a[child + 1] > a[child])//(大根堆条件)
  82. {
  83. ++child;//默认指向小的孩子,先是指向左孩子,如果右孩子小于左孩子,++右孩子,
  84. //如果右孩子大于左孩子,默认在左孩子上
  85. }
  86. //这里child一定的小的那个孩子,至于是左孩子还是右孩子是不需要关心的
  87. //孩子跟父亲比较
  88. //if (a[child] < a[parent])//(小根堆条件)
  89. if (a[child] > a[parent])//(大根堆条件)
  90. {
  91. Swap(&a[child], &a[parent]);
  92. parent = child;
  93. child = parent*2+1;
  94. }
  95. else
  96. {
  97. break;
  98. }
  99. }
  100. }
  101. void HeapPop(Heap* p)//最优的是将首尾调换,将尾删去,删除其他位置的数是没有价值的(只删除堆顶的值)
  102. {
  103. assert(p);
  104. assert(p->size > 0);
  105. Swap(&(p->array[0]), &(p->array[p->size - 1]));
  106. p->size--;
  107. AdjustDown(p->array, p->size, 0);//删除的时候parent是0,向下删除,parent不一定是从0开始的,所以保留了这个接口
  108. }
  109. HeapDataType HeapTop(Heap* p)
  110. {
  111. assert(p);
  112. assert(p->size > 0);
  113. return p->array[0];
  114. }
  115. bool HeapEmpty(Heap* p)
  116. {
  117. assert(p);
  118. return p->size == 0;//等于0就是空,不等于0就不为空
  119. }
  120. int HeapSize(Heap* p)
  121. {
  122. assert(p);
  123. return p->size;
  124. }
  125. //真正的堆排序不需要堆的数据结构
  126. void HeapSort(int *a,int n)
  127. {
  128. //{27151918283465492537};
  129. // 27
  130. // 15 19
  131. // 18 28 34 65
  132. // 49 25 37
  133. //我们将传入的数组看成是二叉树,但是此时并不是堆,因为没有排序。
  134. 建堆(向上插入帮助我们建堆)
  135. 相当于第0个位置不动,第一个位置开始插入就行,每次插入都相当于是一次向上调整
  136. //for (int i = 1; i < n; i++)
  137. //{
  138. // AdjustUp(a, i);
  139. //}
  140. 相当于一次插入的过程
  141. //建堆
  142. //向下调整要求左子树是堆,右子树也是堆,但现在排序的数组左右子树不是堆
  143. //从倒数第一个非叶子节点开始调整,叶子节点不需要调。(也就是从28开始调)
  144. //孩子比父亲大就换(3728比较,将3728换,4918调换,65194915至此左子树就调整完成)
  145. // // 27
  146. // 49 65
  147. // 15 37 34 19
  148. // 18 25 18
  149. //28这个位置下标怎么计算:28是最后一个节点的父亲。
  150. for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  151. //最后一个节点:n-1,算父亲再-1除以2
  152. {
  153. AdjustDown(a, n, i);
  154. }//这里的i=n-1,这样写也可以,从最后一个数开始调整,只不过比上面多走了几次
  155. //堆向上向下调整的次数,在完全二叉树下是数的高度,logN
  156. //两个分别建堆的时间复杂度是:方式1:O(N*logN),方式2:O(N)
  157. //第二个建堆的方法要更好一些
  158. //升序的话,如果构建小根堆选择最小的,之后还得选择次小的,但是这时的关系全部乱了,需要继续新的建堆
  159. //每次的时间复杂度是O(N^2)跟遍历一遍数组选出最小的一样,没有体现出堆的特性
  160. //升序要建大堆,选出最大的数,把最大的数跟末尾的数交换,如同堆删除的思路
  161. //之前是N个数现在可以看成是N-1个数(不看尾的数)这时不看第一个数,左子树跟右子树依旧是大堆
  162. //要选出次大的数,向下调整一次就可以,时间复杂度是logN
  163. //有N-1个数要选择,就要选N*logN次,对比之前建小堆或者直接遍历的O(N^2)比如一千个数,大堆才十次
  164. int end = n - 1;
  165. while (end>0)
  166. {
  167. Swap(&a[0], &a[end]);
  168. AdjustDown(a, end, 0);//只有n-1个数选出最大的
  169. end--;
  170. }
  171. //整体的时间复杂度:O(N*logN)
  172. }
  1. Test.c
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3. #include"Heap.h"
  4. void TestHeapPush()
  5. {
  6. Heap hp1;
  7. HeapInit(&hp1);
  8. int a[] = { 27,15,19,18,28,34,65,49,25,37 };
  9. int sz = sizeof(a) / sizeof(a[0]);
  10. for (int i = 0; i < sz; i++)
  11. {
  12. HeapPush(&hp1, a[i]);
  13. }
  14. HeapPrint(&hp1);
  15. HeapPush(&hp1, 10);
  16. HeapPrint(&hp1);
  17. }
  18. void TestHeapPop()
  19. {
  20. Heap hp1;
  21. HeapInit(&hp1);
  22. int a[] = { 27,15,19,18,28,34,65,49,25,37 };
  23. int sz = sizeof(a) / sizeof(a[0]);
  24. for (int i = 0; i < sz; i++)
  25. {
  26. HeapPush(&hp1, a[i]);
  27. }
  28. HeapPrint(&hp1);
  29. HeapPop(&hp1, 27);
  30. HeapPrint(&hp1);
  31. HeapPop(&hp1);
  32. HeapPrint(&hp1);
  33. }
  34. //这里的堆排序有两个问题
  35. //1.你得先写一个堆的数据结构,反而复杂
  36. //2.有O(n)的空间复杂度
  37. void TestHeapSort()//堆排序
  38. {
  39. //升序打印
  40. Heap hp1;
  41. HeapInit(&hp1);
  42. int a[] = { 27,15,19,18,28,34,65,49,25,37 };
  43. int sz = sizeof(a) / sizeof(a[0]);
  44. for (int i = 0; i < sz; i++)
  45. {
  46. HeapPush(&hp1, a[i]);
  47. }
  48. while (!HeapEmpty(&hp1))
  49. {
  50. printf("%d ", HeapTop(&hp1));
  51. HeapPop(&hp1);
  52. }
  53. //每次只取堆顶的,堆顶就是最小的,循环直到结束会得到升序的数
  54. HeapDestory(&hp1);
  55. }
  56. int main()
  57. {
  58. //TestHeapPush();
  59. //TestHeapPop();
  60. //TestHeapSort();
  61. int a[] = { 27,15,19,18,28,34,65,49,25,37 };
  62. HeapSort(a, sizeof(a) / sizeof(int));
  63. for (int i = 0; i < sizeof(a) / sizeof(int); i++)
  64. {
  65. printf("%d ", a[i]);
  66. }
  67. return 0;
  68. }

向下调整:

越上面的节点少调整次数多,越下面的节点多调整次数少

调整的次数=总节点的个数×这一层调整的次数

T(n)=2^0* (h -1)+2^1*(h -2)+2^2*(h-3)+2^3*(h -4)+...+2^(h-3)*2+2^(h-2)* 1①

2*T(n)=2^1* (h -1)+2^2*(h -2)+2^3*(h-3)+2^4*(h -4)+...+2^(h-2)*2+2^(h-1)* 1②

因此:建堆的时间复杂度为O(N)

向上调整要最后一层,向下调整不需要最后一层,从倒数第二层开始

最后一层有2^(h-1)个节点,最坏调整h-1次

T(N)=2^1*1+2^2*2+2^3*3+………….+2^(h-2)*(h-2)+2^(h-1)*(h-1)

继续用错位相减

T(N)=N*logN

TOP-K问题(N个数中找最大的/最小的前k个,N是远大于K)

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。

比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:

找最大的前k个

  1. 堆排序(N*logN)
  2. 建N个数的大堆,Top/Pop K次 时间复杂度是O(N+logN*K)(向下建堆是O(N),向上建堆是O(N*logN),选向下) (建立N个数的堆用向下建堆,之后Pop K次,首尾互换,把尾给换掉向下调整,调整logN次,总共调整K次,是logN*K次)
  3. 假设N非常大,比如N是100亿,K比较小,K是100,如何求解?

问题是内存存不下这么大的数,所以1跟2方法都不适合,堆无非建立起来。

将k个数当作堆建立起来,K比较小,前k个数建立一个小堆,这里跟堆排序的思路比较类似有点反过来的感觉,排降序用的是小堆。1> 用数据集合中前K个元素来建堆,前k个最大的元素,则建小堆 ;前k个最小的元素,则建大堆

2>用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

例如排降序:1.前k个数先建立小堆 2.剩下的N-K个依次跟堆顶数据比较,如果比堆顶数据大,则替换堆顶数据进堆,走完之后,堆里面的数就是最大的前K个。如果建大堆只能选最大的那一个数,不能选最大的前k个数。

它的时间复杂度是O(k+(N-k)*logK)这个在时间效率并没有太快于第二个算法的时间,但是在内存空间上,2是需要建立很大的大堆,它的空间复杂度是k只需要开辟k个这么大的空间建堆

  1. //这里的堆排序有两个问题
  2. //1.你得先写一个堆的数据结构,反而复杂
  3. //2.有O(n)的空间复杂度
  4. void TestHeapSort()//堆排序
  5. {
  6. //升序打印
  7. Heap hp1;
  8. HeapInit(&hp1);
  9. int a[] = { 27,15,19,18,28,34,65,49,25,37 };
  10. int sz = sizeof(a) / sizeof(a[0]);
  11. for (int i = 0; i < sz; i++)
  12. {
  13. HeapPush(&hp1, a[i]);
  14. }
  15. while (!HeapEmpty(&hp1))
  16. {
  17. printf("%d ", HeapTop(&hp1));
  18. HeapPop(&hp1);
  19. }
  20. //每次只取堆顶的,堆顶就是最小的,循环直到结束会得到升序的数
  21. HeapDestory(&hp1);
  22. }
  23. //不需要用自己堆的数据结构
  24. void PrintTopK(int* a, int n, int k)
  25. {
  26. int* KMinHeap = malloc(sizeof(int) * k);
  27. assert(KMinHeap);
  28. for (int i = 0; i < k; ++i)
  29. {
  30. KMinHeap[i] = a[i];
  31. }
  32. // 1. 建堆--用a中前k个元素建堆(最后一个非叶子节点的下标开始建堆)
  33. for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  34. {
  35. AdjustDown(KMinHeap, k, i);
  36. }
  37. // 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换(遍历剩下的n-k个数)
  38. for (int j = k; j < n; j++)
  39. {
  40. if (a[j] > KMinHeap[0])
  41. {
  42. KMinHeap[0] = a[j];
  43. AdjustDown(KMinHeap, k, 0);
  44. }
  45. }
  46. //最后的堆里面的数就是最大的前k个数
  47. for (int i = 0; i < k; i++)
  48. {
  49. printf("%d ", KMinHeap[i]);
  50. }
  51. printf("\n");
  52. }
  53. void TestTopk()
  54. {
  55. int n = 10000;
  56. int* a = (int*)malloc(sizeof(int) * n);
  57. srand(time(0));
  58. for (int i = 0; i < n; ++i)
  59. {
  60. a[i] = rand() % 1000000;//每个数都小于100 0000
  61. }
  62. //给十个大于100 0000的数
  63. //最后如果打印出十个下面比100 0000大的数说明程序就ok
  64. a[5] = 1000000 + 1;
  65. a[1231] = 1000000 + 2;
  66. a[531] = 1000000 + 3;
  67. a[5121] = 1000000 + 4;
  68. a[115] = 1000000 + 5;
  69. a[2335] = 1000000 + 6;
  70. a[9999] = 1000000 + 7;
  71. a[76] = 1000000 + 8;
  72. a[423] = 1000000 + 9;
  73. a[3144] = 1000000 + 10;
  74. PrintTopK(a, n, 10);//10000个数据里面找10个最大的
  75. }

链式二叉树:

如果是完全二叉树或者满二叉树,用数组的方式可以表示,如果不是完全二叉树或者满二叉树数组无非很好的表示,链式的二叉树是更合适的。链式的这种普通二叉树的增删查改没有意义。存储数据的话不如用顺序表和链表,学习它的意义:1.为我们后续学习更复杂的二叉树打好基础。(搜素二叉树,AVL树,红黑树,B树….)

学习遍历或者控制结构

二叉树的遍历

前序、中序以及后序遍历

学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉 树中的节点进行相应的操作,并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历 是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。

按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:

任何一个树都要被分为根 左子树 右子树

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 (根 左子树 右子树)

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。

(左子树 根 右子树)

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。(左子树 右子树 根)

#:表示NULL

前序遍历结果:1 2 3 # # # 4 5 # # 6 # #(根 左 右)

中序遍历结果:# 3 # 2 # 1 # 5 # 4 # 6 #(左 根 右)

后序遍历结果:# # 3 # 2 # 5 # # 6 4 1  (左 右 根)

  1. typedef int BTDataType;
  2. typedef struct BinaryTreeNode
  3. {
  4. struct BinaryTreeNode* left;
  5. struct BinaryTreeNode* right;
  6. BTDataType data;
  7. }BTNode;
  8. BTNode* BuyNode(BTDataType x)
  9. {
  10. BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  11. assert(node);
  12. node->data = x;
  13. node->left = node->right = NULL;
  14. return node;
  15. }
  16. BTNode* CreatBinaryTree()
  17. {
  18. BTNode* node1 = BuyNode(1);
  19. BTNode* node2 = BuyNode(2);
  20. BTNode* node3 = BuyNode(3);
  21. BTNode* node4 = BuyNode(4);
  22. BTNode* node5 = BuyNode(5);
  23. BTNode* node6 = BuyNode(6);
  24. node1->left = node2;
  25. node1->right = node4;
  26. node2->left = node3;
  27. node4->left = node5;
  28. node4->right = node6;
  29. return node1;
  30. }
  31. void PreOrder(BTNode*root)//前序
  32. {
  33. if (root == NULL)
  34. {
  35. printf("# ");
  36. return;
  37. }
  38. printf("%d ", root->data);
  39. PreOrder(root->left);
  40. PreOrder(root->right);
  41. }
  42. void InOrder(BTNode* root)//中序
  43. {
  44. if (root == NULL)
  45. {
  46. printf("# ");
  47. return;
  48. }
  49. InOrder(root->left);
  50. printf("%d ", root->data);
  51. InOrder(root->right);
  52. }
  53. void PostOrder(BTNode* root)//后序
  54. {
  55. if (root == NULL)
  56. {
  57. printf("# ");
  58. return;
  59. }
  60. PostOrder(root->left);
  61. PostOrder(root->right);
  62. printf("%d ", root->data);
  63. }
  64. int main()
  65. {
  66. BTNode* root = CreatBinaryTree();
  67. PreOrder(root);
  68. printf("\n");
  69. InOrder(root);
  70. printf("\n");
  71. PostOrder(root);
  72. printf("\n");
  73. return 0;
  74. }

与上面我们分析结果相同;我们创造了这样一个树

这里用到了分治算法(二分查找也用到了这个算法)

分而治之,把大问题分成类似规模的小问题,这里可以用递归写;

第一次传入是1这个节点的地址(用1代表),1不是NULL,打印1,之后访问左子树,递归1的左子树,往下递归,2不是NULL再向下递归,先访问2这个子树,2继续访问左子树是3,3的左子树是NULL,打印#,并且返回,返回到上一个递归的3调用的函数中应该是右子树,3的右子树为NULL,则继续打印#,回到它调用的地方,是2左调用的,之后回到2访问右子树,2 的右子树是NULL,打印#,回到1,访问1的右树,下来是4,打印4,之后访问左子树是5,5的左子树是NULL,访问5的右子树是NULL,访问6的左子树是NULL最后访问6的右子树为NULL;最后递归结束。从物理上来看是建立栈帧;栈帧结束回到上一层栈帧;

最开始传入的是根,根节点是1,1不是NULL,遇到1 不能访问先递归走它的左子树,遇到2不能访问继续走它的左树,到3,3的左边是NULL打印#,return回去(一个函数调用完无论是return回去还是正常的执行结束都是回到调用的地方)下一个打印3,递归到3的右树,打印#,return回到上一层,上一层的左树已经调用完了直接就到了第二步打印,回到了2,访问2的右树,右树为NULL打印#,回到1,打印1,继续走1的右树,访问4,4不是NULL走4的左……直到访问完到底。

后序跟前面相同;

下面是计算二叉树存了多少个数

//遍历的思路

  1. int count=0 ;
  2. int TreeSize(BTNode*root)//求二叉树中存了多少个数据
  3. {
  4. //这里的计数不能像链表里面的计数一样放在函数里面
  5. //链表的计数是迭代,这里的递归不能这样,每个栈帧都有一个计数的count
  6. //int count=0
  7. if (root == NULL)
  8. {
  9. return;
  10. }
  11. ++count;
  12. TreeSize(root->left);
  13. TreeSize(root->right);
  14. }
  15. 注意在每次调用的时候要把count=0;(局部变量)置空一下;
  16. 这里如果多线程的时候可能同时用这个函数,同时计数可能会混,这个count会多个一起计数,全局可见的
  17. //分治的思路
  18. int TreeSize2(BTNode* root)
  19. {
  20. return root == NULL ? 0 : TreeSize2(root->left) + TreeSize2(root->right)+1;
  21. //+1是因为我们计数的时候把数分成3部分,左子树 自己 右子树
  22. }
  23. 这样调用多次也不需要每次把count置成0
  24. int TreeLeafSize(BTNode* root)//求叶子结点(根为0的才是叶子)
  25. {
  26. if (root == NULL)
  27. {
  28. return 0;
  29. }
  30. if ((root->left == NULL) && (root->right == NULL))
  31. {
  32. return 1;
  33. }
  34. //NULL返回0个,是叶子返回1个,不是NULL也不是叶子结点转换左子树叶子节点+右子树叶子节点
  35. return TreeLeafSize(root->left) + TreeLeafSize(root->right);
  36. }
  37. //继续用分治的想法把大问题分成小问题;
  38. //换成子问题:求第k层,看成是求左子树的第k-1+求右子树的第k-1
  39. int TreeKLevel(BTNode* root, int k)//求第k层的节点
  40. {
  41. assert(k >= 1);
  42. if (root == NULL)
  43. {
  44. return 0;
  45. }
  46. if (k == 1)
  47. {
  48. return 1;
  49. }
  50. return TreeKLevel(root->right, k - 1) + TreeKLevel(root->left, k - 1);
  51. }
  52. //二叉树查找值为x的结点
  53. BTNode* TreeFind(BTNode* root ,BTDataType x)
  54. {
  55. if (root == NULL)
  56. {
  57. return NULL;
  58. }
  59. if (root->data == x)
  60. {
  61. return root;
  62. }
  63. BTNode* ret1 = TreeFind(root->left, x);
  64. if (ret1)
  65. {
  66. return ret1;
  67. }
  68. BTNode* ret2 = TreeFind(root->right, x);
  69. if (ret2)
  70. {
  71. return ret2;
  72. }
  73. return NULL;
  74. }

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

闽ICP备14008679号