這個二叉樹的功能算很全面了~~
由給定的完全二叉樹形式存儲的數(shù)組(如"12345 6"),構(gòu)造二叉樹
提供：復制構(gòu)造函數(shù)和賦值操作符重載，遞歸和非遞歸形式的中、前、后序遍歷方法，求一個節(jié)點的父節(jié)點，左右兄弟結(jié)點的函數(shù)以及 求二叉樹深度和結(jié)點個數(shù)的函數(shù)。
1
// BTreeNode.h
2// 二叉樹結(jié)點抽象類型
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** 由給定的完全二叉樹形式存儲的數(shù)組(如"12345 6"),構(gòu)造二叉樹
4** 提供：復制構(gòu)造函數(shù)和賦值操作符重載
5** 遞歸和非遞歸形式的中、前、后序遍歷方法
6** 求一個節(jié)點的父節(jié)點，左右兄弟結(jié)點的函數(shù)
7** 求二叉樹深度和結(jié)點個數(shù)的函數(shù)
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); //構(gòu)造二叉樹時使用
21 BTreeNode<T>* root;
22public:
23 //三個構(gòu)造函數(shù)
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 //原來兩顆子樹的根結(jié)點設置為空，避免非法訪問,否則遍歷時會出錯，創(chuàng)建新樹之前可以復制原來兩棵樹
30 ltree.root = rtree.root = NULL;
31
};
32 //復制構(gòu)造函數(shù)
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; //返回給定結(jié)點父節(jié)點
54 //定義見get_parent函數(shù)，只需修改一條語句
55 BTreeNode<T>* get_left_sibling(BTreeNode<T>* curr)const; //返回給定結(jié)點左兄弟結(jié)點
56 //定義見get_parent函數(shù)，只需修改一條語句
57 BTreeNode<T>* get_right_sibling(BTreeNode<T>* curr)const; //返回給定結(jié)點右兄弟結(jié)點
58 void set_root(BTreeNode<T>* p) { destry(root); copy_body(root, p);};
59
60 //釋放內(nèi)存資源
61 static void destry(BTreeNode<T> *&p);
62
63 //求二叉樹結(jié)點個數(shù)
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//構(gòu)造函數(shù)
75template<class T>
76BTree<T>::BTree(T *a,int m)
77{
78 root = build_body(a, m, 1);//自作聰明,從0開始調(diào)用函數(shù)，導致l=2*i=0，沒有輸出結(jié)果，莫名其妙了半天
79};
80
81//構(gòu)造子樹
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; //左兒子結(jié)點位置
92 r = 2*i + 1; //右兒子結(jié)點位置
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); //根結(jié)點進棧
157
158 while( !stk.empty()) //若棧非空，重復
159 {
160 while(stk.top() != NULL) //棧頂結(jié)點的左兒子相繼進棧，直到NULL為止
161 {
162 q= stk.top()->lchild;
163 stk.push(q);
164 }
165 stk.pop(); //將NULL退出棧
166
167 if( !stk.empty()) //訪問棧頂結(jié)點，并將其跳出棧
168 {
169 q = stk.top();
170 stk.pop();
171 visit(q);
172 stk.push(q->rchild); //將原棧頂結(jié)點的右子樹壓入棧
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); //訪問根節(jié)點，并將其壓入棧
188 while( !stk.empty())
189 {
190 while(stk.top() != NULL) //相繼訪問棧頂結(jié)點的左兒子，并將其壓入棧，直至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; //標記原棧頂結(jié)點右兒子結(jié)點
202 stk.pop(); // 棧頂結(jié)點跳出棧
203 if( q != NULL) visit(q);
204 stk.push(q); //訪問右兒子結(jié)點并將其壓入棧
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記錄前一個訪問的節(jié)點
217
218 stk.push(root);
219
220 while( !stk.empty()) //最后是樹根是如何跳出循環(huán)
221 {
222 while(stk.top() != NULL) //棧頂結(jié)點的左兒子結(jié)點相繼進棧，直到NULL
223 stk.push(stk.top()->lchild);
224
225 stk.pop(); //NULL跳出棧
226
227 if(!stk.empty())
228 {
229 q = stk.top(); //棧頂結(jié)點跳出
230 stk.pop();
231 // 當棧頂結(jié)點有右兒子，且沒有被訪問過時，將原棧頂結(jié)點重新壓入棧，并將其右兒子也壓入棧
232 if(q->rchild != NULL && !equal(q->rchild,pre))
233 {
234 stk.push(q);
235 stk.push(q->rchild);
236 }
237 // 不然，訪問原棧頂結(jié)點，為防止重復遍歷右兒子，將NULL壓入棧
238 else
239 {
240 visit(q);
241 stk.push(NULL);
242 pre = q;
243 }
244 }
245 }
246 cout << endl;
247}
248
249//求雙親結(jié)點
250//實質(zhì)就是在中序遍歷的時候順便判斷一下給定結(jié)點是不是某一節(jié)點的兒子結(jié)點
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 //求雙親結(jié)點
275 if(q->lchild == curr || q->rchild == curr) p = q;
276 //求左兄弟結(jié)點
277 //if(q->rchild == curr) p = q->lchild;
278 //求右兄弟結(jié)點
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//求二叉樹結(jié)點個數(shù)
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//謂詞函數(shù)predicate，定義訪問二叉樹結(jié)點的形式
10void visit(BTreeNode<char> *p) { cout << p->get_data() << " ";};
11
12int main()
13{
14 char *str = "12345 6";//字符數(shù)組的定義形式
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); //創(chuàng)建新樹,注意創(chuàng)建完這個樹以后原先的兩個樹bt，bt2已經(jīng)無效，不能再調(diào)用
23 //bt3.in_order1(visit);
24
25 //測試構(gòu)造函數(shù)
26 bt.in_order1(visit);
27 bt_copy.in_order1(visit);
28 bt_copy2.in_order1(visit);
29 bt_copy3.in_order1(visit);
30 //測試遍歷函數(shù)
31 bt.pre_order1(visit);
32 cout << "Postorder is :";
33 bt.post_order(visit);
34 cout <<endl;
35 bt.post_order1(visit);
36 //測試求二叉樹結(jié)點個數(shù)和深度的函數(shù)及其他
37 cout << bt.num() << "," << bt.depth() <<endl;
38 cout << bt.get_parent(bt.get_root()->get_lchild())->get_data() <<endl; //求雙親結(jié)點
39
40 return 0;
41}