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

C++数据结构与算法（二叉树）_c++ 二叉树

作者：知新_RL | 2024-05-25 12:08:32

赞

踩

c++ 二叉树

目录

1、树的两种定义

2、相关概念

3、二叉树

3.1两种定义

3.2二叉树和树的根本区别

3.3二叉树的创建及遍历

3.3.1（前序、中序和后序递归）

3.3.2（前序、中序和后序非递归）

3.3.3new/delete和malloc/free的区别

3.3.4Practice

3.4二叉树的特性

3.5二叉树常用操作

3.5.1统计二叉树的叶子节点数

3.5.2返回一棵二叉树的层数

3.5.3查找Key值（节点不重复）

3.5.4复制一棵二叉树

3.5.5层次遍历二叉树

3.5.6镜像二叉树

3.5.7统计分支节点个数和单双分支节点个数

3.5.8创建一棵完全二叉树

1、树的两种定义

1）树是一种数据结构，它是由n（n>=1）个有限的节点组成的一个具有层次关系的集合。

2）树（tree）t是一个非空的有限元素的集合，其中一个元素为根（root），余下的元素（如果有的话）组成t的子树（subtree）.

2、相关概念

1）节点的度：节点拥有的孩子的数目，叶节点的度为零；

2）叶子：度为零的节点；

3）分支节点：度不为零的节点；

4）树的度：树中节点的最大的度；

5）层次：根节点的层次为1，往下依次递增；

6）树的高度：树中节点的最大层次；

7）无序树：如果树中节点的各子树之间的次序是不重要的，可以交换位置；

8）有序树：如果树中节点的各子树之间的次序是重要的，不可以交换位置；

9）森林：0或多个不相交的树组成。对森林加上一个根，森林即成为树，删除根，树即成为森林。

10）二叉树是每个节点最多有两个子树的树结构；

11）高度为h，并且由2^h-1个节点的二叉树，被称为满二叉树；

12）一颗二叉树中，只有最下面两层节点的度可以小于2，并且最下一层的叶节点集中在靠左的若干位置上，这样的二叉树被称为完全二叉树；

13）二叉查找树：又被称为二叉搜索树，左子树上的节点小于根节点的值，右子树上的节点大于根节点的值。

3、二叉树

3.1两种定义

节点可以包含两个子节点（也可能为空）的树，每一个子节点都区分为左子节点或右子节点。

二叉树（binary tree）t是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个称为根的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树。

 

       节点的层次是从根到该节点所经过的弧的个数加1。根据该定义，根的层次是1，其非空子节点的层次是2，以此类推。如果除最后一个层次外，其他层上的所有节点都有两个子节点，那么。第一层有1=2^0个节点，第二层有2=2^1个节点，...，第i+1层有2^i个节点。满足该条件的树称为完全二叉树（complete binary tree）。在该树中，所有的非终端节点都有两个子节点，所有的叶节点都位于同一层次。因此，在所有的二叉树中，第i+1层最多有2^i个节点。

        满二叉树是完全二叉树的一种特例。

3.2二叉树和树的根本区别

1）二叉树可以为空，但树不能（原因：树是图的特例，但二叉树不是树的特例，图是不能为空的）；

2）二叉树中每个元素都恰好有两棵子树（其中一个或两个可能为空）。而树中每个元素可有若干子树；

3）在二叉树中每个元素的子树都是有序的，也就是说，可以用左、右子树来区别。而树的子树间是无序的。

3.3二叉树的创建及遍历

3.3.1（前序、中序和后序递归）

  1. /*
  2. 创建二叉树，并且进行输出（前序、中序、后序递归）
  3. */
  4. #include<iostream>
  5. #include<iomanip>
  6. using namespace std;
  7.  
  8. typedef struct Node{
  9. 	int data;                    //数据域
  10. 	struct Node *left, *right;   //指针域
  11. }BTNode;
  12.  
  13. //创建二叉树
  14. BTNode *CreateBTtree(int a[], int n)
  15. {
  16. 	BTNode *root, *c, *pa=NULL, *p;
  17. 	int i;
  18. 	//root = (BTNode *)malloc(sizeof(BTNode));
  19. 	root = new BTNode;
  20. 	root->data = a[0];
  21. 	root->left = root->right = NULL;
  22. 	for (i = 1; i<n; i++)
  23. 	{
  24. 		//p = (BTNode *)malloc(sizeof(BTNode));
  25. 		p = new BTNode;
  26. 		p->left = p->right = NULL;
  27. 		p->data = a[i];
  28. 		c = root;
  29. 		while (c)
  30. 		{
  31. 			pa = c;
  32. 			if (c->data < p->data) //根节点小于待插入节点
  33. 				c = c->right;      //往右遍历
  34. 			else                  //根节点大于待插入节点 
  35. 				c = c->left;      //往左遍历
  36. 		}
  37. 		if (pa->data < p->data)
  38. 			pa->right = p;        //右放
  39. 		else
  40. 			pa->left = p;         //左放
  41. 	}
  42. 	return root;    //返回根节点
  43. }
  44.  
  45. //前序遍历
  46. void Forder(BTNode *root)
  47. {
  48. 	if (root)
  49. 	{
  50. 		//printf("%5d", root->data);
  51. 		cout << setw(5) << root->data;
  52. 		Forder(root->left);
  53. 		Forder(root->right);
  54. 	}
  55. }
  56.  
  57. //中序遍历
  58. void Inorder(BTNode *root)
  59. {
  60. 	if (root)
  61. 	{
  62. 		Inorder(root->left);
  63. 		//printf("%5d", root->data);
  64. 		cout << setw(5) << root->data;
  65. 		Inorder(root->right);
  66. 	}
  67. }
  68.  
  69. //后序遍历
  70. void Porder(BTNode *root)
  71. {
  72. 	if (root)
  73. 	{
  74. 		Porder(root->left);
  75. 		Porder(root->right);
  76. 		//printf("%5d", root->data);
  77. 		cout << setw(5) << root->data;
  78. 	}
  79. }
  80.  
  81. int main()
  82. {
  83. 	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
  84. 	BTNode *root;
  85. 	root = CreateBTtree(a, 8);
  86. 	//前序遍历
  87. 	printf("前序遍历为:");
  88. 	Forder(root);
  89. 	cout << endl;
  90. 	//中序遍历
  91. 	printf("中序遍历为:");
  92. 	Inorder(root);
  93. 	cout << endl;
  94. 	//后序遍历
  95. 	printf("后序遍历为:");
  96. 	Porder(root);
  97. 	cout << endl;
  98. 	system("pause");
  99. 	return 0;
  100. }

常用的三种遍历方法的遍历顺序：

前序遍历：根  >  左  >  右

中序遍历：左  >  根  >  右

后序遍历：左  >  右  >  根

结果：

3.3.2（前序、中序和后序非递归）

  1. /*
  2. 创建二叉树并输出（前序、中序和后序非递归遍历）
  3. */
  4. #include<iostream>
  5. #include<iomanip>
  6. using namespace std;
  7. #define N 9
  8.  
  9. typedef struct Node{
  10. 	int data;
  11. 	struct Node *left, *right;
  12. }BTNode;
  13.  
  14. //创建二叉树
  15. BTNode *CreateBTtree(int a[])
  16. {
  17. 	BTNode *root, *c, *pa = NULL, *p;
  18. 	int i;
  19. 	root = (BTNode *)malloc(sizeof(BTNode));
  20. 	root->data = a[0];
  21. 	root->left = root->right = NULL;
  22. 	for (i = 1; i<N; i++)
  23. 	{
  24. 		p = (BTNode *)malloc(sizeof(BTNode));
  25. 		p->left = p->right = NULL;
  26. 		p->data = a[i];
  27. 		c = root;
  28. 		while (c)
  29. 		{
  30. 			pa = c;
  31. 			if (c->data < p->data)
  32. 				c = c->right;
  33. 			else
  34. 				c = c->left;
  35. 		}
  36. 		if (pa->data < p->data)
  37. 			pa->right = p;
  38. 		else
  39. 			pa->left = p;
  40. 	}
  41. 	return root;
  42. }
  43.  
  44. //前序遍历
  45. void priorder(BTNode *root)
  46. {
  47. 	int top;
  48. 	BTNode **s;
  49. 	BTNode *p;
  50. 	//声明栈
  51. 	s = (BTNode **)malloc(N*sizeof(BTNode *));
  52. 	top = -1;
  53. 	s[++top] = root;
  54. 	while (top != -1)
  55. 	{
  56. 		p = s[top--];
  57. 		//printf("%5d", p->data);
  58. 		cout << setw(5) << p->data;
  59. 		if (p->right)
  60. 			s[++top] = p->right;
  61. 		if (p->left)
  62. 			s[++top] = p->left;
  63. 	}
  64. }
  65.  
  66. //中序遍历
  67. void Inorder(BTNode *root)
  68. {
  69. 	int top;
  70. 	BTNode **s;
  71. 	BTNode *p;
  72. 	//声明栈
  73. 	s = (BTNode **)malloc(N*sizeof(BTNode *));
  74. 	p = root;
  75. 	top = -1;
  76. 	while (p)
  77. 	{
  78. 		s[++top] = p;
  79. 		p = p->left;
  80. 	}
  81. 	while (top != -1)
  82. 	{
  83. 		p = s[top--];
  84. 		//printf("%5d", p->data);
  85. 		cout << setw(5) << p->data;
  86. 		if (p->right)
  87. 		{
  88. 			p = p->right;
  89. 			while (p)
  90. 			{
  91. 				s[++top] = p;
  92. 				p = p->left;
  93. 			}
  94. 		}
  95. 	}
  96. 	free(s);
  97. }
  98.  
  99. //后序遍历
  100. void  PostorderTraverse(BTNode  *root)
  101. {
  102. 	BTNode *S1[N], *p = root;
  103. 	int S2[N], top = 0, flag = 1;
  104. 	if (root == NULL)
  105. 		printf("Binary Tree is Empty!\n");
  106. 	else
  107. 	{
  108. 		do
  109. 		{
  110. 			while (p != NULL)
  111. 			{
  112. 				S1[++top] = p;
  113. 				S2[top] = 0;
  114. 				p = p->left;
  115. 			}
  116. 			if (top == 0)
  117. 				flag = 0;
  118. 			else if (S2[top] == 0)
  119. 			{
  120. 				p = S1[top]->right;
  121. 				S2[top] = 1;
  122. 			}
  123. 			else
  124. 			{
  125. 				p = S1[top];
  126. 				top--;
  127. 				//printf("%5d", p->data);
  128. 				cout << setw(5) << p->data;
  129. 				p = NULL;                 /*  使循环继续进行而不至于死循环 */
  130. 			}
  131. 		} while (flag != 0);
  132. 	}
  133. }
  134.  
  135.  
  136. int main()
  137. {
  138. 	int a[N] = { 6, 2, 8, 1, 4, 10, 3, 5, 9 };
  139. 	BTNode *root;
  140. 	//创建二叉树
  141. 	root = CreateBTtree(a);
  142.  
  143. 	cout << "前序遍历：";
  144. 	//按前序遍历
  145. 	priorder(root);
  146. 	cout << endl;
  147.  
  148. 	cout << "中序遍历：";
  149. 	//按中序遍历
  150. 	Inorder(root);
  151. 	cout << endl;
  152.  
  153. 	cout << "后序遍历：";
  154. 	//按后序遍历
  155. 	PostorderTraverse(root);
  156. 	cout << endl;
  157.  
  158. 	system("pause");
  159. 	return 0;
  160. }

结果：

3.3.3new/delete和malloc/free的区别

详见：https://www.cnblogs.com/QG-whz/p/5140930.html

3.3.4Practice

1）根据前序遍历和中序遍历画出树的结构

2）数学表达式树

       当对一棵数学表达式树进行中序，前序和后序遍历时，就分别得到表达式的中缀、前缀和后缀形式。中缀（infix）形式即为平时所书写的数学表达式。在后缀（postfix）表达式中，每个操作符跟在操作数后面，操作数从左到右的顺序出现。在前缀（prefix）表达式中，操作符位于操作数之前。

3.4二叉树的特性

特性1  包含n（n>0）个元素的二叉树边数为n-1.

特性2  若二叉树的高度为h，h>=0，则该二叉树最少有h个元素，最多有2^h-1个元素。

特性3  包含n个元素的二叉树的高度最大为n，最小为.

特性4  设完全二叉树中一元素的序号为i，，则有以下关系成立：

           1）当i=1时，该元素为二叉树的根。若i>1，则该元素父节点的编号为i/2；

           2）当2i>n时，该元素无左孩子。否则，其左孩子的编号为2i；

           3）当2i+1>n时，该元素无右孩子。否则，其右孩子编号为2i+1.

3.5二叉树常用操作

3.5.1统计二叉树的叶子节点数

  1. /*返回二叉树的叶子节点的数目*/
  2. #include<iostream>
  3. #include<iomanip>
  4. using namespace std;
  5.  
  6. //节点结构体
  7. typedef struct Node{
  8. 	int data;
  9. 	struct Node *left, *right;
  10. }BTNode;
  11.  
  12. //创建二叉树
  13. BTNode *CreateBTtree(int a[], int n)
  14. {
  15. 	BTNode *root, *c, *pa = NULL, *p;
  16. 	int i;
  17. 	//root = (BTNode *)malloc(sizeof(BTNode));
  18. 	root = new BTNode;
  19. 	root->data = a[0];
  20. 	root->left = root->right = NULL;
  21. 	for (i = 1; i<n; i++)
  22. 	{
  23. 		//p = (BTNode *)malloc(sizeof(BTNode));
  24. 		p = new BTNode;
  25. 		p->left = p->right = NULL;
  26. 		p->data = a[i];
  27. 		c = root;
  28. 		while (c)
  29. 		{
  30. 			pa = c;
  31. 			if (c->data<p->data)
  32. 				c = c->right;
  33. 			else
  34. 				c = c->left;
  35. 		}
  36. 		if (pa->data<p->data)
  37. 			pa->right = p;
  38. 		else
  39. 			pa->left = p;
  40. 	}
  41. 	return root;
  42. }
  43.  
  44.  
  45. //前序遍历
  46. void Forder(BTNode *root)
  47. {
  48. 	if (root)
  49. 	{
  50. 		cout << setw(5) << root->data;
  51. 		Forder(root->left);
  52. 		Forder(root->right);
  53. 	}
  54. }
  55.  
  56. //中序遍历
  57. void Inorder(BTNode *root)
  58. {
  59. 	if (root)
  60. 	{
  61. 		Inorder(root->left);
  62. 		cout << setw(5) << root->data;
  63. 		Inorder(root->right);
  64. 	}
  65. }
  66.  
  67. //后序遍历
  68. void Porder(BTNode *root)
  69. {
  70. 	if (root)
  71. 	{
  72. 		Porder(root->left);
  73. 		Porder(root->right);
  74. 		cout << setw(5) << root->data;
  75. 	}
  76. }
  77.  
  78.  
  79. //计算二叉树叶子节点数
  80. int CountLeafNode(BTNode *root)
  81. {
  82. 	int l1, l2, l;
  83. 	if (root == NULL)
  84. 		return 0;
  85. 	else
  86. 	{
  87. 		l1 = CountLeafNode(root->left);
  88. 		l2 = CountLeafNode(root->right);
  89. 		l = l1 + l2;
  90. 		if ((!root->left) && (!root->right))
  91. 			l++;
  92. 		return l;
  93. 	}
  94. }
  95.  
  96. int main()
  97. {
  98. 	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
  99. 	int x;
  100. 	BTNode *root;
  101. 	root = CreateBTtree(a, 8);
  102. 	
  103. 	//前序遍历
  104. 	printf("前序遍历为:");
  105. 	Forder(root);
  106. 	cout << endl;
  107. 	//中序遍历
  108. 	printf("中序遍历为:");
  109. 	Inorder(root);
  110. 	cout << endl;
  111. 	//后序遍历
  112. 	printf("后序遍历为:");
  113. 	Porder(root);
  114. 	cout << endl;
  115. 	x = CountLeafNode(root);
  116. 	cout << "该二叉树的叶子结点数为：" << x << endl;
  117. 	system("pause");
  118. 	return 0;
  119. }

3.5.2返回一棵二叉树的层数

  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4.  
  5. typedef struct Node{
  6. 	int data;
  7. 	struct Node *left, *right;
  8. }BTNode;
  9.  
  10. //创建二叉树
  11. BTNode *CreateBTtree(int a[], int n)
  12. {
  13. 	BTNode *root, *c, *pa = NULL, *p;
  14. 	int i;
  15. 	root = new BTNode;
  16. 	root->data = a[0];
  17. 	root->left = root->right = NULL;
  18. 	for (i = 1; i<n; i++)
  19. 	{
  20. 		p = new BTNode;
  21. 		p->left = p->right = NULL;
  22. 		p->data = a[i];
  23. 		c = root;
  24. 		while (c)
  25. 		{
  26. 			pa = c;
  27. 			if (c->data<p->data)
  28. 				c = c->right;
  29. 			else
  30. 				c = c->left;
  31. 		}
  32. 		if (pa->data<p->data)
  33. 			pa->right = p;
  34. 		else
  35. 			pa->left = p;
  36. 	}
  37. 	return root;
  38. }
  39.  
  40. //前序遍历
  41. void Forder(BTNode *root)
  42. {
  43. 	if (root)
  44. 	{
  45. 		cout << setw(5) << root->data;
  46. 		Forder(root->left);
  47. 		Forder(root->right);
  48. 	}
  49. }
  50.  
  51. //中序遍历
  52. void Inorder(BTNode *root)
  53. {
  54. 	if (root)
  55. 	{
  56. 		Inorder(root->left);
  57. 		cout << setw(5) << root->data;
  58. 		Inorder(root->right);
  59. 	}
  60. }
  61.  
  62. //后序遍历
  63. void Porder(BTNode *root)
  64. {
  65. 	if (root)
  66. 	{
  67. 		Porder(root->left);
  68. 		Porder(root->right);
  69. 		cout << setw(5) << root->data;
  70. 	}
  71. }
  72.  
  73. //返回二叉树的层数
  74. int BTtree(BTNode *root)
  75. {
  76. 	int c1, c2, c;
  77. 	if (!root)
  78. 		return 0;
  79. 	else
  80. 	{
  81. 		c1 = BTtree(root->left);
  82. 		c2 = BTtree(root->right);
  83. 		c = c1>c2 ? c1 : c2;
  84. 		return c + 1;
  85. 	}
  86. }
  87. int main()
  88. {
  89. 	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
  90. 	BTNode *root;
  91. 	int x;
  92. 	root = CreateBTtree(a, 8);
  93. 	//前序遍历
  94. 	printf("前序遍历为:");
  95. 	Forder(root);
  96. 	cout << endl;
  97. 	//中序遍历
  98. 	printf("中序遍历为:");
  99. 	Inorder(root);
  100. 	cout << endl;
  101. 	//后序遍历
  102. 	printf("后序遍历为:");
  103. 	Porder(root);
  104. 	cout << endl;
  105. 	//计算层数
  106. 	x = BTtree(root);
  107. 	cout << "该二叉树层数为：" << x << endl;
  108. 	system("pause");
  109. 	return 0;
  110. }

3.5.3查找Key值（节点不重复）

  1. /*查找Key值的地址*/
  2. #include<iostream>
  3. #include<iomanip>
  4. using namespace std;
  5.  
  6. typedef struct Node{
  7. 	int data;
  8. 	struct Node *left, *right;
  9. }BTNode;
  10.  
  11. //创建二叉树
  12. BTNode *CreateBTtree(int a[], int n)
  13. {
  14. 	BTNode *root, *c, *pa = NULL, *p;
  15. 	int i;
  16. 	root = (BTNode *)malloc(sizeof(BTNode));
  17. 	root->data = a[0];
  18. 	root->left = root->right = NULL;
  19. 	for (i = 1; i<n; i++)
  20. 	{
  21. 		p = (BTNode *)malloc(sizeof(BTNode));
  22. 		p->left = p->right = NULL;
  23. 		p->data = a[i];
  24. 		c = root;
  25. 		while (c)
  26. 		{
  27. 			pa = c;
  28. 			if (c->data<p->data)
  29. 				c = c->right;
  30. 			else
  31. 				c = c->left;
  32. 		}
  33. 		if (pa->data<p->data)
  34. 			pa->right = p;
  35. 		else
  36. 			pa->left = p;
  37. 	}
  38. 	return root;
  39. }
  40.  
  41. //前序遍历
  42. void Forder(BTNode *root)
  43. {
  44. 	if (root)
  45. 	{
  46. 		cout << setw(5) << root->data;
  47. 		Forder(root->left);
  48. 		Forder(root->right);
  49. 	}
  50. }
  51.  
  52. //中序遍历
  53. void Inorder(BTNode *root)
  54. {
  55. 	if (root)
  56. 	{
  57. 		Inorder(root->left);
  58. 		cout << setw(5) << root->data;
  59. 		Inorder(root->right);
  60. 	}
  61. }
  62.  
  63. //后序遍历
  64. void Porder(BTNode *root)
  65. {
  66. 	if (root)
  67. 	{
  68. 		Porder(root->left);
  69. 		Porder(root->right);
  70. 		cout << setw(5) << root->data;
  71. 	}
  72. }
  73.  
  74. BTNode *FindNode(BTNode *root, int key)
  75. {
  76. 	if (!root)
  77. 		return NULL;
  78. 	else if (root->data == key)
  79. 		return root;
  80. 	else if (key<root->data)
  81. 		return FindNode(root->left, key);
  82. 	else
  83. 		return FindNode(root->right, key);
  84. }
  85.  
  86. int main()
  87. {
  88. 	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
  89. 	BTNode *root, *p;
  90. 	int key;
  91. 	printf("任意键入一个key值：");
  92. 	cin>>key;
  93.  
  94. 	root = CreateBTtree(a, 8);
  95. 	//前序遍历
  96. 	printf("前序遍历为:");
  97. 	Forder(root);
  98. 	cout << endl;
  99. 	//中序遍历
  100. 	printf("中序遍历为:");
  101. 	Inorder(root);
  102. 	cout << endl;
  103. 	//后序遍历
  104. 	printf("后序遍历为:");
  105. 	Porder(root);
  106. 	cout << endl;
  107. 	p = FindNode(root, key);
  108. 	//输出Key值的地址
  109. 	cout << "key值地址为："<< p << endl;
  110. 	system("pause");
  111. 	return 0;
  112. }

3.5.4复制一棵二叉树

  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4.  
  5. typedef struct Node{
  6. 	int data;
  7. 	struct Node *left, *right;
  8. }BTNode;
  9.  
  10. //创建二叉树
  11. BTNode *CreateBTtree(int a[], int n)
  12. {
  13. 	BTNode *root, *c, *pa = NULL, *p;
  14. 	int i;
  15. 	root = new BTNode;
  16. 	root->data = a[0];
  17. 	root->left = root->right = NULL;
  18. 	for (i = 1; i<n; i++)
  19. 	{
  20. 		p = new BTNode;
  21. 		p->left = p->right = NULL;
  22. 		p->data = a[i];
  23. 		c = root;
  24. 		while (c)
  25. 		{
  26. 			pa = c;
  27. 			if (c->data<p->data)
  28. 				c = c->right;
  29. 			else
  30. 				c = c->left;
  31. 		}
  32. 		if (pa->data<p->data)
  33. 			pa->right = p;
  34. 		else
  35. 			pa->left = p;
  36. 	}
  37. 	return root;
  38. }
  39.  
  40. //复制一棵二叉树
  41. BTNode *BTcopy(BTNode *root)
  42. {
  43. 	BTNode * p = NULL;
  44. 	if (root)
  45. 	{
  46. 		p = (BTNode *)malloc(sizeof(BTNode));
  47. 		p->data = root->data;
  48. 		p->left = p->right = NULL;
  49. 		if (root->left)
  50. 			p->left = BTcopy(root->left);
  51. 		if (root->right)
  52. 			p->right = BTcopy(root->right);
  53. 	}
  54. 	return p;
  55. }
  56.  
  57. //前序遍历
  58. void Forder(BTNode *root)
  59. {
  60. 	if (root)
  61. 	{
  62. 		cout << setw(5) << root->data;
  63. 		Forder(root->left);
  64. 		Forder(root->right);
  65. 	}
  66. }
  67.  
  68. //中序遍历
  69. void Inorder(BTNode *root)
  70. {
  71. 	if (root)
  72. 	{
  73. 		Inorder(root->left);
  74. 		cout << setw(5) << root->data;
  75. 		Inorder(root->right);
  76. 	}
  77. }
  78.  
  79. //后序遍历
  80. void Porder(BTNode *root)
  81. {
  82. 	if (root)
  83. 	{
  84. 		Porder(root->left);
  85. 		Porder(root->right);
  86. 		cout << setw(5) << root->data;
  87. 	}
  88. }
  89.  
  90.  
  91.  
  92.  
  93. int main()
  94. {
  95. 	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
  96. 	BTNode *root, *p;
  97. 	root = CreateBTtree(a, 8);
  98.  
  99. 	//前序遍历
  100. 	cout << "前序遍历为:";
  101. 	Forder(root);
  102. 	cout << endl;
  103. 	//中序遍历
  104. 	cout << "中序遍历为:";
  105. 	Inorder(root);
  106. 	cout << endl;
  107. 	//后序遍历
  108. 	cout<<"后序遍历为:";
  109. 	Porder(root);
  110. 	cout << endl;
  111. 	
  112. 	
  113. 	p = BTcopy(root);
  114. 	cout<<"复制后的前序遍历为:";
  115. 	Forder(p);
  116. 	cout << endl;
  117. 	system("pause");
  118. 	return 0;
  119. }

 

3.5.5层次遍历二叉树

  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. #define N 8
  5.  
  6. typedef struct Node{
  7. 	int data;
  8. 	struct Node *left, *right;
  9. }BTNode;
  10.  
  11. //创建完全二叉树
  12. BTNode *CreateBTtree(int a[])
  13. {
  14. 	BTNode *root, *pa, *p;
  15. 	BTNode **Q;
  16. 	int i;
  17. 	int front, rear;
  18. 	front = rear = 0;
  19. 	//创建队列
  20. 	Q = (BTNode **)malloc((N + 1)*sizeof(BTNode*));
  21. 	//创建根结点
  22. 	pa = root = (BTNode *)malloc(sizeof(BTNode));
  23. 	root->data = a[0];
  24. 	root->left = root->right = NULL;
  25. 	for (i = 1; i<N; i++)
  26. 	{
  27. 		p = (BTNode *)malloc(sizeof(BTNode));
  28. 		p->data = a[i];
  29. 		p->left = p->right = NULL;
  30. 		Q[++rear] = p;
  31. 		if (pa->left == NULL)
  32. 			pa->left = p;
  33. 		else
  34. 		{
  35. 			pa->right = p;
  36. 			pa = Q[++front];
  37. 		}
  38. 	}
  39. 	free(Q);
  40. 	return root;
  41. }
  42.  
  43. //按层遍历
  44. void levelorder(BTNode *root)
  45. {
  46. 	int front, rear;
  47. 	BTNode ** Q;
  48. 	BTNode * p;
  49. 	//声明队列
  50. 	Q = (BTNode **)malloc((N + 1)*sizeof(BTNode *));
  51. 	//初始化队列
  52. 	front = rear = 0;
  53. 	Q[++rear] = root;
  54. 	//按层输出
  55. 	while (front - rear)
  56. 	{
  57. 		p = Q[++front];  //出队
  58. 		cout << setw(5) << p->data;
  59. 		if (p->left)
  60. 			Q[++rear] = p->left;
  61. 		if (p->right)
  62. 			Q[++rear] = p->right;
  63. 	}
  64. 	free(Q);
  65. }
  66.  
  67.  
  68. int main()
  69. {
  70. 	int a[N] = { 5, 3, 7, 2, 4, 6, 8, 9 };
  71. 	BTNode *root;
  72. 	root = CreateBTtree(a);
  73. 	//按层遍历
  74. 	cout << "按层遍历结果为：" << endl;
  75. 	levelorder(root);
  76. 	cout << endl;
  77. 	system("pause");
  78. 	return 0;
  79. }

3.5.6镜像二叉树

  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. #define N 8
  5. #define null 0
  6.  
  7. typedef struct node{
  8. 	int data;
  9. 	struct node *left;
  10. 	struct node *right;
  11. }BTNode;
  12.  
  13. //创建二叉树
  14. BTNode *GreatBtree(int[], int);
  15. //生成一棵二叉树的镜像树
  16. void MirrorTree(BTNode *);
  17.  
  18. //按层遍历
  19. void levelorder(BTNode *root)
  20. {
  21. 	int front, rear;
  22. 	BTNode ** Q;
  23. 	BTNode * p;
  24. 	//声明队列
  25. 	Q = (BTNode **)malloc((N + 1)*sizeof(BTNode *));
  26. 	//初始化队列
  27. 	front = rear = 0;
  28. 	Q[++rear] = root;
  29. 	//按层输出
  30. 	while (front - rear)
  31. 	{
  32. 		p = Q[++front];  //出队
  33. 		cout << setw(5) << p->data;
  34. 		if (p->left)
  35. 			Q[++rear] = p->left;
  36. 		if (p->right)
  37. 			Q[++rear] = p->right;
  38. 	}
  39. 	free(Q);
  40. }
  41.  
  42.  
  43. int main()
  44. {
  45. 	int a[N] = { 5, 3, 7, 2, 4, 6, 8, 9 };
  46. 	BTNode *root;
  47. 	root = GreatBtree(a, N);
  48. 	cout << "按层遍历（镜像前）：" << endl;
  49. 	levelorder(root);
  50. 	cout << endl;
  51.  
  52. 	MirrorTree(root);
  53. 	cout << "按层遍历（镜像后）：" << endl;
  54. 	levelorder(root);
  55. 	cout << endl;
  56. 	system("pause");
  57. 	return 0;
  58. }
  59. BTNode *GreatBtree(int a[], int n)
  60. {
  61. 	BTNode *root = null, *p, *c, *q = NULL;
  62. 	int i;
  63. 	for (i = 0; i<n; i++){
  64. 		//创建一个结点
  65. 		p = (BTNode *)malloc(sizeof(BTNode));
  66. 		p->left = p->right = null;
  67. 		p->data = a[i];
  68. 		if (root){
  69. 			c = root;
  70. 			while (c){
  71. 				q = c;
  72. 				if (p->data <= c->data){
  73. 					c = c->left;
  74. 				}
  75. 				else{
  76. 					c = c->right;
  77. 				}
  78. 			}
  79. 			if (p->data <= q->data){
  80. 				q->left = p;
  81. 			}
  82. 			else{
  83. 				q->right = p;
  84. 			}
  85. 		}
  86. 		else{
  87. 			root = p;
  88. 		}
  89. 	}
  90. 	return root;
  91. }
  92.  
  93.  
  94. //镜像树即只有根结点不变
  95. //其余所有左子女与右子女对调位置
  96. //缺点:直接改变了原二叉树
  97. //改进方法先拷贝后镜像即可
  98. void MirrorTree(BTNode *root)
  99. {
  100. 	BTNode *middle;
  101. 	if (!root){
  102. 		return;
  103. 	}
  104. 	else{
  105. 		MirrorTree(root->left);
  106. 		MirrorTree(root->right);
  107. 		middle = root->left;
  108. 		root->left = root->right;
  109. 		root->right = middle;
  110. 	}
  111. }
  112.  
  113. //拷贝二叉树
  114. BTNode *CopyBT(BTNode *root)
  115. {
  116. 	BTNode *p = null;
  117. 	if (root){
  118. 		p = (BTNode *)malloc(sizeof(BTNode));
  119. 		p->data = root->data;
  120. 		p->left = CopyBT(root->left);
  121. 		p->right = CopyBT(root->right);
  122. 	}
  123. 	return p;
  124. }

3.5.7统计分支节点个数和单双分支节点个数

分支节点：度不为零的节点

双分支节点：拥有两个孩子的节点（度为2的节点）

单分支节点：拥有一个孩子的节点（度为1的节点）

  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. #define N 8
  5. #define null 0
  6.  
  7. typedef struct node{
  8. 	int data;
  9. 	struct node *left;
  10. 	struct node *right;
  11. }BTNode;
  12.  
  13. //创建二叉树
  14. BTNode *GreatBtree(int[], int);
  15. //统计二叉树双分支结点个数
  16. int CountDoubleNode(BTNode *);
  17. //统计二叉树单双分支结点总数
  18. int CountSingleAndDoubleNode(BTNode *);
  19.  
  20. int main()
  21. {
  22. 	int a[N] = { 5, 3, 7, 2, 4, 6, 8, 9 };
  23. 	BTNode *root;
  24. 	root = GreatBtree(a, N);
  25. 	cout << "Double's Node number:" << CountDoubleNode(root) << endl;
  26. 	cout << "Double's and single's Node number:" << CountSingleAndDoubleNode(root) << endl;
  27. 	system("pause");
  28. 	return 0;
  29. }
  30. BTNode *GreatBtree(int a[], int n)
  31. {
  32. 	BTNode *root = null, *p, *c, *q = NULL;
  33. 	int i;
  34. 	for (i = 0; i<n; i++){
  35. 		//创建一个结点
  36. 		p = (BTNode *)malloc(sizeof(BTNode));
  37. 		p->left = p->right = null;
  38. 		p->data = a[i];
  39. 		if (root){
  40. 			c = root;
  41. 			while (c){
  42. 				q = c;
  43. 				if (p->data <= c->data){
  44. 					c = c->left;
  45. 				}
  46. 				else{
  47. 					c = c->right;
  48. 				}
  49. 			}
  50. 			if (p->data <= q->data){
  51. 				q->left = p;
  52. 			}
  53. 			else{
  54. 				q->right = p;
  55. 			}
  56. 		}
  57. 		else{
  58. 			root = p;
  59. 		}
  60. 	}//for
  61. 	return root;
  62. }
  63. int CountLeafNode(BTNode *root)
  64. {
  65. 	if (!root){
  66. 		return 0;
  67. 	}
  68. 	else{
  69. 		return CountLeafNode(root->left) + CountLeafNode(root->right) + !(root->left || root->right);
  70. 	}
  71. }
  72. //双分支结点满足有左子女和右子女
  73. int CountDoubleNode(BTNode *root)
  74. {
  75. 	if (!root){
  76. 		return 0;
  77. 	}
  78. 	else{
  79. 		return CountDoubleNode(root->left) + CountDoubleNode(root->right) + (root->left&&root->right);//此处&&优先级最低
  80. 	}
  81. }
  82. int CountSingleAndDoubleNode(BTNode *root)
  83. {
  84. 	if (!root){
  85. 		return 0;
  86. 	}
  87. 	else{
  88. 		return CountSingleAndDoubleNode(root->left) + CountSingleAndDoubleNode(root->right) + (root->left || root->right);
  89. 	}
  90. }

3.5.8创建一棵完全二叉树

  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4. #define N 14
  5.  
  6. typedef struct Node{
  7. 	int data;
  8. 	struct Node *left, *right;
  9. }BTNode;
  10.  
  11. //创建一棵完全二叉树
  12. BTNode *CreateBTtree(int a[])
  13. {
  14. 	BTNode *root, *pa, *p;
  15. 	BTNode **Q;
  16. 	int i;
  17. 	int front, rear;
  18. 	front = rear = 0;
  19. 	//创建队列
  20. 	Q = (BTNode **)malloc((N + 1)*sizeof(BTNode*));
  21. 	//创建根结点
  22. 	pa = root = (BTNode *)malloc(sizeof(BTNode));
  23. 	root->data = a[0];
  24. 	root->left = root->right = NULL;
  25. 	for (i = 1; i<N; i++)
  26. 	{
  27. 		p = (BTNode *)malloc(sizeof(BTNode));
  28. 		p->data = a[i];
  29. 		p->left = p->right = NULL;
  30. 		Q[++rear] = p;
  31. 		if (pa->left == NULL)
  32. 			pa->left = p;
  33. 		else
  34. 		{
  35. 			pa->right = p;
  36. 			pa = Q[++front];
  37. 		}
  38. 	}
  39. 	free(Q);
  40. 	return root;
  41. }
  42.  
  43. //按层遍历
  44. void levelorder(BTNode *root)
  45. {
  46. 	int front, rear;
  47. 	BTNode ** Q;
  48. 	BTNode * p;
  49. 	//声明队列
  50. 	Q = (BTNode **)malloc((N + 1)*sizeof(BTNode *));
  51. 	//初始化队列
  52. 	front = rear = 0;
  53. 	Q[++rear] = root;
  54. 	//按层输出
  55. 	while (front - rear)
  56. 	{
  57. 		p = Q[++front];  //出队
  58. 		cout << setw(5) << p->data;
  59. 		if (p->left)
  60. 			Q[++rear] = p->left;
  61. 		if (p->right)
  62. 			Q[++rear] = p->right;
  63. 	}
  64. 	free(Q);
  65. }
  66.  
  67. //前序遍历
  68. void Forder(BTNode *root)
  69. {
  70. 	if (root)
  71. 	{
  72. 		cout << setw(5) << root->data;
  73. 		Forder(root->left);
  74. 		Forder(root->right);
  75. 	}
  76. }
  77.  
  78. //中序遍历
  79. void Inorder(BTNode *root)
  80. {
  81. 	if (root)
  82. 	{
  83. 		Inorder(root->left);
  84. 		cout << setw(5) << root->data;
  85. 		Inorder(root->right);
  86. 	}
  87. }
  88.  
  89. //后序遍历
  90. void Porder(BTNode *root)
  91. {
  92. 	if (root)
  93. 	{
  94. 		Porder(root->left);
  95. 		Porder(root->right);
  96. 		cout << setw(5) << root->data;
  97. 	}
  98. }
  99.  
  100.  
  101. int main()
  102. {
  103. 	//int a[N]={3,2,13,8,12,7,9,1,6,11,4,5};
  104. 	int a[N] = { 14, 23, 24, 32, 42, 51, 58, 62, 65, 73, 80, 99, 120, 3942 };
  105. 	BTNode *root;
  106. 	root = CreateBTtree(a);
  107.  
  108. 	//按层遍历
  109. 	cout << "按层遍历：";
  110. 	levelorder(root);
  111. 	cout << endl;
  112.  
  113. 	//前序遍历
  114. 	cout << "前序遍历：";
  115. 	Forder(root);
  116. 	cout << endl;
  117.  
  118. 	//中序遍历
  119. 	cout << "中序遍历：";
  120. 	Inorder(root);
  121. 	cout << endl;
  122.  
  123. 	//后序遍历
  124. 	cout << "后序遍历：";
  125. 	Porder(root);
  126. 	cout << endl;
  127.  
  128. 	system("pause");
  129. 	return 0;
  130. }

结果：

由此可绘制出这棵完全二叉树

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

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

  

闽ICP备14008679号