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

    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

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

    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.  
    16. int main()
    17. {
    18. 	Node* root = CreateNode();
    19. 	/*PreTraval(root);
    20. 	printf("\n");
    21. 	MidTraval(root);
    22. 	printf("\n");
    23. 	PosTraval(root);
    24. 	printf("\n");*/
    25.  
    26. 	printf("NodeSize = %d\n", NodeSize(root));
    27. 	printf("NodeSize = %d\n", NodeSize(root));
    28. 	return 0;
    29. }

    可以看到我们使用计数法是可以帮助我们完成任务的，但是当我们第二次调用这个函数就出现了问题。原因是全局变量和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.  
    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.  
    34. 	printf("NodeSize = %d\n", NodeSize(root));
    35. 	printf("NodeSize = %d\n", NodeSize(root));
    36. 	return 0;
    37. }

    可以看到，递归的方式完美的解决了计数的"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.  
    18. int main()
    19. {
    20. 	Node* root = CreateNode();
    21. 	/*PreTraval(root);
    22. 	printf("\n");
    23. 	MidTraval(root);
    24. 	printf("\n");
    25. 	PosTraval(root);
    26. 	printf("\n");*/
    27.  
    28. 	//printf("NodeSize = %d\n", NodeSize(root));
    29. 	//printf("NodeSize = %d\n", NodeSize(root));
    30.  
    31. 	printf("KSize = %d\n", KSize(root, 3));
    32. 	printf("KSize = %d\n", KSize(root, 1));
    33.  
    34. 	return 0;
    35. }

    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.  
    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.  
    25. 	//printf("NodeSize = %d\n", NodeSize(root));
    26. 	//printf("NodeSize = %d\n", NodeSize(root));
    27.  
    28. 	//printf("KSize = %d\n", KSize(root, 3));
    29. 	//printf("KSize = %d\n", KSize(root, 1));
    30.  
    31. 	printf("LeafSize = %d\n", LeafSize(root));
    32. 	return 0;
    33. }

     

    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.  
    25. int main()
    26. {
    27. 	Node* root = CreateNode();
    28. 	/*PreTraval(root);
    29. 	printf("\n");
    30. 	MidTraval(root);
    31. 	printf("\n");
    32. 	PosTraval(root);
    33. 	printf("\n");*/
    34.  
    35. 	//printf("NodeSize = %d\n", NodeSize(root));
    36. 	//printf("NodeSize = %d\n", NodeSize(root));
    37.  
    38. 	//printf("KSize = %d\n", KSize(root, 3));
    39. 	//printf("KSize = %d\n", KSize(root, 1));
    40.  
    41. 	//printf("LeafSize = %d\n", LeafSize(root));
    42.  
    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.  
    47. 	return 0;
    48. }

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

    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. 	}
    26. 	while (!QueueEmpty(&q))
    27. 	{
    28. 		Node* tmp = QueueHead(&q);
    29. 		QueuePop(&q);
    30. 		if (tmp != NULL)
    31. 		{
    32. 			return false;
    33. 		}
    34. 	}
    35. 	QueueDestroy(&q);
    36. 	return true;
    37. }
    38.  
    39.  
    40. int main()
    41. {
    42. 	Node* root = CreateNode();
    43. 	/*PreTraval(root);
    44. 	printf("\n");
    45. 	MidTraval(root);
    46. 	printf("\n");
    47. 	PosTraval(root);
    48. 	printf("\n");*/
    49.  
    50. 	//printf("NodeSize = %d\n", NodeSize(root));
    51. 	//printf("NodeSize = %d\n", NodeSize(root));
    52.  
    53. 	//printf("KSize = %d\n", KSize(root, 3));
    54. 	//printf("KSize = %d\n", KSize(root, 1));
    55.  
    56. 	//printf("LeafSize = %d\n", LeafSize(root));
    57.  
    58. 	//printf("NodeFind = %p\n", NodeFind(root, 1));
    59. 	//printf("NodeFind = %p\n", NodeFind(root, 3));
    60. 	//printf("NodeFind = %p\n", NodeFind(root, 100));
    61.  
    62. 	//LayerTraval(root);
    63. 	printf("FuncTree = %d\n", FuncTree(root));
    64. 	return 0;
    65. }

     8.结尾

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

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

  • 相关阅读:
    选择排序（学习笔记）
    Java IO流处理 面试题汇总
    数据结构与算法分析之树（1）
    C#获取指定软件安装路径
    化工厂人员定位方案
    【错误解决方案】ModuleNotFoundError: No module named ‘ngboost‘
    【网络爬虫】2 初探网络爬虫
    Python 中 4 个高效的技巧！
    Scott-Knott ESD test
    【Redis】Set集合内部编码方式
  • 原文地址：https://blog.csdn.net/weixin_59913110/article/details/126583056