• 2022_08_09__106期__二叉树

    目录

    满二叉树和完全二叉树：

    二叉树的性质：

    链式存储：

    二叉树前序遍历：

    中序遍历：

    统计节点的个数：

    叶子节点的数目:

    求树的高度：

    满二叉树和完全二叉树：

     满二叉树是所有节点的值都达到最大值，假设满二叉树的层数是k，则满二叉树的节点数量为2^k-1.

    完全二叉树是除最后一行的节点外，所有的节点都是满的，满二叉树是完全二叉树的一种。

    二叉树的性质：

    性质1

     假设i=1时，我们的第一层节点的数目为2^0=1.

    假设i=2，我们的第二层节点的数目为2^1结果为2.

    假设i=3，我们的第三层节点的数目为2^2结果为4.

    所以第i层的最多有2^(n-1)个节点。

    性质2：

     假设我们的深度为1时，我们的节点的数目为2^1-1，结果为1.

     假设我们的深度为2时，我们的节点的数目为2^2-1,结果为3.

    性质3：

     度为0的叶节点的个数为1，为n1

    度为2的叶节点的个数为0，为n2.

    n1-n2=1.

      度为0的叶节点的个数为2，为n1

    度为2的叶节点的个数为1，为n2.

    n1-n2=1.

       度为0的叶节点的个数为4，为n1

    度为2的叶节点的个数为3，为n2.

    n1-n2=1.

    性质4：

    假设我们的满二叉树深度为h，我们的满二叉树节点个数为n。2^h-1=n,2^h=n+1,h=log(n+1).

    性质5：

     假设我们的完全二叉树的高度为h，我们的节点个数为N，完全二叉树的节点的最大值为2^h-1.完全二叉树的节点的最小值为2^(h-1)-1+1为2^(h-1).

    所以2^(h-1)<=N<=2^h-1

    题目1：

     因为度为0的节点比度为2的节点多一个，所以度为0的节点为200个，而叶子节点就是度为0的节点，所以叶子节点的个数为200个，选B

    题目2

     非完全二叉树的图像：

     对应的顺序存储：

     对应的顺序存储是不连续的，所以非完全二叉树不适合采用顺序存储。

    题目3：

     节点分为三种，分为度为0的节点n0，度为1的节点为n1，度为2的节点为n2.

    所以n0+n1+n2=2n

     对于完全二叉树来说，n1要么是1，要莫是0

    又因为度为0的节点比度为1的节点大1

    n0+n1+n0-1=2n

    2n0-1+n1=2n，所以只有n1等于1时，才符合规律。

    而叶子节点等于度为0的节点，也就是n

    所以答案为A

    题目4：

    假设我们的高度为h的话，完全二叉树的元素个数为

    2^(N-1)<=N<=2^N-1

    计算得出，N为10，所以这棵树的高度为10.

     第六题：

     这道题就是刚才的变形：

    2n0-1+n1=767

    2n0+n1=768，所以n1=0，所以n0等于384.

    答案选B

    链式存储：

    前序遍历：根 左子树 右子树

    中续遍历：左子树 根 右子树

    后续遍历：左子树 右子树 根：

    前序遍历的过程：

    首先访问1的左子树，1的左子树为2，再访问2的左子树为3，再访问3的左子树为NULL，再访问3的右子树为NULL，然后访问2的右子树为NULL

    然后访问1的右子树4，再访问4的左子树5，再访问5的左子树为NULL，再访问5的右子树为NULL，再访问4的右子树6，再访问6的左子树为NULL，再访问6的右子树为NULL，

     所以1->2->3->NULL->NULL->NULL->4->5->NULL->NULL->6->NULL->NULL.

    这就是前序遍历的过程。

    1 2 3 4 5 6

    中序遍历的过程：

    首先，我们要找左节点，找1，找2，找3，找到3的左节点NULL，再找到3，再找到3的右节点NULL，我们再找2，再找2的右节点为NULL，再找1，再通过4，5，找到5的左节点为NULL，再找到5，再找到5的右节点为NULL，再找到4，再找到6

    所以过程为 NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

    3 2 1 5 4 6

    后续遍历的过程：

    先找到左子树，找到3的左子树为NULL，右子树为NULL，找到3，2的右子树为NULL，找到2，再通过1，4，5找到5的左子树为NULL，5的右子树为NULL，再通过4，6找到6的左子树为NULL,右子树为NULL，再找到6，再找到4，再找到1

    所以过程： NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1

    3 2 5 6 4 1.

    二叉树前序遍历：

    我们用代码实现：

    1. #include
    2. #include
    3. #include
    4. typedef int BTDataType;
    5. typedef struct BinaryTreeNode
    6. {
    7. 	BTDataType data;
    8. 	struct BinartTreeNode*left;
    9. 	struct BinaryTreeNode*right;
    10. }BTNode;
    11. void PreOrder(BTNode*root)
    12. {
    13. 	if (root == NULL)
    14. 		return;
    15. 	printf("%d  ", root->data);
    16. 	PreOrder(root->left);
    17. 	PreOrder(root->right);
    18. }
    19. void InOrder(BTNode*root);
    20. void PostOrder(BTNode*root);
    21.  
    22. BTNode*CreateTree()
    23. {
    24. 	BTNode*n1 = (BTNode*)malloc(sizeof(BTNode));
    25. 	assert(n1);
    26. 	BTNode*n2 = (BTNode*)malloc(sizeof(BTNode));
    27. 	assert(n2);
    28. 	BTNode*n3 = (BTNode*)malloc(sizeof(BTNode));
    29. 	assert(n3);
    30. 	BTNode*n4 = (BTNode*)malloc(sizeof(BTNode));
    31. 	assert(n4);
    32. 	BTNode*n5 = (BTNode*)malloc(sizeof(BTNode));
    33. 	assert(n5);
    34. 	BTNode*n6 = (BTNode*)malloc(sizeof(BTNode));
    35. 	assert(n6);
    36.  
    37. 	n1->data = 1;
    38. 	n2->data = 2;
    39. 	n3->data = 3;
    40. 	n4->data = 4;
    41. 	n5->data = 5;
    42. 	n6->data = 6;
    43.  
    44. 	n1->left = n2;
    45. 	n1->right = n4;
    46. 	n2->right = NULL;
    47. 	n2->left = n3;
    48. 	n2->right = NULL;
    49. 	n4->left = n5;
    50. 	n4->right = n6;
    51. 	n3->left = NULL;
    52. 	n3->right = NULL;
    53. 	n5->left = NULL;
    54. 	n5->right = NULL;
    55. 	n6->left = NULL;
    56. 	n6->right = NULL;
    57. 	return n1;
    58. }
    59.  
    60. int main()
    61. {
    62. 	BTNode*root = CreateTree();
    63. 	PreOrder(root);
    64. 	printf("\n");
    65. 	return 0;
    66. }
    1. typedef struct BinaryTreeNode
    2. {
    3. 	BTDataType data;
    4. 	struct BinartTreeNode*left;
    5. 	struct BinaryTreeNode*right;
    6. }BTNode;

    这里我们构造二叉树，我们把BinaryTreeNode重命名为BTNode

    结构体有三个成员变量，分别是：节点中存放的数据，左节点和右节点

    我们对二叉树进行初始化：

    1. BTNode*CreateTree()
    2. {
    3. 	BTNode*n1 = (BTNode*)malloc(sizeof(BTNode));
    4. 	assert(n1);
    5. 	BTNode*n2 = (BTNode*)malloc(sizeof(BTNode));
    6. 	assert(n2);
    7. 	BTNode*n3 = (BTNode*)malloc(sizeof(BTNode));
    8. 	assert(n3);
    9. 	BTNode*n4 = (BTNode*)malloc(sizeof(BTNode));
    10. 	assert(n4);
    11. 	BTNode*n5 = (BTNode*)malloc(sizeof(BTNode));
    12. 	assert(n5);
    13. 	BTNode*n6 = (BTNode*)malloc(sizeof(BTNode));
    14. 	assert(n6);
    15.  
    16. 	n1->data = 1;
    17. 	n2->data = 2;
    18. 	n3->data = 3;
    19. 	n4->data = 4;
    20. 	n5->data = 5;
    21. 	n6->data = 6;
    22.  
    23. 	n1->left = n2;
    24. 	n1->right = n4;
    25. 	n2->right = NULL;
    26. 	n2->left = n3;
    27. 	n2->right = NULL;
    28. 	n4->left = n5;
    29. 	n4->right = n6;
    30. 	n3->left = NULL;
    31. 	n3->right = NULL;
    32. 	n5->left = NULL;
    33. 	n5->right = NULL;
    34. 	n6->left = NULL;
    35. 	n6->right = NULL;
    36. 	return n1;
    37. }

    我们进行动态内存开辟申请空间，分别为6个节点分配相同数量字节大小的空间，正常情况下，我们使用malloc需要创建临时变量，还需要判断malloc是否申请失败，我们这里可以直接使用断言，假如malloc申请失败，不进入函数。

    我们再对节点的值进行初始化。

    把二叉树节点与节点的关系写明。

     然后我们返回头节点。

    接下来，我们调用函数：

    1. void PreOrder(BTNode*root)
    2. {
    3. 	if (root == NULL)
    4. 		return;
    5. 	printf("%d  ", root->data);
    6. 	PreOrder(root->left);
    7. 	PreOrder(root->right);
    8. }

    root的初始值是二叉树的头节点。

    我们画图进行解释：

     因为对应的节点1不为NULL，我们打印节点对应的数据，节点1对应的数据为1，然后我们继续调用前序遍历函数：

    root-

     2节点不为空指针，打印2节点对应的值为2，调用前序遍历函数，root->left指向的是3节点。

     3节点不为空指针，打印3节点对应的数据为3，继续调用前序遍历函数：

    root->left指向的是空指针

    这时候root==NULL，我们退出函数。

    我们开始向外扩展，首先root->right也为空指针，退出函数。

    然后求2->right也为空指针。

    所以已经求出所有的二叉树左边的数据，接下来，求二叉树右边的：

    4节点不为空指针，打印4节点对应的数据，然后继续调用函数：

    4->left为5节点，5节点不为空，打印5节点对应的数据，继续调用函数

    5->left为空指针，退出函数，调用5->right为空指针，退出函数

    然后调用4->right=6节点,6节点不为空指针，打印6节点对应的数据，继续调用函数

    6->left=NULL,退出函数。6->right=NULL,退出函数。

    所以我们打印的结果应该是1，2，3，4，5，6

    接下来，我们来实现

    中序遍历：

    1. void InOrder(BTNode*root)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		printf("NULL ");
    6. 		return;
    7. 	}
    8. 	InOrder(root->left);
    9. 	printf("%d ", root->data);
    10. 	InOrder(root->right);
    11. }

    我们用图像进行解析：

     root首先为1，1不为空指针，我们先找左节点，继续调用函数：

     1->left=2节点，2节点不为空指针，我们先找左节点，继续调用函数

    2->left=3节点，3节点不为空指针，我们先找左节点，继续调用函数。

    3->left=NULL，然后我们打印3，3->right=NULL。

    然后我们打印2，调用函数2->right为空指针，退出函数。

    等等。

    统计节点的个数：

    第一种写法：

    1. void TreeSize(BTNode*root)
    2. {
    3. 	static int count = 0;
    4. 	if (root == NULL)
    5. 	{
    6. 		return;
    7. 	}
    8. 	TreeSize(root->left);
    9. 	count++;
    10. 	TreeSize(root->right);
    11. 	return count;
    12. }

    static修饰的原因是能够保留值，因为我们的count是局部变量，假如我们不用static修饰时，每一次递归调用treesize函数时，我们的count的值都为0.

    我们对代码进行分析：

    首先要创建一个参数count，用来计算树的节点个数。

    如果root为空指针

    如图所示。我们要退出函数。

    然后我们递归调用求左侧树的节点，然后count++，再求右侧树的节点数目。

    我们调用函数：

    1. int main()
    2. {
    3. 	BTNode*root = CreateTree();
    4. 	PreOrder(root);
    5. 	printf("\n");
    6. 	InOrder(root);
    7. 	printf("\n");
    8. 	printf("Tree size:%d\n", TreeSize(root));
    9. 	return 0;
    10. }

     

     我们计算的结果是正确的，但我们的函数还是存在一些问题：

    假如我们要连续调用两次函数呢？

    1. int main()
    2. {
    3. 	BTNode*root = CreateTree();
    4. 	PreOrder(root);
    5. 	printf("\n");
    6. 	InOrder(root);
    7. 	printf("\n");
    8. 	printf("Tree size:%d\n", TreeSize(root));
    9. 	printf("Tree size:%d\n", TreeSize(root));
    10. 	return 0;
    11. }

    我们进行编译：

     因为我们的static修饰变量会保留变量的原值，第一次调用，我们的count为6，第二次调用，我们的count就为12.

    我们可以定义一个全局的变量。

    1. int count = 0;
    2. void TreeSize(BTNode*root)
    3. {
    4. 	if (root == NULL)
    5. 	{
    6. 		return;
    7. 	}
    8. 	TreeSize(root->left);
    9. 	count++;
    10. 	TreeSize(root->right);
    11. 	return;
    12. }

    我们在函数外创建一个全局变量count，我们在函数中只需控制函数的加减即可。

    我们进行调用函数：

    1. int main()
    2. {
    3. 	BTNode*root = CreateTree();
    4. 	PreOrder(root);
    5. 	printf("\n");
    6. 	InOrder(root);
    7. 	printf("\n");
    8. 	TreeSize(root);
    9. 	printf("Tree size:%d\n", count);
    10. 	count = 0;
    11. 	TreeSize(root);
    12. 	printf("Tree size:%d\n", count);
    13. 	return 0;
    14. }

     

     

    子问题的思路解决：

    这种思路的核心是分而治之：

    1. int TreeSize(BTNode*root)
    2. {
    3. 	return root == NULL ? 0 :
    4. 		TreeSize(root->left) + TreeSize(root->right) + 1;
    5. }

    root为空指针时，返回0，不为空指针，返回左树的节点和右数的节点加1.

    叶子节点的数目:

    1. int LeafSize(BTNode*root)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		return 0;
    6. 	}
    7. 	if (root->left == NULL
    8. 		&&root->right == NULL)
    9. 		return 1;
    10. 	return LeafSize(root->left)
    11. 		+LeafSize(root->right);
    12. }

    我们进行编译：

    叶子节点的数目为3.

    叶子节点的满足条件是root->left==root->right=NULL。

     

    求树的高度：

    1. int TreeHeight(BTNode*root)
    2. {
    3. 	if (root == NULL)
    4. 	{
    5. 		return 0;
    6. 	}
    7. 	int lh = TreeHeight(root->left);
    8. 	int rh = TreeHeight(root->right);
    9. 	return lh > rh ? lh + 1 : rh + 1;
    10. }

  • 相关阅读:
    C和指针 第13章 高级指针话题 13.5 字符串常量
    这些13 种锁的实现方式你知道吗
    谈谈电子电气架构的解决方案与发展路线
    springboot集成flowable简单实例入门
    未授权访问：MongoDB未授权访问漏洞
    洛谷题解 | P1046 陶陶摘苹果
    面前是惊涛骇浪：对当下的经济困境，货币政策和大类资产的看法
    要想后期修改少，代码重构要趁早
    【Python语言速回顾】——爬虫基础知识
    基于SSM的学院就业信息网设计与实现
  • 原文地址：https://blog.csdn.net/qq_66581313/article/details/126435987