二叉树 二叉链表 遍历代码
二叉树 二叉链表 遍历代码
01.//file:BTtree.h
02.#ifndef _BTTREE_H_HUMING_INCLUDE_
03.#define _BTTREE_H_HUMING_INCLUDE_
04.#include<iostream>
05.#include<queue>
06.#include<stack>
07.#define maxlen 100
08.using namespace std;
09.template <class T>
10.class treenode
11.{
12.public:
13. treenode():lchild(NULL),rchild(NULL) {};
14. treenode(const T &v,treenode<T> *left,treenode<T> *right):data(v),lchild(left),rchild(right) {};
15. ~treenode()
16. {
17. delete lchild;
18. delete rchild;
19. }
20. treenode<T> *lchild,*rchild;
21. T data;
22.};
23.template <class T>
24.class BTtree
25.{
26.public:
27. BTtree():root(NULL) {};
28. ~BTtree();
29. void pre_create();
30. bool Isempty();
31. treenode<T>* Lchild(treenode<T>* t);
32. treenode<T>* Rchild(treenode<T>* t);
33. T element(treenode<T>* t);
34. treenode<T>* return_root();
35. void pre_order(treenode<T>* t);
36. void in_order(treenode<T>* t);
37. void post_order(treenode<T>* t);
38. void nrec_pre_order(treenode<T>* t);
39. void nrec_in_order(treenode<T>* t);
40. void nrec_post_order(treenode<T>* t);
41. void level_order(treenode<T>* t);
42.private:
43. treenode<T> *root;
44. void clear(treenode<T>* t);
45. treenode<T>*insert();
46.};
47.
48.template<class T>
49.BTtree<T>::~BTtree()
50.{
51. clear(root);
52. delete root;
53.}
54.template <class T>
55.void BTtree<T>::clear(treenode<T>* t)
56.{
57. if(t==NULL) return;
58. else
59. {
60. clear(t->lchild);
61. clear(t->rchild);
62. t=NULL;
63. }
64.}
65.template <class T>
66.void BTtree<T>::pre_create()
67.{
68. root=insert();
69.}
70.template<class T>
71.treenode<T>* BTtree<T>::insert()
72.{
73. T ch;
74. treenode<T> *t;
75. cin >> ch;
76. if(ch=='#') t=NULL;
77. else
78. {
79. t=new treenode<T>;
80. t->data=ch;
81. t->lchild=insert();
82. t->rchild=insert();
83. }
84. return t;
85.}
86.template<class T>
87.bool BTtree<T>::Isempty()
88.{
89. return root?false:true;
90.}
91.template <class T>
92.treenode<T>* BTtree<T>::Lchild(treenode<T>* t)
93.{
94. return t->lchild?t->lchild:NULL;
95.}
96.template <class T>
97.treenode<T>* BTtree<T>::Rchild(treenode<T>* t)
98.{
99. return t->rchild?t->rchild:NULL;
100.}
101.template <class T>
102.T BTtree<T>::element(treenode<T>* t)
103.{
104. return t->data;;
105.}
106.template <class T>
107.void BTtree<T>::pre_order(treenode<T>* t)
108.{
109. if(t!=NULL)