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

二叉树的初始化·数据结构_二叉树初始化

作者：笔触狂放9 | 2024-07-24 22:16:03

赞

踩

二叉树初始化

二叉树是什么？

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分

思路：

首先，需要创建一个BTNode的结点，结点包含了数据，两个指针——lchild和rchild，再一个BTNode的构造函数，来初始化结点
接着，创建二叉树的类，类包含了头结点，以及各函数的实现操作。（初始化函数、创建树函数、遍历函数、求树的结点个数、求树的叶子数、求树的深度）

代码如下：

  1. using namespace std;
  2. typedef int Element;
  3.  
  4. //定义结点
  5. struct BTNode {
  6. 	Element data;
  7. 	BTNode* lchild;
  8. 	BTNode* rchild;
  9. 	//结构体的构造函数
  10. 	BTNode(Element number) {
  11. 		data = number;
  12. 		lchild = NULL;
  13. 		rchild = NULL;
  14. 	}
  15. };
  16.  
  17. //定义二叉树类
  18. class Btree {
  19. public:
  20. 	BTNode* Root;
  21. 	//初始化创建树头
  22. 	void Init() {
  23. 		Root = CreatBTree();
  24. 		cout << "树创建成功" << endl;
  25. 	}
  26.  
  27. 	//创建树(前序)
  28. 	BTNode* CreatBTree() {
  29. 		BTNode* p;
  30. 		Element number;
  31. 		cin >> number;
  32. 		if (number == 0)
  33. 			p = NULL;
  34. 		else {
  35. 			p = new BTNode(number);
  36. 			p->lchild = CreatBTree();
  37. 			p->rchild = CreatBTree();
  38. 		}
  39. 		return p;
  40. 	}
  41. 	
  42. 	//前序遍历
  43. 	void preOrderTraverse(BTNode *root) {
  44. 		if (root) {
  45. 			cout << root->data << " ";
  46. 			preOrderTraverse(root->lchild);
  47. 			preOrderTraverse(root->rchild);
  48. 		}
  49. 	}
  50.  
  51. 	//中序遍历
  52. 	void inOrderTraverse(BTNode* root) {
  53. 		if (root) {
  54. 			inOrderTraverse(root->lchild);
  55. 			cout << root->data << " ";
  56. 			inOrderTraverse(root->rchild);
  57. 		}
  58. 	}
  59.  
  60. 	//后序遍历
  61. 	void lastOrderTraverse(BTNode* root) {
  62. 		if (root) {
  63. 			lastOrderTraverse(root->lchild);
  64. 			lastOrderTraverse(root->rchild);
  65. 			cout << root->data << " ";
  66. 		}
  67. 	}
  68.  
  69. 	//求叶子结点个数
  70. 	int LeafNum(BTNode* root) {
  71. 		if (root == NULL) {
  72. 			return 0;
  73. 		}
  74. 		else if (root->lchild == NULL && root->rchild == NULL)
  75. 			return 1;
  76. 		else
  77. 			return LeafNum(root->lchild) + LeafNum(root->rchild);
  78. 	}
  79.  
  80. 	//求树的结点个数
  81. 	int BTNodeNum(BTNode* root) {
  82. 		if (root == NULL)
  83. 			return 0;
  84. 		else
  85. 			return BTNodeNum(root->lchild) + BTNodeNum(root->rchild) + 1;
  86. 	}
  87.  
  88. 	//求树的深度
  89. 	int TreeDepth(BTNode* root) {
  90. 		if (root == NULL)
  91. 			return 0;
  92. 		int left = TreeDepth(root->lchild);
  93. 		int right = TreeDepth(root->rchild);
  94. 		return left > right ? left + 1 : right + 1;
  95. 	}
  96. };
  97.  
  98. int main()
  99. {
  100. 	Btree T;
  101.  
  102. 	//初始化
  103. 	T.Init();
  104.  
  105. 	//遍历
  106. 	cout << "前序遍历为：" << endl;
  107. 	T.preOrderTraverse(T.Root);
  108. 	cout << endl;
  109. 	cout << "中序遍历为：" << endl;
  110. 	T.inOrderTraverse(T.Root);
  111. 	cout << endl;
  112. 	cout << "后序遍历为：" << endl;
  113. 	T.lastOrderTraverse(T.Root);
  114. 	cout << endl;
  115.  
  116. 	//树的结点个数
  117. 	cout << "树的结点个数为：";
  118. 	int nodenum = T.BTNodeNum(T.Root);
  119. 	cout << nodenum << endl;
  120.  
  121. 	//树的叶子个数
  122. 	cout << "树的叶子个数为：";
  123. 	int leaves = T.LeafNum(T.Root);
  124. 	cout << leaves << endl;
  125.  
  126. 	//树的深度为：
  127. 	cout << "树的深度为：";
  128. 	int depth = T.TreeDepth(T.Root);
  129. 	cout << depth << endl;
  130.  
  131. 	system("pause");
  132. 	cout << endl;
  133. }

二叉树的非递归算法1——中序遍历非递归算法:
步骤介绍：

1.初始化一个空栈s，指针p指向根节点

2.申请一个空间来存放栈顶弹出的元素

3.当p非空或栈s非空时，循环以下步骤：

（一）如果p非空，入栈p结点，p指向p的左孩子

（二）如果p为空，则弹出栈顶元素并cout，p指向q的右孩子

  1. 	void Traverse(BTNode* root) {
  2. 		//创建栈
  3. 		stack<BTNode*>s;
  4. 		BTNode* p = root;
  5. 		BTNode* q = NULL;
  6. 		while (p || !empty(s)) {
  7. 			if (p) {
  8. 				s.push(p);
  9. 				p = p->lchild;
  10. 			}
  11. 			else {
  12. 				q = s.top();
  13. 				cout << q->data << " ";
  14. 				s.pop();
  15. 				p = q->rchild;
  16. 			}
  17. 		}
  18.  
  19. 	}

二叉树的非递归算法2——层次遍历二叉树：
步骤介绍：

1.将根节点入队；

2.若队列不为空时，出队队头结点p，进行以下循环：

（一）若p有左孩子（左孩子不为空），入队它的左孩子

（二）若p有右孩子（右孩子不为空），入队它的右孩子

  1. 	void LevelOrder(BTNode* root) {
  2. 		//创建队列
  3. 		queue<BTNode*>q;
  4. 		BTNode* p;
  5. 		//先入队头结点
  6. 		q.push(root);
  7. 		//队不为空
  8. 		while (!q.empty()) {
  9. 			//取队头
  10. 			p = q.front();
  11. 			q.pop();
  12. 			cout << p->data << " ";
  13. 			//左孩子不为空
  14. 			if (p->lchild != NULL) {
  15. 				q.push(p->lchild);
  16. 			}
  17. 			//右孩子不为空
  18. 			if (p->rchild != NULL) {
  19. 				q.push(p->rchild);
  20. 			}
  21. 		}
  22. 	}

代码总和（2023.1.4更新版）

  1. #include<stack>
  2. #include<queue>
  3. using namespace std;
  4. typedef int Element;
  5.  
  6. //定义结点
  7. struct BTNode {
  8. 	Element data;
  9. 	BTNode* lchild;
  10. 	BTNode* rchild;
  11. 	//结构体的构造函数
  12. 	BTNode(Element number) {
  13. 		data = number;
  14. 		lchild = NULL;
  15. 		rchild = NULL;
  16. 	}
  17. };
  18.  
  19. //定义二叉树类
  20. class Btree {
  21. public:
  22. 	BTNode* Root;
  23. 	//初始化创建树头
  24. 	void Init() {
  25. 		Root = CreatBTree();
  26. 		cout << "树创建成功" << endl;
  27. 	}
  28.  
  29. 	//创建树(前序)
  30. 	BTNode* CreatBTree() {
  31. 		BTNode* p;
  32. 		Element number;
  33. 		cin >> number;
  34. 		if (number == 0)
  35. 			p = NULL;
  36. 		else {
  37. 			p = new BTNode(number);
  38. 			p->lchild = CreatBTree();
  39. 			p->rchild = CreatBTree();
  40. 		}
  41. 		return p;
  42. 	}
  43. 	
  44. 	//前序遍历
  45. 	void preOrderTraverse(BTNode *root) {
  46. 		if (root) {
  47. 			cout << root->data << " ";
  48. 			preOrderTraverse(root->lchild);
  49. 			preOrderTraverse(root->rchild);
  50. 		}
  51. 	}
  52.  
  53. 	//中序遍历
  54. 	void inOrderTraverse(BTNode* root) {
  55. 		if (root) {
  56. 			inOrderTraverse(root->lchild);
  57. 			cout << root->data << " ";
  58. 			inOrderTraverse(root->rchild);
  59. 		}
  60. 	}
  61.  
  62. 	//后序遍历
  63. 	void lastOrderTraverse(BTNode* root) {
  64. 		if (root) {
  65. 			lastOrderTraverse(root->lchild);
  66. 			lastOrderTraverse(root->rchild);
  67. 			cout << root->data << " ";
  68. 		}
  69. 	}
  70.  
  71. 	//求叶子结点个数
  72. 	int LeafNum(BTNode* root) {
  73. 		if (root == NULL) {
  74. 			return 0;
  75. 		}
  76. 		else if (root->lchild == NULL && root->rchild == NULL)
  77. 			return 1;
  78. 		else
  79. 			return LeafNum(root->lchild) + LeafNum(root->rchild);
  80. 	}
  81.  
  82. 	//求树的结点个数
  83. 	int BTNodeNum(BTNode* root) {
  84. 		if (root == NULL)
  85. 			return 0;
  86. 		else
  87. 			return BTNodeNum(root->lchild) + BTNodeNum(root->rchild) + 1;
  88. 	}
  89.  
  90. 	//求树的深度
  91. 	int TreeDepth(BTNode* root) {
  92. 		if (root == NULL)
  93. 			return 0;
  94. 		int left = TreeDepth(root->lchild);
  95. 		int right = TreeDepth(root->rchild);
  96. 		return left > right ? left + 1 : right + 1;
  97. 	}
  98.  
  99. 	//中序遍历非递归
  100. 	void Traverse(BTNode* root) {
  101. 		//创建栈
  102. 		stack<BTNode*>s;
  103. 		BTNode* p = root;
  104. 		BTNode* q = NULL;
  105. 		while (p || !empty(s)) {
  106. 			if (p) {
  107. 				s.push(p);
  108. 				p = p->lchild;
  109. 			}
  110. 			else {
  111. 				q = s.top();
  112. 				cout << q->data << " ";
  113. 				s.pop();
  114. 				p = q->rchild;
  115. 			}
  116. 		}
  117.  
  118. 	}
  119.  
  120. 	//二叉树层次遍历算法
  121. 	void LevelOrder(BTNode* root) {
  122. 		//创建队列
  123. 		queue<BTNode*>q;
  124. 		BTNode* p;
  125. 		//先入队头结点
  126. 		q.push(root);
  127. 		//队不为空
  128. 		while (!q.empty()) {
  129. 			//取队头
  130. 			p = q.front();
  131. 			q.pop();
  132. 			cout << p->data << " ";
  133. 			//左孩子不为空
  134. 			if (p->lchild != NULL) {
  135. 				q.push(p->lchild);
  136. 			}
  137. 			//右孩子不为空
  138. 			if (p->rchild != NULL) {
  139. 				q.push(p->rchild);
  140. 			}
  141. 		}
  142. 	}
  143. };
  144.  
  145. int main()
  146. {
  147.  
  148. 	Btree T;
  149.  
  150. 	//初始化
  151. 	T.Init();
  152.  
  153. 	//遍历
  154. 	cout << "前序遍历为：" << endl;
  155. 	T.preOrderTraverse(T.Root);
  156. 	cout << endl;
  157. 	cout << "中序遍历为：" << endl;
  158. 	T.inOrderTraverse(T.Root);
  159. 	cout << endl;
  160. 	cout << "后序遍历为：" << endl;
  161. 	T.lastOrderTraverse(T.Root);
  162. 	cout << endl;
  163.  
  164. 	//树的结点个数
  165. 	cout << "树的结点个数为：";
  166. 	int nodenum = T.BTNodeNum(T.Root);
  167. 	cout << nodenum << endl;
  168.  
  169. 	//树的叶子个数
  170. 	cout << "树的叶子个数为：";
  171. 	int leaves = T.LeafNum(T.Root);
  172. 	cout << leaves << endl;
  173.  
  174. 	//树的深度为：
  175. 	cout << "树的深度为：";
  176. 	int depth = T.TreeDepth(T.Root);
  177. 	cout << depth << endl;
  178.  
  179. 	//树的中序非递归遍历
  180. 	cout << "树的中序非递归遍历：" << endl;
  181. 	T.Traverse(T.Root);
  182. 	cout << endl;
  183.  
  184. 	//树的层次遍历算法
  185. 	cout << "树的层次遍历算法：" << endl;
  186. 	T.LevelOrder(T.Root);
  187. 	cout << endl;
  188.  
  189. 	system("pause");
  190. 	cout << endl;
  191. }

结果测试：

 

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

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

  

闽ICP备14008679号