这个二叉树的功能算很全面了~~
由给定的完全二叉树形式存储的数组(如"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}