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

C++ 二叉树(建立、销毁、前中后序遍历和层次遍历，寻找双亲结点等)_c++ 树 销毁

作者：Cpp五条 | 2024-05-25 11:56:22

赞

踩

c++ 树 销毁

（1）结构体和类定义

  1. struct BTreeNode {
  2. 	T data;
  3. 	BTreeNode* left, * right;
  4. 	BTreeNode() :data(0), left(nullptr), right(nullptr) {}
  5. 	BTreeNode(T val, BTreeNode<T>* leftChild = nullptr, BTreeNode<T>* rightChild = nullptr)
  6. 		:data(val), left(leftChild), right(rightChild) {}
  7.  
  8. };
  9.  
  10. template<class T>
  11. class BTree {
  12. public:
  13. 	BTree() :root(nullptr) {}										      // 构造函数
  14. 	BTree(string str);                                                    // 重载
  15.  
  16. 	void createTree(BTreeNode<T>*& bt, string str);                       // 创建二次树
  17. 	~BTree();														      // 析构函数
  18. 	bool IsEmpty();													      // 判二叉树空否？
  19. 	int Size(BTreeNode<T>* cur);                                          // 计算结点个数
  20. 	int getSize();                                                        // 获取结点个数
  21. 	BTreeNode<T>* getData(T& item, BTreeNode<T>* cur);	                  // 取得结点数据
  22. 	bool Find(T& item);		                                              // 判断item是否在树中
  23. 	int Height(BTreeNode<T>* bt);                                         // 求树高度
  24. 	int getHeight();                                                      // 获取树高度
  25. 	BTreeNode<T>* getRoot();	                                          // 取根
  26.  
  27. 	void preOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);          // 前序遍历
  28. 	void inOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);		      // 中序遍历
  29. 	void postOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);         // 后序遍历
  30. 	void levelOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);        // 层序遍历
  31.  
  32. 	vector<T> preOrder();						                          // 调用前序遍历，返回vector
  33. 	vector<T> inOrder();											      // 调用中序遍历，返回vector
  34. 	vector<T> postOrder();											      // 调用后序遍历，返回vector
  35. 	vector<T> levelOrder();                                               // 调用层序遍历，返回vector
  36.  
  37. 	void CopyTree(BTreeNode<T>* root, BTreeNode<T>*& copyRoot);           // 二叉树复制
  38. 	void Copy(BTreeNode<T>*& copyRoot);                                   // 调用二叉树复制
  39. 	void destroyCopyTree(BTreeNode<T>*& copyRoot);                        // 销毁复制二叉树
  40.  
  41.  
  42. 	BTreeNode<T>* FindParent(BTreeNode<T>* root, BTreeNode<T>* node);     // 寻找双亲
  43. 	BTreeNode<T>* LeftChild(BTreeNode<T>* node) {                         //求结点 node 的左孩子
  44. 		return (node != nullptr) ? node->left : nullptr;
  45. 	}
  46. 	BTreeNode<T>* RightChild(BTreeNode<T>* node) {                        //求结点 node 的右孩子
  47. 		return (node != nullptr) ? node->right : nullptr;
  48. 	}
  49.  
  50. protected:
  51. 	BTreeNode<T>* root;
  52. 	void destroyTree(BTreeNode<T>* node);                                // 销毁二叉树
  53. };

（2）创建二叉树

  1. template<class T>
  2. BTree<T>::BTree(string str) {
  3. 	createTree(root, str);
  4. 	cout << "报告：创建一颗二叉树，完成！！！" << endl;
  5. }
  6.  
  7. template<class T>
  8. void BTree<T>::createTree(BTreeNode<T>*& bt, string str) {
  9. 	static int i = 0;
  10. 	char ch = ' ';
  11. 	ch = str[i++];
  12.  
  13. 	if (ch == '#') bt = nullptr;
  14. 	else {
  15. 		bt = new BTreeNode<T>(ch);
  16. 		createTree(bt->left, str);
  17. 		createTree(bt->right, str);
  18. 	}
  19. };

（3）前中后序遍历和层序遍历

  1. // 前序遍历
  2. template<class T>
  3. void BTree<T>::preOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
  4. 	if (cur == nullptr)
  5. 		return;
  6. 	vec.push_back(cur->data);           // 中
  7. 	preOrderTraversal(cur->left, vec);  // 左
  8. 	preOrderTraversal(cur->right, vec); // 右
  9. }
  10.  
  11. // 调用前序遍历，返回vector
  12. template<class T>
  13. vector<T> BTree<T>::preOrder() {
  14. 	cout << "获取前序遍历数组...." << endl;
  15. 	cout << ">>>>";
  16. 	vector<T> resVec;
  17. 	preOrderTraversal(root, resVec);
  18. 	return resVec;
  19. }
  20.  
  21. // 中序遍历
  22. template<class T>
  23. void BTree<T>::inOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
  24. 	if (cur == nullptr)
  25. 		return;
  26. 	inOrderTraversal(cur->left, vec);  // 左
  27. 	vec.push_back(cur->data);          // 中
  28. 	inOrderTraversal(cur->right, vec); // 右
  29. }
  30.  
  31. // 调用中序遍历，返回vector
  32. template<class T>
  33. vector<T> BTree<T>::inOrder() {
  34. 	cout << "获取中序遍历数组...." << endl;
  35. 	cout << ">>>>";
  36. 	vector<T> resVec;
  37. 	inOrderTraversal(root, resVec);
  38. 	return resVec;
  39. }
  40.  
  41. // 后序遍历
  42. template<class T>
  43. void BTree<T>::postOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
  44. 	if (cur == nullptr)
  45. 		return;
  46. 	postOrderTraversal(cur->left, vec);  // 左
  47. 	postOrderTraversal(cur->right, vec); // 右
  48. 	vec.push_back(cur->data);            // 中
  49. }
  50.  
  51. // 调用后序遍历，返回vector
  52. template<class T>
  53. vector<T> BTree<T>::postOrder() {
  54. 	cout << "获取后序遍历数组...." << endl;
  55. 	cout << ">>>>";
  56. 	vector<T> resVec;
  57. 	postOrderTraversal(root, resVec);
  58. 	return resVec;
  59. }
  60.  
  61. // 层序遍历
  62. template<class T>
  63. void BTree<T>::levelOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
  64. 	if (cur == nullptr) return;
  65. 	queue<BTreeNode<T>*> Queue;
  66. 	BTreeNode<T>* p;
  67. 	Queue.push(cur); // 根结点入队列
  68. 	while (!Queue.empty()) {
  69. 		p = Queue.front();
  70. 		//cout << p->data << " ";//输出出队结点的数据
  71. 		vec.push_back(p->data);
  72. 		Queue.pop();
  73. 		if (p->left != nullptr) {
  74. 			Queue.push(p->left);
  75. 		}
  76. 		if (p->right != nullptr) {
  77. 			Queue.push(p->right);
  78. 		}
  79. 	}
  80. }
  81.  
  82. // 调用层序遍历，返回vector
  83. template<class T>
  84. vector<T> BTree<T>::levelOrder() {
  85. 	cout << "获取层序遍历数组...." << endl;
  86. 	cout << ">>>>";
  87. 	vector<T> resVec;
  88. 	levelOrderTraversal(root, resVec);
  89. 	return resVec;
  90. }

（4）复制二叉树

  1. template<class T>
  2. void BTree<T>::CopyTree(BTreeNode<T>* root, BTreeNode<T>*& copyRoot) {
  3. 	if (!root) {
  4. 		copyRoot = nullptr;
  5. 	}
  6. 	else {
  7. 		copyRoot = new BTreeNode<T>;
  8. 		copyRoot->data = root->data;           //复制根节点
  9. 		CopyTree(root->left, copyRoot->left);  //递归复制左子树
  10. 		CopyTree(root->right, copyRoot->right);//递归复制左子树
  11. 	}
  12. }
  13.  
  14. template<class T>
  15. void BTree<T>::Copy(BTreeNode<T>*& copyRoot) {
  16. 	CopyTree(root, copyRoot);
  17. }

（5）销毁二叉树

  1. template<class T>
  2. void BTree<T>::destroyCopyTree(BTreeNode<T>*& copyRoot) {
  3. 	destroyTree(copyRoot);
  4. 	cout << "报告，复制二叉树已销毁完毕!!!" << endl;
  5. }
  6.  
  7. // 销毁二叉树 
  8. template<class T>
  9. void BTree<T>::destroyTree(BTreeNode<T>* bt) {
  10. 	// 后序遍历删除根为subTree的子树；
  11. 	if (bt != nullptr) {
  12. 		destroyTree(bt->left);    //删除左子树
  13. 		destroyTree(bt->right);   //删除右子树
  14. 		delete bt; 			      //删除根结点
  15. 	}
  16. }

（6）析构函数

  1. // 析构函数
  2. template<class T>
  3. BTree<T>::~BTree<T>() {
  4. 	//cout << "调用析构函数" << endl;
  5. 	destroyTree(root);
  6. 	cout << "报告，这棵树已经销毁完毕!!!" << endl;
  7. }

（7）求树的高度

  1. // 求树高度
  2. template<class T>
  3. int BTree<T>::Height(BTreeNode<T>* bt) {
  4. 	if (bt == nullptr) return 0;
  5. 	else {
  6. 		int leftH = Height(bt->left);
  7. 		int rightH = Height(bt->right);
  8. 		return (leftH > rightH) ? leftH + 1 : rightH + 1;
  9. 	}
  10. }
  11.  
  12. // 获取树高度
  13. template<class T>
  14. int BTree<T>::getHeight() {
  15. 	return Height(root);
  16. }

（8）获取结点，判断其是否在二叉树中

  1. // 取得结点数据
  2. template<class T>
  3. BTreeNode<T>* BTree<T>::getData(T& item, BTreeNode<T>* cur) {
  4. 	if (cur == nullptr) return nullptr;
  5. 	if (cur->data == item) return cur;
  6. 	return getData(item, cur->left) != nullptr ? getData(item, cur->left) : getData(item, cur->right);
  7. }
  8.  
  9. // 判断item是否在树中
  10. template<class T>
  11. bool BTree<T>::Find(T& item) {
  12. 	if (this->getData(item, root) == nullptr) return false;
  13. 	else return true;

（9）计算结点个数和获取结点个数

  1. // 计算结点个数
  2. template<class T>
  3. int BTree<T>::Size(BTreeNode<T>* cur) {
  4. 	if (cur == nullptr)
  5. 		return 0;
  6. 	else
  7. 		return 1 + Size(cur->left) + Size(cur->right);
  8. }
  9.  
  10. // 获取结点个数
  11. template<class T>
  12. int BTree<T>::getSize() {
  13. 	return Size(root);
  14. }

（10）二叉树判空

  1. // 判二叉树空否？
  2. template<class T>
  3. bool BTree<T>::IsEmpty() {
  4. 	return (root == nullptr) ? true : false;
  5. }

（11）获取根结点

  1. // 获取根 
  2. template<class T>
  3. BTreeNode<T>* BTree<T>::getRoot() {
  4. 	if (!root) return nullptr;
  5. 	else {
  6. 		return this->root;
  7. 	}
  8. }

源代码：

btree.h
  1. #pragma once
  2. #include <iostream>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. template<class T>
  8. struct BTreeNode {
  9. 	T data;
  10. 	BTreeNode* left, * right;
  11. 	BTreeNode() :data(0), left(nullptr), right(nullptr) {}
  12. 	BTreeNode(T val, BTreeNode<T>* leftChild = nullptr, BTreeNode<T>* rightChild = nullptr)
  13. 		:data(val), left(leftChild), right(rightChild) {}
  14.  
  15. };
  16.  
  17. template<class T>
  18. class BTree {
  19. public:
  20. 	BTree() :root(nullptr) {}										      // 构造函数
  21. 	BTree(string str);                                                    // 重载
  22.  
  23. 	void createTree(BTreeNode<T>*& bt, string str);                       // 创建二次树
  24. 	~BTree();														      // 析构函数
  25. 	bool IsEmpty();													      // 判二叉树空否？
  26. 	int Size(BTreeNode<T>* cur);                                          // 计算结点个数
  27. 	int getSize();                                                        // 获取结点个数
  28. 	BTreeNode<T>* getData(T& item, BTreeNode<T>* cur);	                  // 取得结点数据
  29. 	bool Find(T& item);		                                              // 判断item是否在树中
  30. 	int Height(BTreeNode<T>* bt);                                         // 求树高度
  31. 	int getHeight();                                                      // 获取树高度
  32. 	BTreeNode<T>* getRoot();	                                          // 取根
  33.  
  34. 	void preOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);          // 前序遍历
  35. 	void inOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);		      // 中序遍历
  36. 	void postOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);         // 后序遍历
  37. 	void levelOrderTraversal(BTreeNode<T>* cur, vector<int>& vec);        // 层序遍历
  38.  
  39. 	vector<T> preOrder();						                          // 调用前序遍历，返回vector
  40. 	vector<T> inOrder();											      // 调用中序遍历，返回vector
  41. 	vector<T> postOrder();											      // 调用后序遍历，返回vector
  42. 	vector<T> levelOrder();                                               // 调用层序遍历，返回vector
  43.  
  44. 	void CopyTree(BTreeNode<T>* root, BTreeNode<T>*& copyRoot);           // 二叉树复制
  45. 	void Copy(BTreeNode<T>*& copyRoot);                                   // 调用二叉树复制
  46. 	void destroyCopyTree(BTreeNode<T>*& copyRoot);                        // 销毁复制二叉树
  47.  
  48.  
  49. 	BTreeNode<T>* FindParent(BTreeNode<T>* root, BTreeNode<T>* node);     // 寻找双亲
  50. 	BTreeNode<T>* LeftChild(BTreeNode<T>* node) {                         //求结点 node 的左孩子
  51. 		return (node != nullptr) ? node->left : nullptr;
  52. 	}
  53. 	BTreeNode<T>* RightChild(BTreeNode<T>* node) {                        //求结点 node 的右孩子
  54. 		return (node != nullptr) ? node->right : nullptr;
  55. 	}
  56.  
  57. protected:
  58. 	BTreeNode<T>* root;
  59. 	void destroyTree(BTreeNode<T>* node);                                // 销毁二叉树
  60. };
btree.cpp
  1. // 每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！
  2. // 1.确定递归函数的参数的返回值
  3. // 2.确定终止条件
  4. // 3.确定单层递归的逻辑
  5.  
  6. #include "btree.h"
  7.  
  8. template<class T>
  9. BTree<T>::BTree(string str) {
  10. 	createTree(root, str);
  11. 	cout << "报告：创建一颗二叉树，完成！！！" << endl;
  12. }
  13.  
  14. template<class T>
  15. void BTree<T>::createTree(BTreeNode<T>*& bt, string str) {
  16. 	static int i = 0;
  17. 	char ch = ' ';
  18. 	ch = str[i++];
  19.  
  20. 	if (ch == '#') bt = nullptr;
  21. 	else {
  22. 		bt = new BTreeNode<T>(ch);
  23. 		createTree(bt->left, str);
  24. 		createTree(bt->right, str);
  25. 	}
  26. };
  27.  
  28. // 判二叉树空否？
  29. template<class T>
  30. bool BTree<T>::IsEmpty() {
  31. 	return (root == nullptr) ? true : false;
  32. }
  33.  
  34. // 计算结点个数
  35. template<class T>
  36. int BTree<T>::Size(BTreeNode<T>* cur) {
  37. 	if (cur == nullptr)
  38. 		return 0;
  39. 	else
  40. 		return 1 + Size(cur->left) + Size(cur->right);
  41. }
  42.  
  43. // 获取结点个数
  44. template<class T>
  45. int BTree<T>::getSize() {
  46. 	return Size(root);
  47. }
  48.  
  49. // 取得结点数据
  50. template<class T>
  51. BTreeNode<T>* BTree<T>::getData(T& item, BTreeNode<T>* cur) {
  52. 	if (cur == nullptr) return nullptr;
  53. 	if (cur->data == item) return cur;
  54. 	return getData(item, cur->left) != nullptr ? getData(item, cur->left) : getData(item, cur->right);
  55. }
  56.  
  57. // 判断item是否在树中
  58. template<class T>
  59. bool BTree<T>::Find(T& item) {
  60. 	if (this->getData(item, root) == nullptr) return false;
  61. 	else return true;
  62. }
  63.  
  64. // 求树高度
  65. template<class T>
  66. int BTree<T>::Height(BTreeNode<T>* bt) {
  67. 	if (bt == nullptr) return 0;
  68. 	else {
  69. 		int leftH = Height(bt->left);
  70. 		int rightH = Height(bt->right);
  71. 		return (leftH > rightH) ? leftH + 1 : rightH + 1;
  72. 	}
  73. }
  74.  
  75. // 获取树高度
  76. template<class T>
  77. int BTree<T>::getHeight() {
  78. 	return Height(root);
  79. }
  80.  
  81. // 获取根 
  82. template<class T>
  83. BTreeNode<T>* BTree<T>::getRoot() {
  84. 	if (!root) return nullptr;
  85. 	else {
  86. 		return this->root;
  87. 	}
  88. }
  89.  
  90. // 析构函数
  91. template<class T>
  92. BTree<T>::~BTree<T>() {
  93. 	//cout << "调用析构函数" << endl;
  94. 	destroyTree(root);
  95. 	cout << "报告，这棵树已经销毁完毕!!!" << endl;
  96. }
  97.  
  98. // 销毁二叉树 
  99. template<class T>
  100. void BTree<T>::destroyTree(BTreeNode<T>* bt) {
  101. 	// 后序遍历删除根为subTree的子树；
  102. 	if (bt != nullptr) {
  103. 		destroyTree(bt->left);    //删除左子树
  104. 		destroyTree(bt->right);   //删除右子树
  105. 		delete bt; 			      //删除根结点
  106. 	}
  107. }
  108.  
  109. // 前序遍历
  110. template<class T>
  111. void BTree<T>::preOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
  112. 	if (cur == nullptr)
  113. 		return;
  114. 	vec.push_back(cur->data);           // 中
  115. 	preOrderTraversal(cur->left, vec);  // 左
  116. 	preOrderTraversal(cur->right, vec); // 右
  117. }
  118.  
  119. // 调用前序遍历，返回vector
  120. template<class T>
  121. vector<T> BTree<T>::preOrder() {
  122. 	cout << "获取前序遍历数组...." << endl;
  123. 	cout << ">>>>";
  124. 	vector<T> resVec;
  125. 	preOrderTraversal(root, resVec);
  126. 	return resVec;
  127. }
  128.  
  129. // 中序遍历
  130. template<class T>
  131. void BTree<T>::inOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
  132. 	if (cur == nullptr)
  133. 		return;
  134. 	inOrderTraversal(cur->left, vec);  // 左
  135. 	vec.push_back(cur->data);          // 中
  136. 	inOrderTraversal(cur->right, vec); // 右
  137. }
  138.  
  139. // 调用中序遍历，返回vector
  140. template<class T>
  141. vector<T> BTree<T>::inOrder() {
  142. 	cout << "获取中序遍历数组...." << endl;
  143. 	cout << ">>>>";
  144. 	vector<T> resVec;
  145. 	inOrderTraversal(root, resVec);
  146. 	return resVec;
  147. }
  148.  
  149. // 后序遍历
  150. template<class T>
  151. void BTree<T>::postOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
  152. 	if (cur == nullptr)
  153. 		return;
  154. 	postOrderTraversal(cur->left, vec);  // 左
  155. 	postOrderTraversal(cur->right, vec); // 右
  156. 	vec.push_back(cur->data);            // 中
  157. }
  158.  
  159. // 调用后序遍历，返回vector
  160. template<class T>
  161. vector<T> BTree<T>::postOrder() {
  162. 	cout << "获取后序遍历数组...." << endl;
  163. 	cout << ">>>>";
  164. 	vector<T> resVec;
  165. 	postOrderTraversal(root, resVec);
  166. 	return resVec;
  167. }
  168.  
  169. // 层序遍历
  170. template<class T>
  171. void BTree<T>::levelOrderTraversal(BTreeNode<T>* cur, vector<int>& vec) {
  172. 	if (cur == nullptr) return;
  173. 	queue<BTreeNode<T>*> Queue;
  174. 	BTreeNode<T>* p;
  175. 	Queue.push(cur); // 根结点入队列
  176. 	while (!Queue.empty()) {
  177. 		p = Queue.front();
  178. 		//cout << p->data << " ";//输出出队结点的数据
  179. 		vec.push_back(p->data);
  180. 		Queue.pop();
  181. 		if (p->left != nullptr) {
  182. 			Queue.push(p->left);
  183. 		}
  184. 		if (p->right != nullptr) {
  185. 			Queue.push(p->right);
  186. 		}
  187. 	}
  188. }
  189.  
  190. // 调用层序遍历，返回vector
  191. template<class T>
  192. vector<T> BTree<T>::levelOrder() {
  193. 	cout << "获取层序遍历数组...." << endl;
  194. 	cout << ">>>>";
  195. 	vector<T> resVec;
  196. 	levelOrderTraversal(root, resVec);
  197. 	return resVec;
  198. }
  199.  
  200. template<class T>
  201. void BTree<T>::CopyTree(BTreeNode<T>* root, BTreeNode<T>*& copyRoot) {
  202. 	if (!root) {
  203. 		copyRoot = nullptr;
  204. 	}
  205. 	else {
  206. 		copyRoot = new BTreeNode<T>;
  207. 		copyRoot->data = root->data;           //复制根节点
  208. 		CopyTree(root->left, copyRoot->left);  //递归复制左子树
  209. 		CopyTree(root->right, copyRoot->right);//递归复制左子树
  210. 	}
  211. }
  212.  
  213. template<class T>
  214. void BTree<T>::Copy(BTreeNode<T>*& copyRoot) {
  215. 	CopyTree(root, copyRoot);
  216. }
  217.  
  218. template<class T>
  219. void BTree<T>::destroyCopyTree(BTreeNode<T>*& copyRoot) {
  220. 	destroyTree(copyRoot);
  221. 	cout << "报告，复制二叉树已销毁完毕!!!" << endl;
  222. }
  223.  
  224. template<class T>
  225. BTreeNode<T>* BTree<T>::FindParent(BTreeNode<T>* root, BTreeNode<T>* node) {
  226.  
  227. 	if (root == nullptr) return nullptr;
  228. 	if (root->left == node || root->right == node)
  229. 		return root;	     //找到, 返回父结点地址
  230. 	BTreeNode <T>* p;
  231. 	if ((p = FindParent(root->left, node)) != nullptr)
  232. 		return p;	         //递归在左子树中搜索
  233. 	else return FindParent(root->right, node);
  234. }
test.cpp
  1. #include "btree.h"
  2. #include "btree.cpp"
  3. //#include <iostream>
  4. //using namespace std;
  5. int main() {
  6. 	cout << "-------------------------Start--------------------------" << endl;
  7. 	cout << "---------------------创建原始二叉树---------------------" << endl;
  8. 	string str = "ABD#G##E##CF###";
  9. 	BTree<int>* T = new BTree<int>(str);
  10. 	BTreeNode<int>* root = T->getRoot();
  11. 	cout << "这棵树有 " << T->getSize() << " 个结点" << endl;
  12.  
  13. 	int zifu = 'G';
  14. 	if (T->Find(zifu)) {
  15. 		cout << "这棵树有 " << (char)zifu << " 结点" << endl;
  16. 	}
  17. 	else {
  18. 		cout << "这棵树无 " << (char)zifu << " 结点" << endl;
  19. 	}
  20. 	BTreeNode<int>* node = T->getData(zifu, root);
  21. 	if (node) {
  22. 		cout << (char)node->data << endl;
  23. 		BTreeNode<int>* nodeParent = T->FindParent(root, node);
  24. 		if (!nodeParent) {
  25. 			cout << "找不到父亲结点" << endl;
  26. 		}
  27. 		else {
  28. 			cout << "结点 " << (char)zifu << " 的父亲结点是: " << (char)nodeParent->data << " 结点" << endl;
  29. 			if (nodeParent->left) cout << "我的左孩子是: " << (char)nodeParent->left->data << endl;
  30. 			else cout << "我没有左孩子..." << endl;
  31. 			if (nodeParent->right) cout << "我的右孩子是: " << (char)nodeParent->right->data << endl;
  32. 			else cout << "我没有右孩子..." << endl;
  33. 		}
  34. 	}
  35. 	cout << "这棵树的高度为: " << T->getHeight() << endl;
  36.  
  37. 	vector<int> vec = T->preOrder();
  38. 	for (auto i : vec) {
  39. 		cout << (char)i;
  40. 	}
  41. 	cout << endl;
  42.  
  43. 	vec.clear();
  44. 	vec = T->inOrder();
  45. 	for (auto i : vec) {
  46. 		cout << (char)i;
  47. 	}
  48. 	cout << endl;
  49.  
  50. 	vec.clear();
  51. 	vec = T->postOrder();
  52. 	for (auto i : vec) {
  53. 		cout << (char)i;
  54. 	}
  55. 	cout << endl;
  56.  
  57. 	vec.clear();
  58. 	vec = T->levelOrder();
  59. 	for (auto i : vec) {
  60. 		cout << (char)i;
  61. 	}
  62. 	cout << endl;
  63.  
  64.  
  65. 	cout << "-----------------------复制二叉树-----------------------" << endl;
  66. 	// 复制二叉树
  67. 	//vector<int> vec;
  68. 	//BTreeNode<int>* root = T->getRoot();
  69. 	BTreeNode<int>* copyRoot = new BTreeNode<int>;
  70. 	//T->Copy(copyRoot);          // 方法一
  71. 	T->CopyTree(root, copyRoot);  // 方法二
  72.  
  73. 	vec.clear();
  74. 	cout << "获取前序遍历数组...." << endl;
  75. 	cout << ">>>>";
  76. 	T->preOrderTraversal(copyRoot, vec);
  77. 	for (auto i : vec) {
  78. 		cout << (char)i;
  79. 	}
  80. 	cout << endl;
  81.  
  82. 	vec.clear();
  83. 	cout << "获取中序遍历数组...." << endl;
  84. 	cout << ">>>>";
  85. 	T->inOrderTraversal(copyRoot, vec);
  86. 	for (auto i : vec) {
  87. 		cout << (char)i;
  88. 	}
  89. 	cout << endl;
  90.  
  91. 	vec.clear();
  92. 	cout << "获取后序遍历数组...." << endl;
  93. 	cout << ">>>>";
  94. 	T->postOrderTraversal(copyRoot, vec);
  95. 	for (auto i : vec) {
  96. 		cout << (char)i;
  97. 	}
  98. 	cout << endl;
  99.  
  100. 	vec.clear();
  101. 	cout << "获取层序遍历数组...." << endl;
  102. 	cout << ">>>>";
  103. 	T->levelOrderTraversal(copyRoot, vec);
  104. 	for (auto i : vec) {
  105. 		cout << (char)i;
  106. 	}
  107. 	cout << endl;
  108. 	cout << "---------------------销毁复制二叉树---------------------" << endl;
  109. 	T->destroyCopyTree(copyRoot);
  110. 	cout << "---------------------销毁原始二叉树---------------------" << endl;
  111. 	T->~BTree();
  112. 	cout << "--------------------------End---------------------------" << endl;
  113. 	return 0;
  114. }
>>测试结果 
  1. -------------------------Start--------------------------
  2. ---------------------创建原始二叉树---------------------
  3. 报告：创建一颗二叉树，完成！！！
  4. 这棵树有 7 个结点
  5. 这棵树有 G 结点
  6. G
  7. 结点 G 的父亲结点是: D 结点
  8. 我没有左孩子...
  9. 我的右孩子是: G
  10. 这棵树的高度为: 4
  11. 获取前序遍历数组....
  12. >>>>ABDGECF
  13. 获取中序遍历数组....
  14. >>>>DGBEAFC
  15. 获取后序遍历数组....
  16. >>>>GDEBFCA
  17. 获取层序遍历数组....
  18. >>>>ABCDEFG
  19. -----------------------复制二叉树-----------------------
  20. 获取前序遍历数组....
  21. >>>>ABDGECF
  22. 获取中序遍历数组....
  23. >>>>DGBEAFC
  24. 获取后序遍历数组....
  25. >>>>GDEBFCA
  26. 获取层序遍历数组....
  27. >>>>ABCDEFG
  28. ---------------------销毁复制二叉树---------------------
  29. 报告，复制二叉树已销毁完毕!!!
  30. ---------------------销毁原始二叉树---------------------
  31. 报告，这棵树已经销毁完毕!!!
  32. --------------------------End---------------------------

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

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

  

闽ICP备14008679号