实验6
学号： 姓名： 专业：
6.1 实验目的
掌握二叉树的动态链表存储结构及表示。
掌握二叉树的三种遍历算法（递归和非递归两类）。
运用二叉树三种遍历的方法求解有关问题。
6.2 实验要求
按照C++面向对象方法编写二叉树类；二叉树的测试数据可用多种方式进行输入，如键盘输入、静态写入、文件读入等。//最难的是从文件把数据读进去！
设计二叉树的二叉链表存储结构，编写算法实现下列问题的求解。
<1>打印出二叉树的三种遍历序列。
<2>设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。
<3>求二叉树的高度。
<4>求二叉树的结点数。
<5>求二叉树的叶子结点数。
<6>求二叉树的度为2的结点数。
<7>键盘输入一个元素x，求其父节点、兄弟结点、子结点的值，不存在时给出相应提示信息。对兄弟结点和孩子结点，存在时要明确指出是左兄弟、左孩子、右兄弟或右孩子。
<8>键盘输入一个元素x，求其在树中的层次，不存在时给出相应提示信息。
<9>将按顺序方式存储在数组中的二叉树转换为二叉链表形式。（数组中要扩展为完全二叉树）。
<10>交换二叉树中每个结点的左右孩子指针的值。（即：左子树变为右子树，右子树变为左子树）。
（下面为选做实验，有兴趣的同学完成）
<11>复制一棵二叉树T到T1。
<12>输出二叉树从每个叶子结点到根结点的路径（经历的结点）。
<13>对二叉链表表示的二叉树，按从上到下，从左到右打印结点值，即按层次打印。（提示：需要使用队列）
<14>对二叉链表表示的二叉树，求2个结点最近的共同祖先。
实验测试数据基本要求：
<15>求二叉树中一条最长的路径长度（边数），并输出路径上的个结点值。
实验测试数据基本要求：
6.3 实验数据要求
自我编写测试样例，要求每个功能函数的测试样例不少于两组
6.4 运行结果截图及说明
图1 测试（1）、（2）、（3）、（4）、（5）、（6）
图2 测试（1）、（2）、（3）、（4）、（5）、（6）
图3 测试（1）、（2）、（3）、（4）、（5）、（6）
图4 测试（1）、（2）、（3）、（4）、（5）、（6）
图5 测试（1）、（2）、（3）、（4）、（5）、（6）
图6 测试（1）、（2）、（3）、（4）、（5）、（6）
图7 测试（1）、（2）、（3）、（4）、（5）、（6）
图8 测试（1）、（2）、（3）、（4）、（5）、（6）
图9 测试（1）、（2）、（3）、（4）、（5）、（6）
图10 测试（1）、（2）、（3）、（4）、（5）、（6）
图11 测试（1）、（2）、（3）、（4）、（5）、（6）
图12 测试（1）、（2）、（3）、（4）、（5）、（6）
图13 测试（1）、（2）、（3）、（4）、（5）、（6）
图14 测试（1）、（2）、（3）、（4）、（5）、（6）
图15 测试（1）、（2）、（3）、（4）、（5）、（6）
图16 测试（1）、（2）、（3）、（4）、（5）、（6）
图17 测试（1）、（2）、（3）、（4）、（5）、（6）
图18 测试（1）、（2）、（3）、（4）、（5）、（6）
图19 测试（1）、（2）、（3）、（4）、（5）、（6）
图20 测试（1）、（2）、（3）、（4）、（5）、（6）
图21 测试（1）、（2）、（3）、（4）、（5）、（6）
图22 测试（1）、（2）、（3）、（4）、（5）、（6）
图23 测试（1）、（2）、（3）、（4）、（5）、（6）
图24 测试（7）
图25 测试（7）
图26 测试（7）
图27 测试（7）
图28 测试（7）
图29 测试（7）
图30 测试（7）
图31 测试（8）
图32 测试（8）
图33 测试（9）
图34 测试（9）
图35 测试（10）
图36 测试（10）
图37 测试（11）
图38 测试（11）
图39 测试（12）
图40 测试（12）
图41 测试（13）
图42 测试（13）
图43 测试（14）
图44 测试（14）
图45 测试（15）
图46 测试（15）
6.5 附源代码
1 // stdafx.h : include file for standard system include files, 2 // or project specific include files that are used frequently, but 3 // are changed infrequently 4 // 5 6 #if !defined(AFX_STDAFX_H__02F8C78B_9F6E_45FF_BFCE_7F99B5AC9359__INCLUDED_) 7 #define AFX_STDAFX_H__02F8C78B_9F6E_45FF_BFCE_7F99B5AC9359__INCLUDED_ 8 9 #if _MSC_VER > 1000 10 #pragma once 11 #endif // _MSC_VER > 1000 12 13 #include <stdc++.h> 14 #include <windows.h> 15 16 using namespace std; 17 18 typedef char elementType; 19 typedef int elementType1; 20 21 typedef struct node 22 { 23 elementType data;//刚开始应该写成将data写成string或者直接将整个函数写成模板的，写完了最后测试时 24 //才发现现在的写法有诸多不便；但修改的话就又要重构一遍，懒得整了。 25 struct node *leftChild, *rightChild; 26 }bitNode, *binTree; 27 28 typedef struct charNode 29 { 30 //elementType data; 31 bitNode *data;//the type must be bitNode* 32 struct charNode *link; 33 }CLNode, *CPNode; 34 35 36 //typedef struct charNode 37 //{ 38 //elementType data; 39 //struct charNode *leftChild, *rightChild; 40 //}charBitNode, *charBinTree; 41 42 // TODO: reference additional headers your program requires here 43 44 //{{AFX_INSERT_LOCATION}} 45 // Microsoft Visual C++ will insert additional declarations immediately before the previous line. 46 47 #endif // !defined(AFX_STDAFX_H__02F8C78B_9F6E_45FF_BFCE_7F99B5AC9359__INCLUDED_)
1 // charLinkedQueue.h: interface for the charLinkedQueue class.
2 //
3 //////////////////////////////////////////////////////////////////////
4
5 #if !defined(AFX_CHARLINKEDQUEUE_H__13C2F642_81C0_4489_9CF2_3D58D8B48EA9__INCLUDED_)
6 #define AFX_CHARLINKEDQUEUE_H__13C2F642_81C0_4489_9CF2_3D58D8B48EA9__INCLUDED_
7
8 #if _MSC_VER > 1000
9 #pragma once
10 #endif // _MSC_VER > 1000
11
12 //刚开始尝试写英文注释的，后面知难而退了；不过原来的英文注释我保留了
13
14 class charLinkedQueue
15 {
16 public:
17 charLinkedQueue();
18 virtual ~charLinkedQueue();
19 bool emptyCharLinkedQueue();
20 //bool fullSeqCircleQueue();
21 bool enQueue( bitNode *value );//the type must be bitNode*
22 bool deQueue( /*bitNode *value*/ );
23 bool getFront( bitNode *&value );//the type must be bitNode*&
24 int length();
25 friend ostream &operator<<( ostream &os, charLinkedQueue &clq )
26 {
27 /*
28 if( ( scq._front - 1 ) % maxn == scq._rear )
29 return os;
30 int column = 0;
31 for( int i = scq._front; i % maxn != scq._rear; i = ( i + 1 ) % maxn )
32 {
33 os << setw(3) << setiosflags(ios::left) << scq.data[i] << " ";
34 column ++;
35 if( column % 10 == 0 )
36 os << endl;
37 }
38 os << endl;
39 */
40 if( clq._front == NULL )
41 return os;
42 CLNode *tmp = clq._front;
43 int column = 0;
44 while( tmp != clq._rear->link )
45 {
46 os << setw(4) << setiosflags(ios::left) << tmp->data << " ";
47 column ++;
48 tmp = tmp->link;
49 if( column % 10 == 0 )
50 os << endl;
51 }
52 os << endl;
53 }
54 //为了能顺利使用原来的这个代码块来进行二叉树的层次便利，我主要的精力都放在_front、_rear类型、
55 //deQueue()、enQueue()、charNode的类型确定上，经过无数次尝试，总算结果对了----
56 //如果有Git，看了这个代码的每个版本你就会知道我付出了多少心血。。。。
57 private:
58 CLNode *_front;//the type must be CLNode*
59 CLNode *_rear;//the type must be CLNode*
60 };
61
62 #endif // !defined(AFX_CHARLINKEDQUEUE_H__13C2F642_81C0_4489_9CF2_3D58D8B48EA9__INCLUDED_)
1 // _Binary_Tree.h: interface for the _Binary_Tree class.
2 //
3 //////////////////////////////////////////////////////////////////////
4
5 #if !defined(AFX__BINARY_TREE_H__9381B15F_E185_4489_9415_360A22C0A4E2__INCLUDED_)
6 #define AFX__BINARY_TREE_H__9381B15F_E185_4489_9415_360A22C0A4E2__INCLUDED_
7
8 #if _MSC_VER > 1000
9 #pragma once
10 #endif // _MSC_VER > 1000
11
12 #include "charLinkedQueue.h"
13
14 //刚开始尝试写英文注释的，后面知难而退了；不过原来的英文注释我保留了
15
16 class _Binary_Tree
17 {
18 public:
19 _Binary_Tree();//不带参数的构造函数
20 _Binary_Tree( elementType *Arr );//带参数的构造函数
21 void build( elementType *Arr );//从数组建立二叉树，相当于初始化；不带参数的构造函数无法适用于这里
22 void createNode( binTree BT, elementType *Arr, int number );//根据从数组读到的数据先序递归建树
23 virtual ~_Binary_Tree();//析构函数
24 bool createBinaryTree( binTree &BT, elementType stringLine[100][3], int length, int &row );//根据文本数据
25 //先序构造二叉树
26 bool readFileToArray( elementType stringLine[100][3], int &length );//将文本数据读入二维数组中
27 bool emptyBinaryTree();//二叉树判空，仅适用于带参数构造函数建立的二叉树
28 bool _exit( binTree BT, elementType value );//判断节点数据是否在二叉树中
29 binTree getNodePoint();//返回根节点地址
30 binTree getNodePoint( binTree BT, elementType value );//返回value在二叉树中的地址
31 binTree getParent( binTree BT, elementType value );//返回value的父母
32 void PreOrderTraverse(binTree BT);//前序遍历
33 void InOrderTraverse(binTree BT);//中序遍历
34 void PostOrderTraverse(binTree BT);//后序遍历
35 void levelOrderTraverse(binTree BT);//层次遍历
36 void destroy( binTree BT );//销毁二叉树
37 void level( binTree BT, int number );//求二叉树中各个节点的层次
38 int height( binTree BT );//求二叉树高度
39 int numberOfBTreeNode( binTree BT );//返回二叉树节点总数
40 int numberOfBTreeLeafNode( binTree BT, int &number );//返回二叉树叶节点个数
41 void numberOfNodeDegreeTwo( binTree BT, int &number );//求二叉树中度为2的节点个数
42 //void family( binTree BT, elementType1 number );
43 void getParent( binTree BT, elementType value, bool &flag );//求value的父节点
44 void getSibling( binTree BT, elementType value, bool &flag );//when call the function, the parameter flag
45 //must be assigned for false
46 //求value的兄弟节点，法1；有一个bug
47 void getSibling( binTree BT, elementType value );//求value的兄弟节点，法2
48 void getChild( binTree BT, elementType value, bool &flag );//求value孩子节点
49 int levelJudge( binTree BT, elementType value, int &number, int level );//返回value节点的层次
50 void exchangeLeftAndRightSibling( binTree BT );//交换左右子树
51 void copyBTree( binTree BT1, binTree BT );//复制二叉树
52 charLinkedQueue clq;//包含
53 void allLeafToRootPath( binTree BT, elementType *path, int &pathLength );//求所有叶节点到根节点路径
54 void binaryTreeLongestPath( binTree BT, elementType *path, int &pathLength,
55 elementType *longestPath, int &longestLength );//求叶节点到根节点的最长路径
56 binTree nearestAncestor( binTree BT, bitNode *BNode1, bitNode *BNode2 );//求两个节点的最近祖先
57 //本来打算用elementType数据
58 //作为参数的，后面发现行不通
59 //可能是我太菜了吧
60 private:
61 bitNode *BTree;
62
63 };
64
65 #endif // !defined(AFX__BINARY_TREE_H__9381B15F_E185_4489_9415_360A22C0A4E2__INCLUDED_)
1 // charLinkedQueue.cpp: implementation of the charLinkedQueue class.
2 //
3 //////////////////////////////////////////////////////////////////////
4
5 #include "stdafx.h"
6 #include "charLinkedQueue.h"
7
8 //////////////////////////////////////////////////////////////////////
9 // Construction/Destruction
10 //////////////////////////////////////////////////////////////////////
11
12 charLinkedQueue::charLinkedQueue()
13 {
14 _front = _rear = NULL;
15 }
16
17 charLinkedQueue::~charLinkedQueue()
18 {
19 CLNode *tmp = NULL;
20 while( _front != _rear )
21 {
22 tmp = _front;
23 _front = _front->link;
24 delete tmp;
25 }
26 cout << "The charLinkedQueue destruction has been called!" << endl;
27 }
28
29 bool charLinkedQueue::emptyCharLinkedQueue()
30 {
31 return _front == NULL;
32 }
33
34 bool charLinkedQueue::enQueue( bitNode *value )
35 {
36 CLNode *newNode = new CLNode;
37 if( !newNode )
38 {
39 cerr << "Space allocating falied!Error in charLinkedQueue::enQueue()!" << endl;
40 return false;
41 }
42 newNode->data = value;
43 newNode->link = NULL;
44 if( emptyCharLinkedQueue() )
45 {
46 _front = _rear = newNode;
47 }
48 else
49 {
50 _rear->link = newNode;
51 _rear = newNode;
52 }
53 return true;
54 }
55
56 bool charLinkedQueue::deQueue( /*elementType &value*/ )
57 {
58 if( emptyCharLinkedQueue() )
59 {
60 cerr << "Node deleting falied!Error in charLinkedQueue::deQueue()!" << endl;
61 return false;
62 }
63 CLNode *tmp = _front;
64 //value = _front->data;
65 _front = _front->link;
66 delete tmp;
67 if( _front == NULL )
68 _rear = NULL;
69 return true;
70 }
71
72 bool charLinkedQueue::getFront( bitNode *&value )
73 {
74 if( emptyCharLinkedQueue() )
75 {
76 cerr << "Queue is empty!
Node-data acquiring falied!Error in charLinkedQueue::deQueue()!" << endl;
77 return false;
78 }
79 value = _front->data;//原来我是注释掉的，导致输出一直是A；
80 return true;
81 }
82
83 int charLinkedQueue::length()
84 {
85 if( emptyCharLinkedQueue() )
86 {
87 cerr << "Queue is empty!" << endl;
88 return -1;
89 }
90 CLNode *tmp = _front;
91 int _size = 0;
92 while( tmp != NULL )
93 {
94 tmp = tmp->link;
95 _size ++;
96 }
97 return _size;
98 }
1 // _Binary_Tree.cpp: implementation of the _Binary_Tree class.
2 //
3 //////////////////////////////////////////////////////////////////////
4
5 #include "stdafx.h"
6 #include "_Binary_Tree.h"
7 #include "charLinkedQueue.h"
8
9 //////////////////////////////////////////////////////////////////////
10 // Construction/Destruction
11 //////////////////////////////////////////////////////////////////////
12
13
14 _Binary_Tree::_Binary_Tree() //新建一个结点
15 {
16 //BTree = NULL;
17 BTree = new bitNode;
18 BTree->leftChild = BTree->rightChild = NULL;
19 }
20
21 _Binary_Tree::~_Binary_Tree()
22 {
23 destroy(BTree);//析构函数不能带参数，只能这么处理了
24 }
25
26 _Binary_Tree::_Binary_Tree( elementType *Arr )
27 {
28 BTree = NULL;
29 build(Arr);
30 }
31
32 void _Binary_Tree::build( elementType *Arr )
33 {
34 if(BTree)
35 destroy(BTree);
36 if( Arr[0] == '^' )
37 {
38 BTree = NULL;
39 return;
40 }
41 BTree = new bitNode;
42 BTree->leftChild = NULL;
43 BTree->rightChild = NULL;
44 BTree->data = Arr[0];
45 createNode( BTree, Arr, 0 );
46 }
47
48 void _Binary_Tree::createNode( binTree BT, elementType *Arr, int number )
49 {
50 bitNode *tmp = new bitNode;
51 if( Arr[ number * 2 + 1 ] != '^' )
52 {
53 BT->leftChild =new bitNode ;
54 tmp = BT->leftChild;
55 tmp->data = Arr[ number * 2 + 1 ];
56 tmp->leftChild = NULL;
57 tmp->rightChild = NULL;
58 createNode( tmp, Arr, number * 2 + 1 );
59 }
60 if( Arr[ number * 2 + 2 ] != '^' )
61 {
62 BT->rightChild =new bitNode ;
63 tmp = BT->rightChild;
64 tmp->data = Arr[ number * 2 + 2 ];
65 tmp->leftChild = NULL;
66 tmp->rightChild = NULL;
67 createNode( tmp, Arr, number * 2 + 2 );
68 }
69 }
70
71 bool _Binary_Tree::createBinaryTree( binTree &BT, elementType stringLine[100][3], int length, int &row )
72 {
73 if (row >= length || length == 0 ) //strlen存数据的二维数组，nRow结点所在的位数，nlen结点的个数
74 return false;
75 if ( row == 0 )
76 BT = BTree;
77 else
78 BT = new bitNode;//new下面是公用的，用if的目的是改变private里BTree里的值
79 BT->data = stringLine[row][0];
80 BT->leftChild = NULL;
81 BT->rightChild = NULL;
82
83 int nextRow = row;
84 if ( stringLine[nextRow][1] == '1' )
85 {
86 ++ row;
87 createBinaryTree( BT->leftChild, stringLine, length, row );
88 }
89 if ( stringLine[nextRow][2] == '1' )
90 {
91 ++row;
92 createBinaryTree( BT->rightChild, stringLine, length, row );
93 }
94 return true;
95 }
96
97 bool _Binary_Tree::readFileToArray( elementType stringLine[100][3], int &length )
98 {
99 FILE *fp;
100 char str[100];
101
102 cout << "Please input the file name(belike includes the file path):" << endl;
103 char name[50];// = "bt10.btr";
104 cin >> name;
105 fp = fopen( name, "r" );
106 if (!fp)
107 {
108 cout << "Error!" << endl;
109 return false;
110 }
111 if (fgets(str, 1000, fp) != NULL)
112 {
113 if (strcmp(str, "BinaryTree
") != 0)
114 {
115 cout << "Error!" << endl;
116 fclose(fp);
117 return false;
118 }
119 }
120 length = 0;
121 while (fscanf(fp, "%c %c %c
", &stringLine[length][0], &stringLine[length][1], &stringLine[length][2]) != EOF)
122 {
123 length ++;
124 }
125 fclose(fp);
126 return true;
127 }
128
129
130 bool _Binary_Tree::emptyBinaryTree()
131 {
132 //if(BTree)
133 //return BTree->leftChild == NULL && BTree->rightChild == NULL;
134 //else
135 return BTree == NULL;
136 }
137
138 bool _Binary_Tree::_exit( binTree BT, elementType value )
139 {
140 if(!BT)
141 return false;
142 //return NULL;
143 if( BT->data == value )
144 return true;
145 //return BT;
146 //bitNode *index = _exit( BT->leftChild, value );
147 bool flag = _exit( BT->leftChild, value );
148 //if(!index)
149 if(!flag)
150 //_exit( BT->leftChild, value );
151 _exit( BT->rightChild, value );
152 }
153
154 binTree _Binary_Tree::getNodePoint()
155 {
156 //if( emptyBinaryTree() )
157 //{
158 //throw "Empty binary tree!Error in binTree _Binary_Tree::getNodePoint()!
";
159 //return NULL;
160 //}
161 return (*this).BTree;
162 }
163
164 binTree _Binary_Tree::getNodePoint( binTree BT, elementType value )
165 {
166 /*
167 if(!BT)
168 {
169 return NULL;
170 }
171 else
172 {
173 if( BT->data == value )
174 return BT;
175 else
176 {
177 bitNode *tmp;
178 if( tmp = getNodePoint( BT->leftChild, value ) )
179 return tmp;
180 if( tmp = getNodePoint( BT->rightChild, value ) )
181 return tmp;
182 return NULL;
183 }
184 }
185 */
186 if(!BT)
187 {
188 return NULL;
189 }
190 else
191 {
192 if( BT->data == value )
193 {
194 return BT;
195 }
196 //getNodePoint( BT->leftChild, value );
197 //getNodePoint( BT->rightChild, value );
198
199 bitNode *tmp = getNodePoint( BT->leftChild, value );
200 if(!tmp)
201 {
202 getNodePoint( BT->rightChild, value );
203 }
204 //follow statement can't be added to the code
205 //return tmp;
206 }
207 }
208
209 void _Binary_Tree::PreOrderTraverse(binTree BT)
210 {
211 //if( emptyBinaryTree() )
212 // {
213 //throw "Empty binary tree!Error in void _Binary_Tree::PreOrderTraverse(binTree BT) !
";
214 //return;
215 //}
216 if (BT)
217 {
218 cout << BT->data << " ";
219 PreOrderTraverse(BT->leftChild);
220 PreOrderTraverse(BT->rightChild);
221 }
222 }
223
224 void _Binary_Tree::InOrderTraverse(binTree BT)
225 {
226 if (BT)
227 {
228 InOrderTraverse(BT->leftChild);
229 cout << BT->data << " ";
230 InOrderTraverse(BT->rightChild);
231 }
232 //return 0;
233 }
234
235 void _Binary_Tree::PostOrderTraverse( binTree BT )
236 {
237 if (BT)
238 {
239 PostOrderTraverse(BT->leftChild);
240 PostOrderTraverse(BT->rightChild);
241 cout << BT->data << " ";
242 }
243 }
244
245 void _Binary_Tree::destroy( binTree BT )
246 {
247 if(BT)
248 {
249 destroy( BT->leftChild );
250 destroy( BT->rightChild );
251 delete BT;
252 BT = NULL;
253 }
254 }
255
256 void _Binary_Tree::level( binTree BT, int number )
257 {
258
259 if(BT)
260 {
261 level( BT->leftChild, number + 1 );
262 ///number +=3;
263 //cout << number << endl;
264 cout << BT->data << " level: " << number << endl;
265
266 level( BT->rightChild, number + 1 );
267 //number -=2;
268 }
269 //number --;
270 }
271
272 int _Binary_Tree::height( binTree BT )
273 {
274 if(!BT)
275 {
276 return 0;
277 }
278 else
279 {
280 int i = height( BT->leftChild );
281 int j = height( BT->rightChild );
282 return i < j ? j + 1 : i + 1;
283
284 }
285 }
286
287 int _Binary_Tree::numberOfBTreeNode( binTree BT )
288 {
289 if(!BT)
290 return 0;
291 else
292 {
293 return numberOfBTreeNode( BT->leftChild ) + numberOfBTreeNode( BT->rightChild ) + 1;
294 }
295 }
296
297 int _Binary_Tree::numberOfBTreeLeafNode( binTree BT, int &number )
298 {
299 if(!BT)
300 {
301 return 0;
302 }
303 else
304 {
305 if( !BT->leftChild && !BT->rightChild )
306 //number += 1;
307 number ++;
308 //return 1;
309 else
310 {
311 numberOfBTreeLeafNode( BT->leftChild, number );
312 numberOfBTreeLeafNode( BT->rightChild, number );
313 }
314 return number;
315 }
316 }
317
318 void _Binary_Tree::numberOfNodeDegreeTwo( binTree BT, int &number )
319 {
320 if(!BT)
321 {
322 return;
323 }
324 else
325 {
326 if( BT->leftChild && BT->rightChild )
327 //number += 1;
328 number += 1;
329 //return 1;
330 //else
331 //{
332 numberOfNodeDegreeTwo( BT->leftChild, number );
333 numberOfNodeDegreeTwo( BT->rightChild, number );
334 //return numberOfNodeDegreeTwo( BT->leftChild, number ) + numberOfNodeDegreeTwo( BT->rightChild, number );
335 //}
336 //return number;
337 }
338 }
339
340 /*
341 void _Binary_Tree::family( binTree BT, elementType1 number )
342 {
343 if(!BT)
344 {
345 return;
346 }
347 if( BT->leftChild->data == number || BT->rightChild->data == number )
348 {
349 cout << "parent ---- " << BT->data << endl;
350 if( BT->leftChild->data == number && BT->rightChild )
351 {
352 cout << "rights sibling ---- " << BT->rightChild->data << endl;
353 }
354 if( BT->leftChild && BT->rightChild->data == number )
355 {
356 cout << "left sibling ---- " << BT->leftChild->data << endl;
357 }
358 }
359 if( BT->data == number && ( BT->leftChild || BT->rightChild ) )
360 {
361 cout << ( BT->leftChild ? "left child ---- " : true ) << endl;
362 cout << ( BT->rightChild ? "right child ---- " : true ) << endl;
363 }
364 family( BT->leftChild, number );
365 family( BT->rightChild, number );
366 //if( BT->data == number && BT-)
367 //if( BT->leftChild->data == number &&)
368 }
369 */
370
371 //bool _Binary_Tree::getParent( binTree BT, elementType number, bool flag )
372 void _Binary_Tree::getParent( binTree BT, elementType value, bool &flag )
373 {
374 if(!BT)
375 {
376 //return false;
377 return;
378 }
379 if( ( BT->leftChild && BT->leftChild->data == value ) || ( BT->rightChild ) && ( BT->rightChild->data == value ) )
380 {
381 flag = true;
382 cout << value << " Parent ---- " << BT->data << endl;
383 return;
384 //return true;
385 }
386 /*
387 if( BT && BT->rightChild->data == number )
388 {
389 cout << "parent ---- " << BT->data << endl;
390 return true;
391 }
392 */
393 getParent( BT->leftChild, value, flag );
394 getParent( BT->rightChild, value, flag );
395 }
396
397 binTree _Binary_Tree::getParent( binTree BT, elementType value )
398 {
399
400 if( !_exit( BT, value ) )
401 {
402 cerr << value << " is not in the binary tree!" << endl;
403 cerr << "Error in binTree _Binary_Tree::getParent( binTree BT, elementType value )!" << endl;
404 return NULL;
405 }
406
407 if(!BT)
408 {
409 return NULL;
410 }
411 if( BT->data == value )
412 {
413 return BT;
414 }
415 if( ( BT->leftChild && BT->leftChild->data == value ) || ( BT->rightChild && BT->rightChild->data == value ) )//|| BT->rightChild->data == value )
416 {
417 return BT;
418 }
419 bitNode *tmp = getParent( BT->leftChild, value );
420 if(!tmp)
421 {
422 getParent( BT->rightChild, value );
423 }
424 }
425
426 void _Binary_Tree::getSibling( binTree BT, elementType value, bool &flag )
427 {
428 if(!BT)
429 {
430 cout << value << " No LeftSibling!" << endl << value << " No RightSibling!" << endl;
431 return;
432 }
433 if( !flag && !BT->leftChild )//|| !BT->rightChild )//write as "if(!BT)" would result error
434 {
435
436 if( BT->rightChild )
437 {
438 getSibling( BT->rightChild, value, flag );
439 //return;
440 }
441 else
442 {
443 //cout << value << " No LeftSibling!" << endl;
444 return;
445 }
446 return;//why would deleting the statement cause error!
447 }
448
449 if( !flag && !BT->rightChild )
450 {
451
452 if( BT->leftChild )
453 {
454 getSibling( BT->leftChild, value, flag );
455
456 }
457 else
458 {
459 //cout << value << "No LeftSibling!" << endl;
460 //cout << value << " No RightSibling!" << endl;
461 return;
462
463 }
464 return;//why would deleting the statement cause error!
465 }
466 if( BT->rightChild->data == value )
467 {
468 if( BT->leftChild )
469 {
470 flag = true;
471 cout << value << " LeftSibling ---- " << BT->leftChild->data << endl;
472 return;
473 }
474 else if( !BT->leftChild )
475 {
476 cout << value << " No LeftSibling!" << endl;
477 return;
478 }
479
480 }
481 if( BT->leftChild->data == value )
482 {
483 if( BT->rightChild )
484 {
485 flag = true;
486 cout << value << " RightSibling ---- " << BT->rightChild->data << endl;
487 return;
488 }
489 else if( !BT->rightChild )
490 {
491 cout << value << " No RightSibling!" << endl;
492 return;
493 }
494 }
495 getSibling( BT->leftChild, value, flag );
496 if( !flag && BT->rightChild )
497 getSibling( BT->rightChild, value, flag );
498 }
499
500 void _Binary_Tree::getSibling( binTree BT, elementType value )
501 {
502 bitNode *parent = getParent( BT, value );
503
504 if( BT->data == value )
505 {
506 cout << value << " is the root node,neither left sibling also useless right sibling!" << endl;
507 return;
508 }
509 if( !_exit( BT, value ) )
510 {
511 cout << value << " is not in the binary-tree!" << endl;
512 cerr << "Error in void _Binary_Tree::getSibling( binTree BT, elementType value )!" << endl;
513 return;
514 }
515 if( parent->leftChild && parent->leftChild->data == value )
516 {
517 if( parent->rightChild )
518 {
519 cout << value << " RightSibling ---- " << parent->rightChild->data << endl;
520 return;
521 }
522 else
523 {
524 cout << value << " No RightSibling!" << endl;
525 return;
526 }
527 }
528 if( parent->rightChild && parent->rightChild->data == value )
529 {
530 if( parent->leftChild )
531 {
532 cout << value << " LeftSibling ---- " << parent->leftChild->data << endl;
533 return;
534 }
535 else
536 {
537 cout << value << " No LeftSibling!" << endl;
538 return;
539 }
540 }
541 }
542
543 void _Binary_Tree::getChild( binTree BT, elementType value, bool &flag )//It costed me several minutes to
544 { //write and almost one hour to
545 /* //perfect the function
546 if( BT->leftChild )
547 {
548 getChild( BT->leftChild, value, flag );
549 }
550 if( BT->rightChild )
551 {
552 getChild( BT->rightChild, value, flag );
553 }
554 */
555
556 /*
557 if( !BT->leftChild )//|| !BT->rightChild )
558 {
559 if(flag)
560 {
561 cout << "No LeftChild! " << endl;
562 flag = true;
563 return;
564 }
565 else
566 {
567 cout << "No LeftChild! " << endl;
568 flag = false;
569 }
570 //return;
571 }
572 if( !BT->rightChild )
573 {
574 if(flag)
575 {
576 cout << "No RightChild! " << endl;
577 flag = true;
578 return;
579 }
580 else
581 {
582 cout << "No RightChild! " << endl;
583 flag = false;
584 }
585 }
586 */
587 //if(!BT)
588 // {
589 // return;
590 // }
591 if( !_exit( BT, value ) )
592 {
593 cerr << value << " is not in the binary tree!
Error in void _Binary_Tree::getChild( binTree BT, elementType value, bool &flag )" << endl;
594 return;
595 }
596 if( BT->data == value )//at first I neglected this detail that resulted wrong judgement at root-node
597 {
598 if( BT->leftChild )
599 {
600 flag = true;
601 cout << value << " LeftChild ---- " << BT->leftChild->data << endl;
602
603 }
604 else
605 {
606 cout << "No LeftChild!" << endl;
607
608 }
609 if( BT->rightChild )
610 {
611 flag = true;
612 cout << value << " RightChild ---- " << BT->rightChild->data << endl;
613 return;
614 }
615 else
616 {
617 cout << "No RightChild! " << endl;
618 return;
619 }
620 }
621 if( !BT->leftChild )
622 {
623 if( BT->rightChild )
624 {
625 getChild( BT->rightChild, value, flag );
626 }
627 return;
628 /*
629 if(flag)
630 {
631 return;
632 }
633 else
634 {
635 flag = false;
636 return;
637 }*/
638 }
639 if( !BT->rightChild )
640 {
641 if( BT->leftChild )
642 {
643 getChild( BT->leftChild, value, flag );
644 }
645 return;
646 //if(flag)
647 //{
648 // flag = false;
649 //}
650 /*
651 if(flag)
652 {
653 return;
654 }
655 else
656 {
657 flag = false;
658 return;
659 }*/
660 }
661 /*
662 if( BT->rightChild->data == value )
663 {
664 if( BT->rightChild->leftChild )
665 {
666 flag = true;
667 cout << value << " LeftChild ---- " << BT->rightChild->leftChild->data << endl;
668 //return;
669 }
670 else
671 {
672 cout << "No LeftChild!" << endl;
673 }
674 if( BT->rightChild->rightChild )
675 {
676 flag = true;
677 cout << value << " RightChild ---- " << BT->rightChild->rightChild->data << endl;
678 return;
679 }
680 else
681 {
682 cout << "No RightChild! " << endl;
683 return;
684 }
685 //else
686 //{
687 //flag = false;
688 // return;
689 //}
690 }
691 if( BT->leftChild->data == value )
692 {
693 if( BT->leftChild->leftChild )
694 {
695 flag = true;
696 cout << value << " LeftChild ---- " << BT->leftChild->leftChild->data << endl;
697 //return;
698 }
699 else
700 {
701 cout << "No LeftChild!" << endl;
702 }
703 if( BT->leftChild->rightChild )
704 {
705 flag = true;
706 cout << value << " RightChild ---- " << BT->leftChild->rightChild->data << endl;
707 return;
708 }
709 else
710 {
711 cout << "No RightChild! " << endl;
712 return;
713 }
714 //else
715 //{
716 //flag = false;
717 // return;
718 //}
719 }
720 */
721 getChild( BT->leftChild, value, flag );
722 getChild( BT->rightChild, value, flag );
723 }
724
725 int _Binary_Tree::levelJudge( binTree BT, elementType value, int &number, int level )
726 {
727 bitNode *position = getNodePoint( getNodePoint(), value );
728 if(!position)
729 {
730 cout << "The value you typed is not in the binary tree!" << endl;
731 //return -1;
732 number = -1;
733 return number;
734 }
735 /*
736 int level;
737 if ( BT == NULL )
738 return 0;
739 else if ( BT->data == value )
740 return number;
741 else
742 {
743 number ++;
744 level = levelJudge( BT->leftChild, value, number );
745 if ( level != 0 )
746 return number;
747 else
748 {
749 //number ++;
750 return levelJudge( BT->rightChild, value, number );
751 }
752 }
753 */
754 if(BT)
755 {
756 if( BT->data == value )
757 {
758 //number ++;
759 number = level;
760 }
761 //number ++;
762 levelJudge( BT->leftChild, value, number, level + 1 );
763 //number ++;
764 levelJudge( BT->rightChild, value, number, level + 1);
765 }
766 }
767
768 void _Binary_Tree::exchangeLeftAndRightSibling( binTree BT )
769 {
770 if( BT && BT->leftChild && BT->rightChild )
771 {
772 bitNode *tmp = BT->leftChild;
773 BT->leftChild = BT->rightChild;
774 BT->rightChild = tmp;
775 exchangeLeftAndRightSibling( BT->leftChild );
776 exchangeLeftAndRightSibling( BT->rightChild );
777 }
778 }
779
780 void _Binary_Tree::copyBTree( binTree BT1, binTree BT )
781 {
782 bitNode *tmp = NULL;//new bitNode;
783 BT1->data = BT->data;
784 if( BT->leftChild )
785 {
786 BT1->leftChild = new bitNode;
787 tmp = BT1->leftChild;
788 tmp->leftChild = NULL;
789 tmp->rightChild = NULL;
790 copyBTree( tmp, BT->leftChild );
791 }
792 if( BT->rightChild )
793 {
794 BT1->rightChild = new bitNode;
795 tmp = BT1->rightChild;
796 tmp->leftChild = NULL;
797 tmp->rightChild = NULL;
798 copyBTree( tmp, BT->rightChild );
799 }
800 }
801
802 void _Binary_Tree::levelOrderTraverse( binTree BT )
803 {
804 clq.enQueue(BT);
805 while( !clq.emptyCharLinkedQueue() )
806 {
807 //CLNode *tmp = NULL;
808 clq.getFront(BT);
809 cout << BT->data << " ";
810 clq.deQueue();
811 if( BT->leftChild != NULL )
812 {
813 clq.enQueue( BT->leftChild );
814 }
815 if( BT->rightChild != NULL )
816 {
817 clq.enQueue( BT->rightChild );
818 }
819 }
820 }
821
822 void _Binary_Tree::allLeafToRootPath( binTree BT, char *path, int &pathLength )
823 {
824 if(BT)
825 {
826 if( !BT->leftChild && !BT->rightChild )
827 {
828 path[pathLength] = BT->data;
829 cout << BT->data << " leaf to root path: " << endl;
830 for( int i = pathLength; i >= 0; i -- )
831 {
832 if( i != 0 )
833 cout << path[i] << " --> ";
834 else
835 cout << path[i] << "
";
836 }
837 //cout << endl;
838 }
839 else
840 {
841 path[ pathLength ++ ] = BT->data;
842 allLeafToRootPath( BT->leftChild, path, pathLength );
843 allLeafToRootPath( BT->rightChild, path, pathLength );
844 pathLength --;
845 }
846 }
847 }
848
849 void _Binary_Tree::binaryTreeLongestPath( binTree BT, elementType *path, int &pathLength,
850 elementType *longestPath, int &longestLength )
851 {
852 if(BT)
853 {
854 if( !BT->leftChild && !BT->rightChild )
855 {
856 path[pathLength] = BT->data;
857 if( pathLength > longestLength)
858 {
859 //cout << BT->data << " leaf to root path: " << endl;
860 //longestPath = pathLength;
861 for( int i = pathLength; i >= 0; i -- )
862 {
863 /*
864 if( i != 0 )
865 cout << path[i] << " --> ";
866 else
867 cout << path[i] << "
";
868 */
869 longestPath[i] = path[i];
870 }
871 longestLength = pathLength;
872 }
873 //longestLength = pathLength;
874 //cout << endl;
875 }
876 else
877 {
878 path[ pathLength ++ ] = BT->data;
879 binaryTreeLongestPath( BT->leftChild, path, pathLength, longestPath, longestLength );
880 binaryTreeLongestPath( BT->rightChild, path, pathLength, longestPath, longestLength );
881 pathLength --;
882 }
883 }
884 }
885
886 binTree _Binary_Tree::nearestAncestor( binTree BT, bitNode *BNode1, bitNode *BNode2 )
887 {
888 // if( !_exit( BT, BNode1->data ) )
889 //{
890 // cout << BNode1->data << " is not in the binary tree!" << endl;
891 // return NULL;
892 //}
893 //if( !_exit( BT, BNode2->data ) )
894 //{
895 // cout << BNode2->data << " is not in the binary tree!" << endl;
896 // return NULL;
897 //}
898 if( !BT || !BNode1 || !BNode2 )
899 {
900 //cout << "NO ANCESTOR!" << endl;
901 return NULL;
902 }
903 if( BT == BNode1 || BT == BNode2 )
904 {
905 //cout << BT->data << endl;
906 return BT;
907 }
908 bitNode *left = nearestAncestor( BT->leftChild, BNode1, BNode2 );
909 bitNode *right = nearestAncestor( BT->rightChild, BNode1, BNode2 );
910 if( left && right )
911 {
912 //cout << BT->data << endl;
913 return BT;
914 }
915 else if(!left)
916 {
917 //cout << right->data << endl;
918 return right;
919 }
920 else
921 {
922 //cout << left->data << endl;
923 return left;
924 }
925 }
1 // BinaryTree.cpp : Defines the entry point for the console application.
2 //
3
4 #include "stdafx.h"
5 #include "_Binary_Tree.h"
6 #include "charLinkedQueue.h"
7
8
9 void test1()
10 {
11 _Binary_Tree BT1;
12 elementType strLine[100][3];
13 int nRow = 0, nLen = 0;
14 binTree index;
15 BT1.readFileToArray(strLine,nLen);
16 //BT1._Binary_Tree();
17
18 BT1.createBinaryTree( index,strLine, nLen, nRow);
19
20 cout << "The preorder traversal of sequence is" << endl;
21 BT1.PreOrderTraverse(BT1.getNodePoint());
22 cout << endl;
23 cout << "The middle order traversal of sequence is" << endl;
24 BT1.InOrderTraverse(BT1.getNodePoint());
25 cout << endl;
26 cout << "The post order traversal of sequence is" << endl;
27 BT1.PostOrderTraverse(BT1.getNodePoint());
28 cout << endl;
29 cout << "The level order traversal of sequence is" << endl;
30 BT1.levelOrderTraverse( BT1.getNodePoint() );
31 cout << endl;
32 int n = 1;
33 BT1.level( BT1.getNodePoint() , n );
34 cout << "BTree height: "<< BT1.height( BT1.getNodePoint() ) << endl;
35 cout << "Total node: " << BT1.numberOfBTreeNode( BT1.getNodePoint() ) << endl;
36 int m = 0;
37 cout << "Leaf node: " << BT1.numberOfBTreeLeafNode( BT1.getNodePoint(), m ) << endl;
38 int a = 0;
39 BT1.numberOfNodeDegreeTwo( BT1.getNodePoint(), a );
40 cout << "Node degree two: " << a << endl;
41 }
42
43 void test2()
44 {
45 _Binary_Tree BT1;
46 elementType strLine[100][3];
47 int nRow = 0, nLen = 0;
48 binTree index;
49 BT1.readFileToArray(strLine,nLen);
50 //BT1._Binary_Tree();
51
52 BT1.createBinaryTree( index,strLine, nLen, nRow);
53 char ch;
54 int key;
55 cout << "Please input a letter as operational character and a number to choose the operation,separated by space.
"1" for searching parent-node，"2" for searching sibiling-node and "3" for searching child-node." << endl;
56 while( cin>> ch >> key )
57 {
58 if( key == 1 )
59 {
60 bool flag = false;
61 bitNode *index = NULL;
62 index = BT1.getParent( BT1.getNodePoint(), ch );
63 if( index && index != BT1.getNodePoint() )
64 cout << ch << " parent ---- " << index->data << endl;
65 else if( index && index->data == ch )
66 cout << ch << " is the root node, no parent." << endl;
67 else if(index)
68 cout << ch << " parent ---- " << index->data << endl;
69 }
70 else if( key == 2 )
71 {
72 BT1.getSibling( BT1.getNodePoint(), ch );
73 }
74 else if( key == 3 )
75 {
76 bool flag;
77 BT1.getChild( BT1.getNodePoint(), ch, flag );
78 }
79 //Sleep( 1000 * 60 );
80 //system( "cls" );
81 //cout << "Please input a letter as operational character and a number to choose the operation,separated by space.
"1" for searching parent-node，"2" for searching sibiling-node and "3" for searching child-node." << endl;
82 }
83 }
84
85 void test3()
86 {
87 _Binary_Tree BT1;
88 elementType strLine[100][3];
89 int nRow = 0, nLen = 0;
90 binTree index;
91 BT1.readFileToArray(strLine,nLen);
92 //BT1._Binary_Tree();
93
94 BT1.createBinaryTree( index,strLine, nLen, nRow);
95
96 elementType value;
97 int cnt = 0;
98 cout << "Please input a letter and the program will judge it in which layer of the binary-tree!" << endl;
99 while( cin >> value )
100 {
101 int number = 1;
102 BT1.levelJudge( BT1.getNodePoint(), value , number, 1 );
103 cout << value << " ---- " << number << " level!" << endl;
104 cnt ++;
105 //Sleep( 1000 * 60 );
106 if( cnt % 10 == 0 )
107 system( "cls" );
108
109 cout << "Please input a letter and the program will judge it in which layer of the binary-tree!" << endl;
110 }
111 }
112
113 void test4()
114 {
115 elementType str[10000];
116 cout << "Please input a character array that will be transformed to the elements of a binary tree.
Attention the typed array must extend for the complete binary tree!" << endl;
117 while( cin >> str )
118 {
119 _Binary_Tree BT1(str);
120 cout << "The preorder traversal of sequence is" << endl;
121 BT1.PreOrderTraverse(BT1.getNodePoint());
122 cout << endl;
123 cout << "The middle order traversal of sequence is" << endl;
124 BT1.InOrderTraverse(BT1.getNodePoint());
125 cout << endl;
126 cout << "The post order traversal of sequence is" << endl;
127 BT1.PostOrderTraverse(BT1.getNodePoint());
128 cout << endl;
129 cout << "The level order traversal of sequence is" << endl;
130 BT1.levelOrderTraverse( BT1.getNodePoint() );
131 cout << endl;
132 int n = 1;
133 BT1.level( BT1.getNodePoint() , n );
134 cout << "BTree height: "<< BT1.height( BT1.getNodePoint() ) << endl;
135 cout << "Total node: " << BT1.numberOfBTreeNode( BT1.getNodePoint() ) << endl;
136 int m = 0;
137 cout << "Leaf node: " << BT1.numberOfBTreeLeafNode( BT1.getNodePoint(), m ) << endl;
138 int a = 0;
139 BT1.numberOfNodeDegreeTwo( BT1.getNodePoint(), a );
140 cout << "Node degree two: " << a << endl;
141 Sleep( 1000 * 60 );
142 system( "cls" );
143 cout << "Please input a character array that will be transformed to the elements of a binary tree.
Attention the typed array must extend for the complete binary tree!" << endl;
144 }
145 }
146
147 void test5()
148 {
149 _Binary_Tree BT1;
150 elementType strLine[100][3];
151 int nRow = 0, nLen = 0;
152 binTree index;
153 BT1.readFileToArray(strLine,nLen);
154 //BT1._Binary_Tree();
155
156 BT1.createBinaryTree( index,strLine, nLen, nRow);
157 cout << "The program will exchange the left subtree and right subtree of the file-inputed binary tree!" << endl;
158 cout << "The origin binary tree is as follow:" << endl;
159
160 cout << "The preorder traversal of sequence is" << endl;
161 BT1.PreOrderTraverse(BT1.getNodePoint());
162 cout << endl;
163 cout << "The middle order traversal of sequence is" << endl;
164 BT1.InOrderTraverse(BT1.getNodePoint());
165 cout << endl;
166 cout << "The post order traversal of sequence is" << endl;
167 BT1.PostOrderTraverse(BT1.getNodePoint());
168 cout << endl;
169 cout << "The level order traversal of sequence is" << endl;
170 BT1.levelOrderTraverse( BT1.getNodePoint() );
171 cout << endl;
172
173 BT1.exchangeLeftAndRightSibling( BT1.getNodePoint() );
174 cout << "The following for the exchange of binary tree:" << endl;
175 cout << "The preorder traversal of sequence is" << endl;
176 BT1.PreOrderTraverse(BT1.getNodePoint());
177 cout << endl;
178 cout << "The middle order traversal of sequence is" << endl;
179 BT1.InOrderTraverse(BT1.getNodePoint());
180 cout << endl;
181 cout << "The post order traversal of sequence is" << endl;
182 BT1.PostOrderTraverse(BT1.getNodePoint());
183 cout << endl;
184 cout << "The level order traversal of sequence is" << endl;
185 BT1.levelOrderTraverse( BT1.getNodePoint() );
186 cout << endl;
187 }
188
189 void test6()
190 {
191 _Binary_Tree BT1;
192 elementType strLine[100][3];
193 int nRow = 0, nLen = 0;
194 binTree index;
195 BT1.readFileToArray(strLine,nLen);
196 //BT1._Binary_Tree();
197
198 BT1.createBinaryTree( index,strLine, nLen, nRow);
199 cout << "The program will copy the file-inputed binary tree to another empty one!" << endl;
200 _Binary_Tree BT2;
201
202 cout << "The origin binary tree is as follow:" << endl;
203 cout << "The preorder traversal of sequence is" << endl;
204 BT1.PreOrderTraverse(BT1.getNodePoint());
205 cout << endl;
206 cout << "The middle order traversal of sequence is" << endl;
207 BT1.InOrderTraverse(BT1.getNodePoint());
208 cout << endl;
209 cout << "The post order traversal of sequence is" << endl;
210 BT1.PostOrderTraverse(BT1.getNodePoint());
211 cout << endl;
212 cout << "The level order traversal of sequence is" << endl;
213 BT1.levelOrderTraverse( BT1.getNodePoint() );
214 cout << endl;
215
216 cout << "The empty binary tree is as follow:" << endl;
217
218 cout << "The preorder traversal of sequence is" << endl;
219 BT2.PreOrderTraverse(BT2.getNodePoint());
220 cout << endl;
221 cout << "The middle order traversal of sequence is" << endl;
222 BT2.InOrderTraverse(BT2.getNodePoint());
223 cout << endl;
224 cout << "The post order traversal of sequence is" << endl;
225 BT2.PostOrderTraverse(BT2.getNodePoint());
226 cout << endl;
227 cout << "The level order traversal of sequence is" << endl;
228 BT2.levelOrderTraverse( BT2.getNodePoint() );
229 cout << endl;
230
231 cout << "The following for the copy of binary tree:" << endl;
232
233 BT1.copyBTree( BT2.getNodePoint(), BT1.getNodePoint() );
234
235 cout << "The preorder traversal of sequence is" << endl;
236 BT2.PreOrderTraverse(BT2.getNodePoint());
237 cout << endl;
238 cout << "The middle order traversal of sequence is" << endl;
239 BT2.InOrderTraverse(BT2.getNodePoint());
240 cout << endl;
241 cout << "The post order traversal of sequence is" << endl;
242 BT2.PostOrderTraverse(BT2.getNodePoint());
243 cout << endl;
244 cout << "The level order traversal of sequence is" << endl;
245 BT2.levelOrderTraverse( BT2.getNodePoint() );
246 cout << endl;
247
248 }
249
250 void test7()
251 {
252 _Binary_Tree BT1;
253 elementType strLine[100][3];
254 int nRow = 0, nLen = 0;
255 binTree index;
256 BT1.readFileToArray(strLine,nLen);
257 //BT1._Binary_Tree();
258
259 BT1.createBinaryTree( index,strLine, nLen, nRow);
260 cout << "The program will output the paths that each leaf node of the binary tree to the root node." << endl;
261
262 cout << "The origin binary tree is as follow:" << endl;
263 cout << "The preorder traversal of sequence is" << endl;
264 BT1.PreOrderTraverse(BT1.getNodePoint());
265 cout << endl;
266 cout << "The middle order traversal of sequence is" << endl;
267 BT1.InOrderTraverse(BT1.getNodePoint());
268 cout << endl;
269 cout << "The post order traversal of sequence is" << endl;
270 BT1.PostOrderTraverse(BT1.getNodePoint());
271 cout << endl;
272 cout << "The level order traversal of sequence is" << endl;
273 BT1.levelOrderTraverse( BT1.getNodePoint() );
274 cout << endl;
275
276 int pathLength = 0;
277 elementType *path = new char[ BT1.numberOfBTreeNode( BT1.getNodePoint() ) ];
278 BT1.allLeafToRootPath( BT1.getNodePoint(), path, pathLength );
279
280 }
281
282 void test8()
283 {
284 _Binary_Tree BT1;
285 elementType strLine[100][3];
286 int nRow = 0, nLen = 0;
287 binTree index;
288 BT1.readFileToArray(strLine,nLen);
289 //BT1._Binary_Tree();
290
291 BT1.createBinaryTree( index,strLine, nLen, nRow);
292 cout << "The program will ouput the level order traversal of the file-inputed binary tree." << endl;
293 cout << "The level order traversal of sequence is" << endl;
294 BT1.levelOrderTraverse( BT1.getNodePoint() );
295 cout << endl;
296 }
297
298 void test9()
299 {
300 _Binary_Tree BT1;
301 char strLine[100][3];
302 int nRow = 0, nLen = 0;
303 binTree index;
304 BT1.readFileToArray(strLine,nLen);
305 //BT1._Binary_Tree();
306
307 BT1.createBinaryTree( index,strLine, nLen, nRow);
308
309 cout << "Please input two character and the program will output their nearset ancestor." << endl;
310 elementType ch1, ch2;
311 while( cin >> ch1 >> ch2 )
312 {
313 //BT1.nearestAncestor( binTree BT, bitNode *BNode1, bitNode *BNode2 );
314 bitNode *index1 = BT1.getNodePoint( BT1.getNodePoint(), ch1 );
315
316 if(!index1)
317 {
318 cout << ch1 << " is not in the binary tree!" << endl;
319 }
320
321 bitNode *index2 = BT1.getNodePoint( BT1.getNodePoint(), ch2 );
322
323 if(!index2)
324 {
325 cout << ch2 << " is not in the binary tree!" << endl;
326 }
327
328 if( index1 && index2 )
329 {
330 bitNode *target = BT1.nearestAncestor( BT1.getNodePoint(), index1, index2 );
331 cout << "The nearset ancestor of " << ch1 << " and " << ch2 << " is " << target->data << endl;
332 }
333 cout << "Please input two character and the program will output their nearset ancestor." << endl;
334 }
335 }
336
337 void test10()
338 {
339 _Binary_Tree BT1;
340 char strLine[100][3];
341 int nRow = 0, nLen = 0;
342 binTree index;
343 BT1.readFileToArray(strLine,nLen);
344 //BT1._Binary_Tree();
345
346 BT1.createBinaryTree( index,strLine, nLen, nRow);
347 cout << "The program will output the longest path of the binary tree." << endl;
348 int pathLength = 0, longestLength = 0;
349 elementType *path1 = new char[ BT1.numberOfBTreeNode( BT1.getNodePoint() ) ];
350 elementType *longestPath = new char[ BT1.numberOfBTreeNode( BT1.getNodePoint() ) ];
351 BT1.binaryTreeLongestPath( BT1.getNodePoint(), path1, pathLength, longestPath, longestLength );
352 cout << "Longest path:" << endl;
353 for( int i = longestLength; i >= 0; i -- )
354 {
355 if( i!= 0 )
356 cout << longestPath[i] << " --> ";
357 else
358 cout << longestPath[i] << endl;
359
360 }
361 }
362
363 int main(int argc, char* argv[])
364 {
365 //test1();
366 test2();
367 //test3();
368 //test4();
369 //test5();
370 //test6();
371 //test7();
372 //test8();
373 //test9();
374 //test10();
375 return 0;
376 }
6.6 调试过程中出现的bug总结
往事不堪回首。
刚开始应该写成将data写成string或者直接将整个函数写成模板的，写完了最后测试时才发现现在的写法有诸多不便；但修改的话就又要重构一遍，懒得整了。
刚开始尝试写英文注释的，后面知难而退了；不过原来的英文注释我保留了。
附测试数据及对应二叉树图形：
bt4.btr
BinaryTree
A 0 1
B 0 1
C 0 1
D 0 0
bt8.btr
BinaryTree
1 1 1
2 1 1
3 1 1
4 0 0
5 0 0
6 0 1
7 0 0
8 0 0
bt9.btr
BinaryTree
a 1 1
b 1 1
d 0 0
e 1 1
g 0 0
h 0 0
c 1 0
f 0 1
i 0 0
bt10.btr
BinaryTree
A 1 1
B 1 1
C 0 0
D 1 0
E 0 0
F 1 1
G 0 1
H 0 0
I 1 0
J 0 0
bt12.btr
BinaryTree
A 1 1
B 1 1
C 0 0
D 1 1
E 0 0
F 0 0
G 1 1
H 1 1
I 0 0
J 1 0
K 0 0
L 0 0
bt14.btr
BinaryTree
A 1 0
B 1 1
C 1 1
D 0 1
E 0 0
F 1 0
G 0 1
H 0 0
I 1 0
J 1 1
K 0 0
L 1 0
M 1 0
N 0 0
bt15.btr
BinaryTree
A 1 1
B 1 1
D 1 0
G 0 0
E 1 1
H 0 0
I 0 0
C 0 1
F 1 1
J 1 1
L 0 0
M 0 1
N 1 0
O 0 0
K 0 0
bt21.btr
BinaryTree
a 1 1
b 1 1
c 1 1
d 1 1
e 0 0
f 0 0
g 0 0
h 1 1
i 0 0
j 0 0
k 1 1
l 1 1
m 0 0
n 0 0
o 1 1
p 0 1
q 0 0
r 1 1
s 0 0
t 1 0
u 0 0
bt261.btr
BinaryTree
a 1 1
b 1 1
c 1 1
d 1 1
e 0 0
f 0 0
g 1 0
h 0 0
i 1 1
j 0 1
k 0 0
l 1 0
m 0 0
n 1 1
o 1 1
p 1 1
q 0 0
r 0 0
s 0 0
t 1 1
u 1 1
v 0 0
w 0 0
x 1 1
y 0 0
z 0 0
bt262.btr
BinaryTree
a 1 1
b 1 1
c 1 1
d 0 1
e 1 1
f 0 1
g 0 0
h 1 1
i 0 0
j 0 0
k 1 1
l 0 0
m 0 0
n 1 1
o 0 0
p 0 0
q 1 1
r 0 1
s 1 1
t 0 0
u 0 0
v 1 1
w 0 1
x 0 0
y 0 1
z 0 0
full4.btr
BinaryTree
a 1 1
b 1 1
c 1 1
d 0 0
e 0 0
f 1 1
g 0 0
h 0 0
i 1 1
j 1 1
k 0 0
l 0 0
m 1 1
n 0 0
o 0 0
full5.btr
BinaryTree
a 1 1
b 1 1
c 1 1
d 1 1
e 0 0
f 0 0
g 1 1
h 0 0
i 0 0
j 1 1
k 1 1
l 0 0
m 0 0
n 1 1
o 0 0
p 0 0
q 1 1
r 1 1
s 1 1
t 0 0
u 0 0
v 1 1
w 0 0
x 0 0
y 1 1
z 1 1
1 0 0
2 0 0
3 1 1
4 0 0
5 0 0
