【数据结构】二叉树(c++)

前端之家收集整理的这篇文章主要介绍了【数据结构】二叉树(c++)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

文件


  1. #include <iostream>
  2. using namespace std;
  3.  
  4. template<class Type>
  5. class Bintree;
  6.  
  7. //结点类
  8. template<class Type>
  9. class BintreeNode
  10. {
  11. friend class Bintree<Type>;
  12. public:
  13. BintreeNode() :data(Type()),leftchild(NULL),rightchild(NULL)
  14. {}
  15. BintreeNode(Type d,BintreeNode<Type> *l = NULL,BintreeNode<Type> *r = NULL) : data(d),leftchild(l),rightchild(r)
  16. {}
  17. private:
  18. BintreeNode<Type> *leftchild;
  19. BintreeNode<Type> *rightchild;
  20. Type data;
  21. };
  22.  
  23. //二叉树类
  24. template<class Type>
  25. class Bintree
  26. {
  27. public:
  28. Bintree() :Ref(Type()),root(NULL)
  29. {}
  30. Bintree(Type re,BintreeNode<Type> *r = NULL) : Ref(re),root(r)
  31. {}
  32. ~Bintree()
  33. {
  34. Destory();
  35. }
  36. public:
  37. //提供接口
  38. void CreatBintree()
  39. {
  40. Creat(root);
  41. }
  42.  
  43. void PreOrder()
  44. {
  45. PreOrder(root);
  46. }
  47.  
  48. void InOrder()
  49. {
  50. InOrder(root);
  51. }
  52.  
  53. void PostOrder()
  54. {
  55. PostOrder(root);
  56. }
  57.  
  58. int Height()
  59. {
  60. return Height(root);
  61. }
  62.  
  63. int Size()
  64. {
  65. return Size(root);
  66. }
  67.  
  68. BintreeNode<Type> *Search(Type key)
  69. {
  70. return Search(root,key);
  71. }
  72.  
  73. BintreeNode<Type> *PreOrder_Find(Type key)
  74. {
  75. return PreOrder_Find(root,key);
  76. }
  77.  
  78. BintreeNode<Type> *InOrder_Find(Type key)
  79. {
  80. return InOrder_Find(root,key);
  81. }
  82.  
  83. BintreeNode<Type> *PostOrder_Find(Type key)
  84. {
  85. return PostOrder_Find(root,key);
  86. }
  87.  
  88. BintreeNode<Type> *Parent(BintreeNode<Type> *q)
  89. {
  90. return Parent(root,q);
  91. }
  92.  
  93. BintreeNode<Type> *Leftchild(Type key)
  94. {
  95. return Leftchild(root,key);
  96. }
  97.  
  98. BintreeNode<Type> *Rightchild(Type key)
  99. {
  100. return Rightchild(root,key);
  101. }
  102.  
  103. Type Root()
  104. {
  105. return Root(root);
  106. }
  107.  
  108. void Destory()
  109. {
  110. return Destory(root);
  111. }
  112.  
  113. bool IsEmpty()
  114. {
  115. return IsEmpty(root);
  116. }
  117. void quit_system(int &x)
  118. {
  119. x = 0;
  120. }
  121. protected:
  122. //创建二叉树
  123. void Creat(BintreeNode<Type> *&t)
  124. {
  125. Type input;
  126. cin >> input;
  127. if (input == Ref)
  128. {
  129. t = NULL;
  130. }
  131. else
  132. {
  133. t = new BintreeNode<Type>(input);
  134. Creat(t->leftchild);
  135. Creat(t->rightchild);
  136. }
  137. }
  138.  
  139. // 前序遍历
  140. void PreOrder(const BintreeNode<Type> *t)
  141. {
  142. if (t == NULL)
  143. {
  144. return;
  145. }
  146. else
  147. {
  148. cout << t->data << " ";
  149. PreOrder(t->leftchild);
  150. PreOrder(t->rightchild);
  151. }
  152. }
  153.  
  154. // 中序遍历
  155. void InOrder(const BintreeNode<Type> *t)
  156. {
  157. if (t == NULL)
  158. {
  159. return;
  160. }
  161. else
  162. {
  163. InOrder(t->leftchild);
  164. cout << t->data << " ";
  165. InOrder(t->rightchild);
  166. }
  167. }
  168.  
  169. // 后序遍历
  170. void PostOrder(const BintreeNode<Type> *t)
  171. {
  172. if (t == NULL)
  173. {
  174. return;
  175. }
  176. else
  177. {
  178. PostOrder(t->leftchild);
  179. PostOrder(t->rightchild);
  180. cout << t->data << " ";
  181. }
  182. }
  183.  
  184. // 求高度
  185. int Height(const BintreeNode<Type> *t)
  186. {
  187. if (t == NULL)
  188. return 0;
  189. return (Height(t->leftchild) > Height(t->rightchild)) ? (Height(t->leftchild) + 1) : (Height(t->rightchild) + 1);
  190. }
  191.  
  192. int Size(const BintreeNode<Type> *t)
  193. {
  194. if (t == NULL)
  195. return 0;
  196. return(Size(t->leftchild) + Size(t->rightchild) + 1);
  197. }
  198.  
  199. // 查找一个节点返回其地址
  200. BintreeNode<Type> *Search( BintreeNode<Type> *t,const Type key)
  201. {
  202. if (t == NULL)
  203. {
  204. return NULL;
  205. }
  206. if (t->data == key)
  207. return t;
  208. BintreeNode<Type> *p;
  209. if ((p = Search(t->leftchild,key)) != NULL)
  210. return p;
  211. else
  212. return Search(t->rightchild,key);
  213. }
  214.  
  215. // 前序查找
  216. BintreeNode<Type> *PreOrder_Find(BintreeNode<Type> *t,const Type key)
  217. {
  218. if (t == NULL)
  219. {
  220. return NULL;
  221. }
  222. if (t->data == key)
  223. return t;
  224. BintreeNode<Type> *p;
  225. if ((p = PreOrder_Find(t->leftchild,key)) != NULL)
  226. return p;
  227. else
  228. return PreOrder_Find(t->rightchild,key);
  229. }
  230.  
  231. // 中序查找
  232. BintreeNode<Type> *InOrder_Find(BintreeNode<Type> *t,const Type key)
  233. {
  234. if (t == NULL)
  235. {
  236. return NULL;
  237. }
  238. BintreeNode<Type> *p;
  239. if ((p = InOrder_Find(t->leftchild,key)) != NULL)
  240. return p;
  241. else if (t->data == key)
  242. return t;
  243. else
  244. return InOrder_Find(t->rightchild,key);
  245. }
  246.  
  247. // 后序查找
  248. BintreeNode<Type> *PostOrder_Find(BintreeNode<Type> *t,const Type key)
  249. {
  250. if (t == NULL)
  251. {
  252. return NULL;
  253. }
  254. BintreeNode<Type> *p;
  255. BintreeNode<Type> *q;
  256. if ((p = PostOrder_Find(t->leftchild,key)) != NULL)
  257. return p;
  258. else if ((q = PostOrder_Find(t->rightchild,key)) != NULL)
  259. return q;
  260. else if (t->data = key)
  261. return t;
  262. }
  263.  
  264. // 求父节点并返回其父节点地址
  265. BintreeNode<Type> *Parent(BintreeNode<Type> *&t,BintreeNode<Type> *q)
  266. {
  267. if (t == NULL)
  268. {
  269. return t;
  270. }
  271. if (q == t->leftchild || q == t->rightchild || q == t)
  272. {
  273. return t;
  274. }
  275. BintreeNode<Type> *p;
  276. if ((p = Parent(t->leftchild,q)) != NULL)
  277. {
  278. return p;
  279. }
  280. else
  281. return Parent(t->rightchild,q);
  282. }
  283.  
  284. // 求左孩子
  285. BintreeNode<Type> *Leftchild(BintreeNode<Type> *t,const Type key)
  286. {
  287. BintreeNode<Type> *p = Search(t,key);
  288. if (p == NULL)
  289. {
  290. cout << "the node is not exist!" << endl;
  291. return NULL;
  292. }
  293. if (p->leftchild == NULL)
  294. {
  295. cout << "this node not has leftchild" << endl;
  296. return NULL;
  297. }
  298. else
  299. return p->leftchild;
  300. }
  301.  
  302. // 求右孩子
  303. BintreeNode<Type> *Rightchild(BintreeNode<Type> *t,key);
  304. if (p == NULL)
  305. {
  306. cout << "the node is not exist!" << endl;
  307. return NULL;
  308. }
  309. if (p->rightchild == NULL)
  310. {
  311. cout << "this node not has rightchild" << endl;
  312. return NULL;
  313. }
  314. else
  315. return p->rightchild;
  316. }
  317.  
  318. // 求根
  319. Type Root(const BintreeNode<Type> *t)
  320. {
  321. return t->data;
  322. }
  323.  
  324. void Destory(const BintreeNode<Type> *t)
  325. {
  326. if (t != NULL)
  327. {
  328. Destory(t->leftchild);
  329. Destory(t->rightchild);
  330. delete t;
  331. }
  332. }
  333.  
  334. // 看树是否为空
  335. bool IsEmpty(const BintreeNode<Type> *t)
  336. {
  337. return t == NULL;
  338. }
  339. private:
  340. BintreeNode<Type> *root;
  341. Type Ref;
  342. };


页面设计:


  1. #include "Bintree.h"
  2.  
  3. int main()
  4. {
  5. Bintree<char> bt('#');
  6. int select = 1;
  7. char c;
  8. while (select)
  9. {
  10. cout << "******************************************************************" << endl;
  11. cout << "* [1] creat [2] PreOrder [3] InOrder *" << endl;
  12. cout << "* [4] PostOrder [5] Height [6] Size *" << endl;
  13. cout << "* [7] search [8] PreOrder_Find [9] InOrder_Find *" << endl;
  14. cout << "* [10] PostOrder_Find [11] parent [12] leftchild *" << endl;
  15. cout << "* [13] rightchild [14] root [15] destory *" << endl;
  16. cout << "* [16] Isempty [17] quit_system *" << endl;
  17. cout << "******************************************************************" << endl;
  18. cout << "pleae choose:";
  19. cin >> select;
  20. switch (select)
  21. {
  22. case 1:
  23. cout << "please enter:";
  24. bt.CreatBintree();
  25. break;
  26. case 2:
  27. bt.PreOrder();
  28. cout << endl;
  29. break;
  30. case 3:
  31. bt.InOrder();
  32. cout << endl;
  33. break;
  34. case 4:
  35. bt.PostOrder();
  36. cout << endl;
  37. break;
  38. case 5:
  39. cout << bt.Height() << endl;
  40. break;
  41. case 6:
  42. cout << bt.Size() << endl;
  43. break;
  44. case 7:
  45. cout << "please enter what u want to search:";
  46. cin >> c;
  47. cout << bt.Search(c) << endl;
  48. break;
  49. case 8:
  50. cout << "please enter what u want to search:";
  51. cin >> c;
  52. cout << bt.PreOrder_Find(c) << endl;
  53. break;
  54. case 9:
  55. cout << "please enter what u want to search:";
  56. cin >> c;
  57. cout << bt.InOrder_Find(c) << endl;
  58. break;
  59. case 10:
  60. cout << "please enter what u want to search:";
  61. cin >> c;
  62. cout << bt.PostOrder_Find(c) << endl;
  63. break;
  64. case 11:
  65. cout << "whose parent u wanna find:";
  66. cin >> c;
  67. cout << bt.Parent(bt.Search(c)) << endl;
  68. break;
  69. case 12:
  70. cout << "whose leftchild u wanna find:";
  71. cin >> c;
  72. cout << bt.Leftchild(c) << endl;
  73. break;
  74. case 13:
  75. cout << "whose rightchild u wanna find:";
  76. cin >> c;
  77. cout << bt.Rightchild(c) << endl;
  78. break;
  79. case 14:
  80. cout << bt.Root() << endl;
  81. break;
  82. case 15:
  83. bt.Destory();
  84. break;
  85. case 16:
  86. if (bt.IsEmpty())
  87. {
  88. cout << "it is an empty bintree" << endl;
  89. }
  90. else
  91. {
  92. cout << "it is not an empty bintree" << endl;
  93. }
  94. break;
  95. case 17:
  96. bt.quit_system(select);
  97. break;
  98. default:
  99. break;
  100.  
  101. }
  102. }
  103. return 0;
  104. }


求高度:



中序遍历:



中序遍历查找:



判断是否为空树:



求其父节点:



后序遍历:



前序遍历:



退出系统:



求其右孩子:



求根:



查找:



求节点个数:


猜你在找的数据结构相关文章