实现一个简单的二叉树

　　之前刷题的时候，很多类似二叉树的题，但是千变万化，基本上都是几种遍历，反转，求高度这些的变形或者组合，所以这里索性直接写一个得了：

　　首先是二叉树的节点：

1 template<typename T>
2 struct TreeNode{
3     T val;
4     TreeNode<T> * left;
5     TreeNode<T> * right;
6     TreeNode();
7     TreeNode(const T & x);
8     ~TreeNode(); // non trivial destructor
9 };

　　注意destructor需要自己去实现一下:

1 template<typename T>
2 TreeNode<T>::~TreeNode()
3 {
4     delete left;
5     delete right;
6     left = right = NULL;
7 }

　　其他的没什么，直接贴代码：

 1 template<typename T>
 2 TreeNode<T>::TreeNode()
 3 {
 4     left = right = NULL;
 5 }
 6 
 7 template<typename T>
 8 TreeNode<T>::TreeNode(const T & x)
 9 {
10     left = right = NULL;
11     val = x;
12 }

　　之后就是树的定义了，考虑到封装，将底层的操作交给一些private方法去做，使用public的方法再去调用这些方法，所有声明如下所示：

 1 template<typename T>
 2 class BinaryTree{
 3     typedef void(*pFunc)(T &);
 4 public:
 5     BinaryTree() :root(NULL){}
 6     ~BinaryTree(); //non-trival destructor
 7     BinaryTree(std::initializer_list<T> il); //use initializer to construct
 8     BinaryTree(const BinaryTree<T> & rhs); // cp constructor
 9     BinaryTree<T> & operator=(const BinaryTree<T> & rhs); // = operator
10     const TreeNode<T> * getRoot() const; 
11     bool empty()const; // check empty
12     void preOrder(pFunc fun); 
13     void inOrder(pFunc fun);
14     void postOrder(pFunc fun);
15     void insert(const T & x);// add new number to the tree
16     int size()const; // get node total number in tree
17     int height()const; // get height of tree
18     void invert(); //invert the tree
19 
20 private:
21     int size(const TreeNode<T> * root)const;
22     int height(const TreeNode<T> * root)const;
23     bool empty(const TreeNode<T> * root)const;
24     bool equal(const TreeNode<T> * left, const TreeNode<T> * right)const;    
25     void assign(TreeNode<T> * & lhs, const TreeNode<T> * rhs);
26     void invert(TreeNode<T> * & root);
27     void clear(TreeNode<T> * & root);
28     void insert(TreeNode<T> * & root, const T & x);
29     void preOrder(TreeNode<T> * root, pFunc fun);
30     void inOrder(const TreeNode<T> * root, pFunc fun);
31     void postOrder(const TreeNode<T> * root, pFunc fun);
32 private:
33     TreeNode<T> * root;
34 };

assign, invert, clear, insert 这几个用到了引用。这里必须用引用，负责传过来的是指针的副本。

下面是具体的定义：

  1 template<typename T>
  2 int BinaryTree<T>::size(const TreeNode<T> * root)const
  3 {
  4     if (root == NULL)
  5         return 0;
  6     else 
  7         return 1 + size(root->left) + size(root->right);
  8 }
  9 
 10 template<typename T>
 11 int BinaryTree<T>::height(const TreeNode<T> * root)const
 12 {
 13     if (root == NULL)
 14         return 0;
 15     else
 16         return 1 + max(height(root->left    ), height(root->right));
 17 }
 18 
 19 template<typename T>
 20 bool BinaryTree<T>::equal(const TreeNode<T> * lhs, const TreeNode<T> *rhs)const
 21 {
 22     if (lhs == NULL && rhs == NULL)
 23         return true;
 24     if (lhs != NULL && rhs != NULL){
 25         if (lhs->val != rhs->val)
 26             return false;
 27         else
 28             return equal(lhs->left, rhs->left) && equal(lhs->right, rhs->right);
 29     }
 30     else{ // left与right中有一者是NULL
 31         return false;
 32     }
 33 }
 34 
 35 template<typename T>
 36 bool BinaryTree<T>::empty(const TreeNode<T> * root)const
 37 {
 38     return root == NULL;
 39 }
 40 
 41 template<typename T>
 42 void BinaryTree<T>::assign(TreeNode<T> * & lhs, const TreeNode<T> * rhs)
 43 {
 44     if (empty(rhs))
 45         lhs = new TreeNode<T>(rhs->val);
 46     if (rhs->left != NULL)
 47         assign(lhs->left, rhs->left);
 48     if (rhs->right != NULL)
 49         assign(lhs->right, rhs->right);
 50 }
 51 
 52 template<typename T>
 53 void BinaryTree<T>::invert(TreeNode<T> * & root)
 54 {
 55     if (root == NULL)
 56         return;
 57     swap(root->left, root->right);
 58     invert(root->left);
 59     invert(root->right);
 60 }
 61 
 62 template<typename T>
 63 void BinaryTree<T>::clear(TreeNode<T> * & root)
 64 {
 65     if (root == NULL)
 66         return;
 67     clear(root->left);
 68     clear(root->right);
 69     delete root;
 70     root = NULL;
 71 }
 72 
 73 template<typename T>
 74 void BinaryTree<T>::insert(TreeNode<T> * & root, const T & x)
 75 {
 76     if (root == NULL){
 77         root = new TreeNode<T>(x);
 78         return;
 79     }
 80     else{
 81         if (height(root->left) <= height(root->right)){
 82             insert(root->left, x);
 83         }
 84         else{
 85             insert(root->right, x);
 86         }
 87     }
 88 }
 89 
 90 template<typename T>
 91 void BinaryTree<T>::preOrder(TreeNode<T> * root, pFunc fun)
 92 {
 93     if (root == NULL)
 94         return;
 95     fun(root->val);
 96     preOrder(root->left, fun);
 97     preOrder(root->right, fun);
 98 }
 99 
100 template <typename T>
101 void BinaryTree<T>::inOrder(const TreeNode<T> * root, pFunc fun)
102 {
103     if (root == NULL)
104         return;
105     inOrder(root->left);
106     fun(root->val);
107     inOrder(root->right);
108 }
109 
110 template<typename T>
111 void BinaryTree<T>::postOrder(const TreeNode<T> * root, pFunc fun)
112 {
113     if (root == NULL)
114         return;
115     postOrder(root->left);
116     postOrder(root->right);
117     fun(root->val);
118 }
119 
120 template<typename T>
121 BinaryTree<T>::~BinaryTree()
122 {
123     clear(this->root);
124 }
125 
126 template<typename T>
127 BinaryTree<T>::BinaryTree(const BinaryTree<T> & rhs)
128 {
129     if (this == &rhs)
130         return;
131     else
132         assign(this->root, rhs.root);
133 }
134 
135 template<typename T>
136 BinaryTree<T> & BinaryTree<T>::operator=(const BinaryTree<T> & rhs)
137 {
138     if (this == &rhs)
139         return *this;
140     assign(this->root, rhs.root);
141     return *this;
142 }
143 
144 template<typename T>
145 const TreeNode<T> * BinaryTree<T>::getRoot()const
146 {
147     return root;
148 }
149 
150 template<typename T>
151 bool BinaryTree<T>::empty()const
152 {
153     return empty(this->root);
154 }
155 
156 template<typename T>
157 void BinaryTree<T>::preOrder(pFunc fun)
158 {
159     preOrder(this->root, fun);
160 }
161 
162 
163 template<typename T>
164 void BinaryTree<T>::inOrder(pFunc fun)
165 {
166     inOrder(this->root, fun);
167 }
168 
169 template<typename T>
170 void BinaryTree<T>::postOrder(pFunc fun)
171 {
172     postOrder(this->root, fun);
173 }
174 
175 template<typename T>
176 int BinaryTree<T>::size()const
177 {
178     return size(this->root);
179 }
180 
181 template<typename T>
182 int BinaryTree<T>::height()const
183 {
184     return height(this->root);
185 }
186 
187 template<typename T>
188 void BinaryTree<T>::invert()
189 {
190     invert(this->root);
191 }
192 
193 template<typename T>
194 void BinaryTree<T>::insert(const T & x)
195 {
196     insert(this->root, x);
197 }
198 
199 
200 template<typename T>
201 BinaryTree<T>::BinaryTree(std::initializer_list<T> il)
202     :root(NULL)
203 {
204     for (T i : il){
205         insert(i);
206     }
207 }
208 
209 
210 void tranverseFunc(int & val)
211 {
212     cout << "#:" << val << endl;
213 }

下面可以造一个实例使用一下：

1 int main()
2 {
3     BinaryTree<int> tree{1,4,3,6,3,2,8,7,11,25};
4     tree.preOrder(tranverseFunc);
5     tree.invert();
6     cout << "Invert 之后的树为： " << endl;
7     tree.preOrder(tranverseFunc);
8     system("pause");
9 }