這個二叉樹的功能算很全面了~~
由給定的完全二叉樹形式存儲的數組(如"12345 6"),構造二叉樹
提供：復制構造函數和賦值操作符重載，遞歸和非遞歸形式的中、前、后序遍歷方法，求一個節點的父節點，左右兄弟結點的函數以及 求二叉樹深度和結點個數的函數。
1
// BTreeNode.h
2// 二叉樹結點抽象類型
3
4#ifndef BTREENODE_H
5#define BTREENODE_H
6
7#include <cstdlib>
8
9template<class T> class BTree;
10template<class T> class BTreeNode
11
{
12
friend class BTree<T>;
13public:
14
BTreeNode():lchild(NULL),rchild(NULL){ };
15 BTreeNode(const T&dt, BTreeNode<T> *lch =NULL , BTreeNode<T> *rch = NULL)
16 :data(dt),lchild(lch),rchild(rch){};
17
18 T get_data()const {return data; };
19 BTreeNode<T>* get_lchild()const {return lchild; };
20 BTreeNode<T>* get_rchild()const {return rchild; };
21
22private:
23 T data;
24 BTreeNode<T> *lchild, *rchild;
25
};
26#endif
1/**//************************************************************************
2** BTree.h二叉樹抽象類型
3** 由給定的完全二叉樹形式存儲的數組(如"12345 6"),構造二叉樹
4** 提供：復制構造函數和賦值操作符重載
5** 遞歸和非遞歸形式的中、前、后序遍歷方法
6** 求一個節點的父節點，左右兄弟結點的函數
7** 求二叉樹深度和結點個數的函數
8************************************************************************/
9#ifndef BTREE_H
10#define BTREE_H
11
12#include "BTreeNode.h"
13#include <stack> //非遞歸遍歷時借用棧
14#include <cstdlib> //NULL的定義在這里
15
16template <class T>
17class BTree
18{
19private:
20 BTreeNode<T>* build_body(T*elems, int n, int i); //構造二叉樹時使用
21 BTreeNode<T>* root;
22public:
23 //三個構造函數
24 BTree(T *a,int m);
25 BTree(BTreeNode<T> *p = NULL) { root = new BTreeNode<T>; copy_body(root, p); };
26 BTree(const T& t, BTree<T>& ltree, BTree<T>& rtree)
27 {
28 root = new BTreeNode<T>(t, ltree.root, rtree.root);
29 //原來兩顆子樹的根結點設置為空，避免非法訪問,否則遍歷時會出錯，創建新樹之前可以復制原來兩棵樹
30 ltree.root = rtree.root = NULL;
31
};
32 //復制構造函數
33 BTree(BTree& bt){root = new BTreeNode<T>; copy_body(root,bt.root);};
34 ~BTree() { destry(root); }
35
36 //重載復制操作符
37 BTree<T>& operator = (const BTree<T>& nbt) {root = new BTreeNode<T>; copy_body(root,nbt.root);};
38 //遞歸復制二叉樹
39 static void copy_body(BTreeNode<T>*&p, BTreeNode<T>* q);
40 //遞歸遍歷
41 static void in_order(BTreeNode<T>*p, void visit(BTreeNode<T>* p));
42 static void pre_order(BTreeNode<T>*p, void visit(BTreeNode<T>* p));
43 static void post_order(BTreeNode<T>*p, void visit(BTreeNode<T>* p));
44 virtual void pre_order(void visit(BTreeNode<T>* p))const {pre_order(root, visit);};
45 virtual void in_order(void visit(BTreeNode<T>* p))const {in_order(root, visit); };
46 virtual void post_order(void visit(BTreeNode<T>* p))const {post_order(root, visit); };
47 //非遞歸遍歷
48 virtual void in_order1(void visit(BTreeNode<T>* p))const;
49 virtual void pre_order1(void visit(BTreeNode<T>* p))const;
50 virtual void post_order1(void visit(BTreeNode<T>* p))const;
51
52 BTreeNode<T>* get_root()const{return root;}; //返回二叉樹根
53 BTreeNode<T>* get_parent(BTreeNode<T> *curr)const; //返回給定結點父節點
54 //定義見get_parent函數，只需修改一條語句
55 BTreeNode<T>* get_left_sibling(BTreeNode<T>* curr)const; //返回給定結點左兄弟結點
56 //定義見get_parent函數，只需修改一條語句
57 BTreeNode<T>* get_right_sibling(BTreeNode<T>* curr)const; //返回給定結點右兄弟結點
58 void set_root(BTreeNode<T>* p) { destry(root); copy_body(root, p);};
59
60 //釋放內存資源
61 static void destry(BTreeNode<T> *&p);
62
63 //求二叉樹結點個數
64 static int num(BTreeNode<T>* p);
65 int num()const { return num(root);};
66 //求二叉樹深度
67 static int depth(BTreeNode<T>* p);
68 int depth()const {return depth(root);};
69 //判斷二叉樹是否相等
70 static bool equal(BTreeNode<T> *p, BTreeNode<T> *q);
71 bool operator ==(BTree<T>&bt) const {return equal(root, bt.root);};
72};
73
74//構造函數
75template<class T>
76BTree<T>::BTree(T *a,int m)
77{
78 root = build_body(a, m, 1);//自作聰明,從0開始調用函數，導致l=2*i=0，沒有輸出結果，莫名其妙了半天
79};
80
81//構造子樹
82template <class T>
83BTreeNode<T>* BTree<T>::build_body(T*elems, int n, int i)//suffix
84{
85 BTreeNode<T> *p;
86 int l,r;
87 if( i <= n && elems[i-1] != ' ')
88 {
89 p = new BTreeNode<T>;
90 p->data = elems[i-1];
91 l = 2*i; //左兒子結點位置
92 r = 2*i + 1; //右兒子結點位置
93 p->lchild = build_body(elems,n,l);
94 p->rchild = build_body(elems,n,r);
95 return p;
96 }
97 else
98 return NULL;
99}
100
101//復制二叉樹
102template<class T>
103void BTree<T>::copy_body(BTreeNode<T>* &p, BTreeNode<T> *q)
104{
105 if(q != NULL)
106 {
107 if(p == NULL)
108 p = new BTreeNode<T>;
109 p->data = q->data;
110 copy_body(p->lchild,q->lchild);
111 copy_body(p->rchild,q->rchild);
112 }
113 else p = NULL;
114}
115
116//遞歸中序遍歷
117template<class T>
118void BTree<T>::in_order(BTreeNode<T>*p, void visit(BTreeNode<T>* p))
119{
120 if(p != NULL)
121 {
122 in_order(p->lchild,visit);
123 visit(p);
124 in_order(p->rchild,visit);
125 }
126}
127//遞歸前序遍歷
128template<class T>
129void BTree<T>::pre_order(BTreeNode<T>*p,void visit(BTreeNode<T>*p))
130{
131 if(p != NULL)
132 {
133 visit(p);
134 pre_order(p->lchild,visit);
135 pre_order(p->rchild,visit);
136 }
137}
138//遞歸后序遍歷
139template<class T>
140void BTree<T>::post_order(BTreeNode<T>*p,void visit(BTreeNode<T>*p))
141{
142 if(p != NULL)
143 {
144 post_order(p->lchild,visit);
145 post_order(p->rchild,visit);
146 visit(p);
147 }
148}
149//非遞歸中序遍歷
150template<class T>
151void BTree<T>::in_order1( void visit(BTreeNode<T>* p))const
152{
153 cout << "The inorder is : ";
154 std::stack< BTreeNode<T>* > stk;
155 BTreeNode<T> * q;
156 stk.push(root); //根結點進棧
157
158 while( !stk.empty()) //若棧非空，重復
159 {
160 while(stk.top() != NULL) //棧頂結點的左兒子相繼進棧，直到NULL為止
161 {
162 q= stk.top()->lchild;
163 stk.push(q);
164 }
165 stk.pop(); //將NULL退出棧
166
167 if( !stk.empty()) //訪問棧頂結點，并將其跳出棧
168 {
169 q = stk.top();
170 stk.pop();
171 visit(q);
172 stk.push(q->rchild); //將原棧頂結點的右子樹壓入棧
173 }
174 }
175 cout << endl;
176}
177
178//非遞歸前序遍歷
179template<class T>
180void BTree<T>::pre_order1(void visit(BTreeNode<T>*p))const
181{
182 cout << "The preorder is: " ;
183 std::stack< BTreeNode<T>* > stk;
184 BTreeNode<T>* q;
185
186 visit(root);
187 stk.push(root); //訪問根節點，并將其壓入棧
188 while( !stk.empty())
189 {
190 while(stk.top() != NULL) //相繼訪問棧頂結點的左兒子，并將其壓入棧，直至NULL
191 {
192 q = stk.top()->lchild;
193 if(q != NULL) visit(q);
194 stk.push(q);
195 }
196
197 stk.pop(); // 將NULL跳出棧
198
199 if( !stk.empty())
200 {
201 q = stk.top()->rchild; //標記原棧頂結點右兒子結點
202 stk.pop(); // 棧頂結點跳出棧
203 if( q != NULL) visit(q);
204 stk.push(q); //訪問右兒子結點并將其壓入棧
205 }
206 }
207 cout << endl;
208}
209
210//非遞歸后序遍歷
211template <class T>
212void BTree<T>::post_order1(void visit(BTreeNode<T>* p))const
213{
214 cout << "The postorder is: ";
215 std::stack< BTreeNode<T>* > stk;
216 BTreeNode<T> *q = NULL, *pre = NULL; //pre記錄前一個訪問的節點
217
218 stk.push(root);
219
220 while( !stk.empty()) //最后是樹根是如何跳出循環
221 {
222 while(stk.top() != NULL) //棧頂結點的左兒子結點相繼進棧，直到NULL
223 stk.push(stk.top()->lchild);
224
225 stk.pop(); //NULL跳出棧
226
227 if(!stk.empty())
228 {
229 q = stk.top(); //棧頂結點跳出
230 stk.pop();
231 // 當棧頂結點有右兒子，且沒有被訪問過時，將原棧頂結點重新壓入棧，并將其右兒子也壓入棧
232 if(q->rchild != NULL && !equal(q->rchild,pre))
233 {
234 stk.push(q);
235 stk.push(q->rchild);
236 }
237 // 不然，訪問原棧頂結點，為防止重復遍歷右兒子，將NULL壓入棧
238 else
239 {
240 visit(q);
241 stk.push(NULL);
242 pre = q;
243 }
244 }
245 }
246 cout << endl;
247}
248
249//求雙親結點
250//實質就是在中序遍歷的時候順便判斷一下給定結點是不是某一節點的兒子結點
251template<class T>
252BTreeNode<T>* BTree<T>::get_parent(BTreeNode<T> *curr)const
253{
254
255 cout << "The parent of " << curr->get_data() << " is: ";
256 std::stack< BTreeNode<T>* > stk;
257 BTreeNode<T> *p, *q;
258 p = NULL;
259 stk.push(root);
260
261 while( !stk.empty())
262 {
263 while(stk.top() != NULL)
264 {
265 q= stk.top()->lchild;
266 stk.push(q);
267 }
268 stk.pop();
269
270 if( !stk.empty())
271 {
272 q = stk.top();
273 stk.pop();
274 //求雙親結點
275 if(q->lchild == curr || q->rchild == curr) p = q;
276 //求左兄弟結點
277 //if(q->rchild == curr) p = q->lchild;
278 //求右兄弟結點
279 //if(q->lchild == curr) p = q->rchild;
280 stk.push(q->rchild);
281 }
282 }
283 return p;
284}
285
286//釋放資源
287template<class T>
288void BTree<T>::destry(BTreeNode<T> *&p)
289{
290 if(p != NULL)
291 {
292 destry(p->lchild);
293 destry(p->rchild);
294 delete p;
295 }
296 p = NULL;
297}
298
299//求二叉樹結點個數
300template<class T>
301int BTree<T>::num(BTreeNode<T>* p)
302{
303 if(p == NULL) return 0;
304 else return num(p->lchild) + num(p->rchild) + 1;
305}
306
307//求二叉樹深度
308template<class T>
309int BTree<T>::depth(BTreeNode<T>* p)
310{
311 int max = 0;
312 if(p == NULL) return 0;
313 else
314 {
315 max = depth(p->lchild);
316 if(depth(p->rchild) > max) max = depth(p->rchild);
317 return (max + 1);
318 }
319}
320
321//判斷二叉樹是否相等
322template<class T>
323bool BTree<T>::equal(BTreeNode<T> *p, BTreeNode<T> *q)
324{
325 bool b = true;
326 if((p == NULL) && (q == NULL)) ;
327 else if((p == NULL) || (q == NULL)) b = false;
328 else
329 {
330 b = (p->data == q->data) && (p->lchild == q->lchild) && (p->rchild == q->rchild);
331 }
332 return b;
333}
334
335#endif
1//MainFn.cpp 測試二叉樹功能
2
3#include "BTree.h"
4#include <iostream>
5
6using std::endl;
7using std::cout;
8
9//謂詞函數predicate，定義訪問二叉樹結點的形式
10void visit(BTreeNode<char> *p) { cout << p->get_data() << " ";};
11
12int main()
13{
14 char *str = "12345 6";//字符數組的定義形式
15 char *str2 = "78 9";
16 BTree<char> bt(str,7);
17 BTree<char> bt_copy(bt);
18 BTree<char> bt_copy2(bt.get_root());
19 BTree<char> bt_copy3 = bt;
20 BTree<char> bt2(str2,4);
21
22 //BTree<char> bt3('a',bt,bt2); //創建新樹,注意創建完這個樹以后原先的兩個樹bt，bt2已經無效，不能再調用
23 //bt3.in_order1(visit);
24
25 //測試構造函數
26 bt.in_order1(visit);
27 bt_copy.in_order1(visit);
28 bt_copy2.in_order1(visit);
29 bt_copy3.in_order1(visit);
30 //測試遍歷函數
31 bt.pre_order1(visit);
32 cout << "Postorder is :";
33 bt.post_order(visit);
34 cout <<endl;
35 bt.post_order1(visit);
36 //測試求二叉樹結點個數和深度的函數及其他
37 cout << bt.num() << "," << bt.depth() <<endl;
38 cout << bt.get_parent(bt.get_root()->get_lchild())->get_data() <<endl; //求雙親結點
39
40 return 0;
41}