当前位置:   article > 正文

C语言描述数据结构 —— 二叉树(3)普通二叉树_c 二叉树

c 二叉树

1.完全二叉树与普通二叉树的对比

我们前面介绍过完全二叉树以及堆(一种完全二叉树),并且实现了堆用顺序结构存储的数据结构。还介绍了两个基本算法:向上调整算法、向下调整算法。在此基础上使用堆解决了 Top-K 问题,以及堆排序。我们通过完全二叉树的规律可以发现,完全二叉树如果不看最后一层,那么它是一棵满二叉树;最后一层的节点必须是上一层连续节点并且依次是左孩子、右孩子。那么现在要介绍的是普通二叉树。普通二叉树只满足二叉树的基本定义,它不满足完全二叉树的定义。那么普通二叉树的结构可能是下面这几种:

 可以发现普通二叉树的结构没有规律,如果用顺序结构存储的话那么物理空间不一定是连续的。

如果是这样,那么数据的存储就没有意义。我们可以试想一下,当我们真正进行数据存储的时候,我们会把数据不连续的存储起来吗?这样做的意义只有增加工作量、难度而已。 不单单是存储数据没有意义,就连删除也没有意义。我们想要访问二叉树的节点时候也是一个难题。所以普通二叉树我们一般使用链式结构,即用链表串联起来,需要注意,这样做的目的不是赋予它适合增删查改的能力,而是使用链式结构可以实现我们从来没有接触过的功能。例如二叉搜索树:

我们使用百科上面的例子做一个分析:

 当然我们现在是简单的举一些普通二叉树的应用,本篇介绍的目的是为了打好基础,做好铺垫,为以后的学习打下地基。 

2.二叉树的性质

我们实现过堆用顺序结构存储的数据结构,里面也涉及到了不少的二叉树性质。那么现在将详细介绍二叉树的性质。

        1.若规定根节点的层数为1,那么一颗非空二叉树的第k层最多有 2^(k-1) 个节点 

        2.若规定根节点的层数为1,那么深度(高度)为h的二叉树最多一共有 2^h-1 个节点 

         3.对任意一颗二叉树而言,如果度为2的节点个数为n2,度为0的节点个数为n0,那么有n0=n2+1

         4.如果规定根节点的层数为1,那么总共有n个节点的满二叉树的深度就为h=log(n+1)

对应这条性质的解释就是数学公式,总节点数为 2^h-1 ,在这个表达式上计算 h ,就用到了对数。

        5.在用顺序结构存储的完全二叉树中有下面几个规律:

                1.如果 child != 0 ,那么 parent = (child-1)/2 ;如果 child = 0,那么这个节点为根节点

                2.如果总节点个数为 n,假设 parent*2+1<n ,那么 parent*2+1 的值就是左孩子的下标

                3.如果总节点个数为 n,假设 parent*2+2<n ,那么 parent*2+2 的值就是右孩子的下标

这三条性质在我们实现堆的顺序结构的时候使用过,当然也是基于数学上得来的公式。

2.1二叉树性质有关练习

1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )
A 不存在这样的二叉树
B 200
C 198
D 199
答案: A 。根据公式 n0=n2+1 可知,度为 0 的节点个数比度为 2 的节点个数多一个。
2. 下列数据结构中,不适合采用顺序存储结构的是()
A 非完全二叉树
B
C 队列
D

答案:A。即使队列不推荐使用顺序结构存储,但即使使用,也比非完全二叉树效率高。

3. 在具有 2n 个结点的完全二叉树中,叶子结点个数为()
A n
B n+1
C n-1
D n/2
答案: A 。在二叉树中,节点的分类只有三种,即度为2的节点,度为1的节点和度为0的节点。那么表达式就为 2n = n2+n1+n0 ,又因为 n2=n0+1 ,所以 2n = 2n0-1+n1;又因为 2n 的结果只能是整数,所以 n1 必须等于 1。故n0 = n。
4. 一棵完全二叉树的节点数位为 531 个,那么这棵树的高度为()
A 11
B 10
C 8
D 12
答案: B 。完全二叉树的节点个数在 [2^(h-1),2^h-1] 这个区间内。那么将 10 带入这个表达式之中,那么区间就为 [512,1023] ,恰好 531 在这个区间之内,所以高度为 10。
5. 一个具有 767 个节点的完全二叉树,其叶子节点个数为()
A 383
B 384
C 385
D 386
答案: B 。n2+n1+n0=767,因为n2=n0+1,所以得 2n0-1+n1=767,即2n0+n1=768,因为 2n0 的结果必为偶数,所以n1必为0( 完全二叉树特性,度为1的节点个数要不为0要不为1 ),所以n0=384。

3.二叉树的递归遍历

我们再回顾一下二叉树的性质,我们提到过二叉树是递归定义的。

在任意一颗二叉树中,只有两种可能:要不为空;要不就为根节点、左子树和右子树组成。 

 了解了递归定义之后,我们就着手前序遍历、中序遍历和后序遍历。

  • 前序遍历,在每一颗树中,它的遍历顺序总为:根节点、左子树、右子树。
  • 中序遍历,在每一颗树中,它的遍历顺序总为:左子树、根节点、右子树。
  • 后序遍历,在每一颗树中,它的遍历顺序总为:左子树、右子树、根节点。

注意我的用词,在每一颗树中。每一颗树,相当于左子树是一棵树,左子树当中又分为根节点、左子树和右子树,左子树的左子树又是一颗树,它又分为根节点、左子树和右子树……

我们先画一下前序遍历的顺序图。

 就像这样层层递归,就可以完成遍历。那么中序遍历、后序遍历和前序遍历一样,那么这里的顺序图就省略了,我们直接看结果:

清楚了遍历顺序之后,就可以开始着手代码。这里注意,因为现在的部分是为了后续学习打基础,所以在这里手动构造与例子相同的二叉树。

  1. #include <stdlib.h>
  2. #include <assert.h>
  3. #include <stdio.h>
  4. typedef int BinaryData;
  5. typedef struct Node
  6. {
  7. BinaryData val;
  8. struct Node* left;
  9. struct Node* right;
  10. }Node;
  11. Node* CreateNode()
  12. {
  13. Node* n1 = (Node*)malloc(sizeof(Node));
  14. assert(n1);
  15. Node* n2 = (Node*)malloc(sizeof(Node));
  16. assert(n2);
  17. Node* n3 = (Node*)malloc(sizeof(Node));
  18. assert(n3);
  19. Node* n4 = (Node*)malloc(sizeof(Node));
  20. assert(n4);
  21. Node* n5 = (Node*)malloc(sizeof(Node));
  22. assert(n5);
  23. Node* n6 = (Node*)malloc(sizeof(Node));
  24. assert(n6);
  25. n1->val = 1;
  26. n2->val = 2;
  27. n3->val = 3;
  28. n4->val = 4;
  29. n5->val = 5;
  30. n6->val = 6;
  31. n1->left = n2;
  32. n1->right = n4;
  33. n2->left = n3;
  34. n2->right = NULL;
  35. n3->left = NULL;
  36. n3->right = NULL;
  37. n4->left = n5;
  38. n4->right = n6;
  39. n5->left = NULL;
  40. n5->right = NULL;
  41. n6->left = NULL;
  42. n6->right = NULL;
  43. return n1;
  44. }
  45. //前序遍历
  46. void PreTraval(Node* root)
  47. {
  48. if (root == NULL)
  49. {
  50. printf("NULL ");
  51. return;
  52. }
  53. printf("%d ", root->val);
  54. PreTraval(root->left);
  55. PreTraval(root->right);
  56. }
  57. //中序遍历
  58. void MidTraval(Node* root)
  59. {
  60. if (root == NULL)
  61. {
  62. printf("NULL ");
  63. return;
  64. }
  65. MidTraval(root->left);
  66. printf("%d ", root->val);
  67. MidTraval(root->right);
  68. }
  69. //后序遍历
  70. void PosTraval(Node* root)
  71. {
  72. if (root == NULL)
  73. {
  74. printf("NULL ");
  75. return;
  76. }
  77. PosTraval(root->left);
  78. PosTraval(root->right);
  79. printf("%d ", root->val);
  80. }
  81. int main()
  82. {
  83. Node* root = CreateNode();
  84. PreTraval(root);
  85. printf("\n");
  86. MidTraval(root);
  87. printf("\n");
  88. PosTraval(root);
  89. printf("\n");
  90. return 0;
  91. }

4.递归遍历的衍生问题

了解了遍历之后,现在有很多衍生问题:怎么求节点个数?怎么求第k层的节点个数?如何求叶节点个数?如何查找值为x的节点?

4.1节点个数

我们逐个分析,如何求节点个数。求个数呢,通用方法是计数法,那么计数法在我们的递归上面也可以使用。

  1. //求节点个数
  2. int count = 0;//使用全局变量
  3. int NodeSize(Node* root)
  4. {
  5. if (root == NULL)
  6. {
  7. return 0;
  8. }
  9. //static int count = 0;//使用static修饰的静态变量
  10. count++;
  11. NodeSize(root->left);
  12. NodeSize(root->right);
  13. return count;
  14. }
  15. int main()
  16. {
  17. Node* root = CreateNode();
  18. /*PreTraval(root);
  19. printf("\n");
  20. MidTraval(root);
  21. printf("\n");
  22. PosTraval(root);
  23. printf("\n");*/
  24. printf("NodeSize = %d\n", NodeSize(root));
  25. printf("NodeSize = %d\n", NodeSize(root));
  26. return 0;
  27. }

可以看到我们使用计数法是可以帮助我们完成任务的,但是当我们第二次调用这个函数就出现了问题。原因是全局变量和static修饰的静态变量只能被初始化一次。所以我们的计数方法是不够好的,那我们就要着手递归的方法了。

  1. //求节点个数
  2. int NodeSize(Node* root)
  3. {
  4. if (root == NULL)
  5. {
  6. return 0;
  7. }
  8. return NodeSize(root->left) + NodeSize(root->right) + 1;
  9. }
  10. //int count = 0;//使用全局变量
  11. //int NodeSize(Node* root)
  12. //{
  13. // if (root == NULL)
  14. // {
  15. // return 0;
  16. // }
  17. // //static int count = 0;//使用static修饰的静态变量
  18. // count++;
  19. // NodeSize(root->left);
  20. // NodeSize(root->right);
  21. // return count;
  22. //}
  23. int main()
  24. {
  25. Node* root = CreateNode();
  26. /*PreTraval(root);
  27. printf("\n");
  28. MidTraval(root);
  29. printf("\n");
  30. PosTraval(root);
  31. printf("\n");*/
  32. printf("NodeSize = %d\n", NodeSize(root));
  33. printf("NodeSize = %d\n", NodeSize(root));
  34. return 0;
  35. }

可以看到,递归的方式完美的解决了计数的"BUG"。

4.2第k层的节点个数

通过公式我们就可以发现,k是一定要被减1的,那么在递归当中也不例外。既然是要求某一层的节点个数,我们只要加一个条件:即递归到了指定层数的时候,才有返回值。 

  1. //求第k层的节点个数
  2. int KSize(Node* root,int k)
  3. {
  4. assert(k > 0);//层数大于0才有意义
  5. if (root == NULL)
  6. {
  7. return 0;
  8. }
  9. //加一个特定条件,必须在这一层才具有返回值
  10. if (k == 1)
  11. {
  12. return 1;
  13. }
  14. //否则继续往下递归找到指定层数
  15. return KSize(root->left,k-1) + KSize(root->right,k-1);
  16. }
  17. int main()
  18. {
  19. Node* root = CreateNode();
  20. /*PreTraval(root);
  21. printf("\n");
  22. MidTraval(root);
  23. printf("\n");
  24. PosTraval(root);
  25. printf("\n");*/
  26. //printf("NodeSize = %d\n", NodeSize(root));
  27. //printf("NodeSize = %d\n", NodeSize(root));
  28. printf("KSize = %d\n", KSize(root, 3));
  29. printf("KSize = %d\n", KSize(root, 1));
  30. return 0;
  31. }

4.3求叶节点个数

叶节点的特征为度为0,即左右孩子都为空。不言而喻,需要添加一个条件来具有返回值。

  1. //求叶节点的个数
  2. int LeafSize(Node* root)
  3. {
  4. if (root == NULL)
  5. {
  6. return 0;
  7. }
  8. if (root->left == NULL && root->right == NULL)
  9. {
  10. return 1;
  11. }
  12. return LeafSize(root->left) + LeafSize(root->right);
  13. }
  14. int main()
  15. {
  16. Node* root = CreateNode();
  17. /*PreTraval(root);
  18. printf("\n");
  19. MidTraval(root);
  20. printf("\n");
  21. PosTraval(root);
  22. printf("\n");*/
  23. //printf("NodeSize = %d\n", NodeSize(root));
  24. //printf("NodeSize = %d\n", NodeSize(root));
  25. //printf("KSize = %d\n", KSize(root, 3));
  26. //printf("KSize = %d\n", KSize(root, 1));
  27. printf("LeafSize = %d\n", LeafSize(root));
  28. return 0;
  29. }

 

4.4查找值为x的节点

很明显,我们需要添加一个条件来限定返回值。那么其难点在于,如果左子树当中找到了节点,那么右子树就不要遍历了;如果左子树当中没有找到指定节点才需要遍历右子树。如果左右子树都找不到指定节点才返回空。这时就要用到分治的思想。 

  1. //查找值为x的节点
  2. Node* NodeFind(Node* root, int x)
  3. {
  4. if (root == NULL)
  5. {
  6. return NULL;
  7. }
  8. if (root->val == x)
  9. {
  10. return root;
  11. }
  12. Node* LeftRet = NodeFind(root->left, x);
  13. if (LeftRet != NULL)
  14. {
  15. return LeftRet;
  16. }
  17. Node* RightRet = NodeFind(root->right, x);
  18. if (RightRet != NULL)
  19. {
  20. return RightRet;
  21. }
  22. return NULL;
  23. }
  24. int main()
  25. {
  26. Node* root = CreateNode();
  27. /*PreTraval(root);
  28. printf("\n");
  29. MidTraval(root);
  30. printf("\n");
  31. PosTraval(root);
  32. printf("\n");*/
  33. //printf("NodeSize = %d\n", NodeSize(root));
  34. //printf("NodeSize = %d\n", NodeSize(root));
  35. //printf("KSize = %d\n", KSize(root, 3));
  36. //printf("KSize = %d\n", KSize(root, 1));
  37. //printf("LeafSize = %d\n", LeafSize(root));
  38. printf("NodeFind = %p\n", NodeFind(root, 1));
  39. printf("NodeFind = %p\n", NodeFind(root, 3));
  40. printf("NodeFind = %p\n", NodeFind(root, 100));
  41. return 0;
  42. }

4.5二叉树的销毁

二叉树的销毁,就是销毁所有的节点。后序遍历是非常契合的。

  1. //二叉树销毁
  2. void BinaryDestroy(Node* root)
  3. {
  4. if (root == NULL)
  5. {
  6. return;
  7. }
  8. BinaryDestroy(root->left);
  9. BinaryDestroy(root->right);
  10. free(root);
  11. }

5.二叉树的非递归遍历

5.1层序遍历

我们可以发现,上面提到的前序、中序、后序遍历好像都在往深的地方走,走到无路可走再退回到上一层继续往深的地方走。由此我们可以总结,前序、中序、后序遍历它们都是一种深度优先遍历(DFS)。现在我们要介绍二叉树的非递归遍历,即层序遍历层序遍历是一种广度优先遍历(BFS)。 

 那么层序遍历实现的思路是怎么样的呢?我们需要借助一个工具——队列。我们看图:

那么我们上手代码时要注意,在C语言的库中没有队列这个数据结构,所以我们需要将实现队列的代码CV过来。这个问题在C++中会得到解决。那么代码我们就可以这么写:

  1. //层序遍历
  2. void LayerTraval(Node* root)
  3. {
  4. HeadTail q;
  5. QueueInit(&q);
  6. //为空则为空树
  7. if (root == NULL)
  8. {
  9. return;
  10. }
  11. //非空则入队列
  12. QueuePush(&q, root);
  13. while (!QueueEmpty(&q))
  14. {
  15. Node* tmp = QueueHead(&q);
  16. QueuePop(&q);
  17. printf("%d ", tmp->val);
  18. if (tmp->left != NULL)
  19. {
  20. QueuePush(&q, tmp->left);
  21. }
  22. if (tmp->right != NULL)
  23. {
  24. QueuePush(&q, tmp->right);
  25. }
  26. }
  27. QueueDestroy(&q);
  28. }
  29. int main()
  30. {
  31. Node* root = CreateNode();
  32. /*PreTraval(root);
  33. printf("\n");
  34. MidTraval(root);
  35. printf("\n");
  36. PosTraval(root);
  37. printf("\n");*/
  38. //printf("NodeSize = %d\n", NodeSize(root));
  39. //printf("NodeSize = %d\n", NodeSize(root));
  40. //printf("KSize = %d\n", KSize(root, 3));
  41. //printf("KSize = %d\n", KSize(root, 1));
  42. //printf("LeafSize = %d\n", LeafSize(root));
  43. //printf("NodeFind = %p\n", NodeFind(root, 1));
  44. //printf("NodeFind = %p\n", NodeFind(root, 3));
  45. //printf("NodeFind = %p\n", NodeFind(root, 100));
  46. LayerTraval(root);
  47. return 0;
  48. }

6.层序遍历的衍生问题

6.1判断二叉树是否为完全二叉树

碰到问题我们大胆地去想,首先便是通过节点个数能不能确定二叉树是否为完全二叉树。答案很明显不可能,因为完全二叉树的最后一层需要保证节点是连续的。但是这个方法是可以确定满二叉树的。

既然我们要通过层序遍历,那我们试着遍历任意几颗完全二叉树寻找规律:

 我们遍历两颗普通二叉树:

可以发现一个非常明显的规律,即完全二叉树使用层序遍历的结果 NULL 总为连续的;而普通二叉树使用层序遍历的结果 NULL 是不连续的。 

那么这个规律,便是我们代码的突破口。

  1. //判断是否为完全二叉树
  2. bool FuncTree(Node* root)
  3. {
  4. HeadTail q;
  5. QueueInit(&q);
  6. if (root == NULL)
  7. {
  8. return;
  9. }
  10. QueuePush(&q, root);
  11. while (!QueueEmpty(&q))
  12. {
  13. Node* tmp = QueueHead(&q);
  14. QueuePop(&q);
  15. //一旦拿到空,就跳出循环进行判断
  16. //此时队列后面要不有节点,要不为空
  17. //不用担心二叉树的所有节点是否完全存放在队列里面
  18. if (tmp == NULL)
  19. {
  20. break;
  21. }
  22. QueuePush(&q, tmp->left);
  23. QueuePush(&q, tmp->right);
  24. }
  25. while (!QueueEmpty(&q))
  26. {
  27. Node* tmp = QueueHead(&q);
  28. QueuePop(&q);
  29. if (tmp != NULL)
  30. {
  31. return false;
  32. }
  33. }
  34. QueueDestroy(&q);
  35. return true;
  36. }
  37. int main()
  38. {
  39. Node* root = CreateNode();
  40. /*PreTraval(root);
  41. printf("\n");
  42. MidTraval(root);
  43. printf("\n");
  44. PosTraval(root);
  45. printf("\n");*/
  46. //printf("NodeSize = %d\n", NodeSize(root));
  47. //printf("NodeSize = %d\n", NodeSize(root));
  48. //printf("KSize = %d\n", KSize(root, 3));
  49. //printf("KSize = %d\n", KSize(root, 1));
  50. //printf("LeafSize = %d\n", LeafSize(root));
  51. //printf("NodeFind = %p\n", NodeFind(root, 1));
  52. //printf("NodeFind = %p\n", NodeFind(root, 3));
  53. //printf("NodeFind = %p\n", NodeFind(root, 100));
  54. //LayerTraval(root);
  55. printf("FuncTree = %d\n", FuncTree(root));
  56. return 0;
  57. }

 8.结尾

为了方便,我把完整代码放在这里(队列各接口除外)。

  1. //队列的声明
  2. #include <stdlib.h>
  3. #include <assert.h>
  4. #include <stdbool.h>
  5. #include <stdio.h>
  6. typedef int BinaryData;
  7. typedef struct Node
  8. {
  9. BinaryData val;
  10. struct Node* left;
  11. struct Node* right;
  12. }Node;
  13. //链表的结点
  14. typedef Node* QueueData;
  15. typedef struct QueueNode
  16. {
  17. QueueData val;
  18. struct QueueNode* next;
  19. }QueueNode;
  20. //存储头、尾结点地址的指针
  21. typedef struct HeadTail
  22. {
  23. QueueNode* head;
  24. QueueNode* tail;
  25. int size;//记录队列有几个元素
  26. }HeadTail;
  27. void QueueInit(HeadTail* p);//初始化队列
  28. void QueuePush(HeadTail* p,QueueData x);//进入队列
  29. QueueData QueueHead(HeadTail* p);//获取队头元素
  30. QueueData QueueTail(HeadTail* p);//获取队尾元素
  31. void QueuePop(HeadTail* p);//删除操作,出队
  32. bool QueueEmpty(HeadTail* p);//检查队列是否为空
  33. int QueueSize(HeadTail* p);//获取队列元素个数
  34. void QueuePopTail(HeadTail* p);
  35. void QueueDestroy(HeadTail* p);//销毁队列
  1. #include "Queue.h"
  2. Node* CreateNode()
  3. {
  4. Node* n1 = (Node*)malloc(sizeof(Node));
  5. assert(n1);
  6. Node* n2 = (Node*)malloc(sizeof(Node));
  7. assert(n2);
  8. Node* n3 = (Node*)malloc(sizeof(Node));
  9. assert(n3);
  10. Node* n4 = (Node*)malloc(sizeof(Node));
  11. assert(n4);
  12. Node* n5 = (Node*)malloc(sizeof(Node));
  13. assert(n5);
  14. Node* n6 = (Node*)malloc(sizeof(Node));
  15. assert(n6);
  16. n1->val = 1;
  17. n2->val = 2;
  18. n3->val = 3;
  19. n4->val = 4;
  20. n5->val = 5;
  21. n6->val = 6;
  22. n1->left = n2;
  23. n1->right = n4;
  24. n2->left = n3;
  25. n2->right = NULL;
  26. n3->left = NULL;
  27. n3->right = NULL;
  28. n4->left = n5;
  29. n4->right = n6;
  30. n5->left = NULL;
  31. n5->right = NULL;
  32. n6->left = NULL;
  33. n6->right = NULL;
  34. return n1;
  35. }
  36. //前序遍历
  37. void PreTraval(Node* root)
  38. {
  39. if (root == NULL)
  40. {
  41. printf("NULL ");
  42. return;
  43. }
  44. printf("%d ", root->val);
  45. PreTraval(root->left);
  46. PreTraval(root->right);
  47. }
  48. //中序遍历
  49. void MidTraval(Node* root)
  50. {
  51. if (root == NULL)
  52. {
  53. printf("NULL ");
  54. return;
  55. }
  56. MidTraval(root->left);
  57. printf("%d ", root->val);
  58. MidTraval(root->right);
  59. }
  60. //后序遍历
  61. void PosTraval(Node* root)
  62. {
  63. if (root == NULL)
  64. {
  65. printf("NULL ");
  66. return;
  67. }
  68. PosTraval(root->left);
  69. PosTraval(root->right);
  70. printf("%d ", root->val);
  71. }
  72. //求节点个数
  73. int NodeSize(Node* root)
  74. {
  75. if (root == NULL)
  76. {
  77. return 0;
  78. }
  79. return NodeSize(root->left) + NodeSize(root->right) + 1;
  80. }
  81. //int count = 0;//使用全局变量
  82. //int NodeSize(Node* root)
  83. //{
  84. // if (root == NULL)
  85. // {
  86. // return 0;
  87. // }
  88. // //static int count = 0;//使用static修饰的静态变量
  89. // count++;
  90. // NodeSize(root->left);
  91. // NodeSize(root->right);
  92. // return count;
  93. //}
  94. //求第k层的节点个数
  95. int KSize(Node* root,int k)
  96. {
  97. assert(k > 0);//层数大于0才有意义
  98. if (root == NULL)
  99. {
  100. return 0;
  101. }
  102. //加一个特定条件,必须在这一层才具有返回值
  103. if (k == 1)
  104. {
  105. return 1;
  106. }
  107. //否则继续往下递归找到指定层数
  108. return KSize(root->left,k-1) + KSize(root->right,k-1);
  109. }
  110. //求叶节点的个数
  111. int LeafSize(Node* root)
  112. {
  113. if (root == NULL)
  114. {
  115. return 0;
  116. }
  117. if (root->left == NULL && root->right == NULL)
  118. {
  119. return 1;
  120. }
  121. return LeafSize(root->left) + LeafSize(root->right);
  122. }
  123. //查找值为x的节点
  124. Node* NodeFind(Node* root, int x)
  125. {
  126. if (root == NULL)
  127. {
  128. return NULL;
  129. }
  130. if (root->val == x)
  131. {
  132. return root;
  133. }
  134. Node* LeftRet = NodeFind(root->left, x);
  135. if (LeftRet != NULL)
  136. {
  137. return LeftRet;
  138. }
  139. Node* RightRet = NodeFind(root->right, x);
  140. if (RightRet != NULL)
  141. {
  142. return RightRet;
  143. }
  144. return NULL;
  145. }
  146. //层序遍历
  147. void LayerTraval(Node* root)
  148. {
  149. HeadTail q;
  150. QueueInit(&q);
  151. //为空则为空树
  152. if (root == NULL)
  153. {
  154. return;
  155. }
  156. //非空则入队列
  157. QueuePush(&q, root);
  158. while (!QueueEmpty(&q))
  159. {
  160. Node* tmp = QueueHead(&q);
  161. QueuePop(&q);
  162. printf("%d ", tmp->val);
  163. if (tmp->left != NULL)
  164. {
  165. QueuePush(&q, tmp->left);
  166. }
  167. if (tmp->right != NULL)
  168. {
  169. QueuePush(&q, tmp->right);
  170. }
  171. }
  172. QueueDestroy(&q);
  173. }
  174. //二叉树销毁
  175. void BinaryDestroy(Node* root)
  176. {
  177. if (root == NULL)
  178. {
  179. return;
  180. }
  181. BinaryDestroy(root->left);
  182. BinaryDestroy(root->right);
  183. free(root);
  184. }
  185. //判断是否为完全二叉树
  186. bool FuncTree(Node* root)
  187. {
  188. HeadTail q;
  189. QueueInit(&q);
  190. if (root == NULL)
  191. {
  192. return;
  193. }
  194. QueuePush(&q, root);
  195. while (!QueueEmpty(&q))
  196. {
  197. Node* tmp = QueueHead(&q);
  198. QueuePop(&q);
  199. //一旦拿到空,就跳出循环进行判断
  200. //此时队列后面要不有节点,要不为空
  201. //不用担心二叉树的所有节点是否完全存放在队列里面
  202. if (tmp == NULL)
  203. {
  204. break;
  205. }
  206. QueuePush(&q, tmp->left);
  207. QueuePush(&q, tmp->right);
  208. }
  209. while (!QueueEmpty(&q))
  210. {
  211. Node* tmp = QueueHead(&q);
  212. QueuePop(&q);
  213. if (tmp != NULL)
  214. {
  215. return false;
  216. }
  217. }
  218. QueueDestroy(&q);
  219. return true;
  220. }
  221. int main()
  222. {
  223. Node* root = CreateNode();
  224. /*PreTraval(root);
  225. printf("\n");
  226. MidTraval(root);
  227. printf("\n");
  228. PosTraval(root);
  229. printf("\n");*/
  230. //printf("NodeSize = %d\n", NodeSize(root));
  231. //printf("NodeSize = %d\n", NodeSize(root));
  232. //printf("KSize = %d\n", KSize(root, 3));
  233. //printf("KSize = %d\n", KSize(root, 1));
  234. //printf("LeafSize = %d\n", LeafSize(root));
  235. //printf("NodeFind = %p\n", NodeFind(root, 1));
  236. //printf("NodeFind = %p\n", NodeFind(root, 3));
  237. //printf("NodeFind = %p\n", NodeFind(root, 100));
  238. //LayerTraval(root);
  239. printf("FuncTree = %d\n", FuncTree(root));
  240. return 0;
  241. }

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

闽ICP备14008679号