樹和二叉樹
-
實驗目的
1.熟悉二叉樹的二叉鏈表存儲結構；
2.掌握構造二叉樹的方法；
3.加深對二叉樹的遍歷的理解。
二.需求分析
本程序演示用C++編寫,完成按先序遍歷生成二叉樹,先序遍歷打印輸出二叉樹, 后序遍歷打印輸出二叉樹, 中序遍歷打印輸出二叉樹, 層序遍歷打印輸出二叉樹, 先序遍歷方法交換左右子樹,求樹的高度,求樹的葉子結點個數.
輸入值的范圍:建立一棵二叉時,要求結點的的左右孩子為空時輸入0代替.所有輸入值必須為整形.輸入的結點個數:若為單邊二叉樹(全只有左結點或全只有右結點)則為任意個數;若非單邊二叉則要求結點最多的層個數不得超過MAXSIZE的值.
輸出形式:輸出時如果結點的左右指針這空則以" #"代替輸出.
程序所能完成的功能:程序能完成按先序遍歷生成二叉樹,先序遍歷打印輸出二叉樹, 后序遍歷打印輸出二叉樹, 中序遍歷打印輸出二叉樹, 層序遍歷打印輸出二叉樹, 先序遍歷方法交換左右子樹,求樹的高度,求樹的葉子結點個數.操作.
測試數據
A建立二叉樹中輸入1230000 生成一棵樹123####
B交換左右子樹得到一棵二叉樹1#2#3##
C按層序遍歷樹得到一棵二叉樹1#2#3##
D求二叉樹的高度得到高度3
E求葉子結點個數得到個數1
三.設計概要
(1)為了實現上述程序的功能,需要定義二叉樹的抽象數據類型:
ADT BiTree is{
數據對象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
數據關系：R={<ai,ai+1>|ai,ai+1 ∈D}
基本操作:
creat()
操作結果:建立一棵二叉樹
preorder()
初始條件:二叉樹已經存在
操作結果:先序遍歷顯示二叉樹
preordertswap()
初始條件: 二叉樹已經存在
操作結果:交換二叉樹的左右子樹
theight()
初始條件: 二叉樹已經存在
操作結果:輸出二叉樹的高度
tleaves()
初始條件:
操作結果:輸出二叉樹的葉子結點個數
levelorder()
初始條件: 二叉樹已經存在
操作結果:層序遍歷顯示二叉樹
}ADT BiTree
(2) 本程序包含兩個類和一個結構體類型
A基類:隊列類SeQueue有5個函數
1.構造函數 SeQueue()
2.析構函數 ~SeQueue()
3.進隊函數 AddQ(NodeType x)
4.出隊函數 DelQ()
5.判斷非空函數 IsEmpty()
B派生類:二叉樹類BiTree有20個函數
1主函數 main()
2. 構造函數 BiTree()
3. 析構函數 ~BiTree()
4. 建立樹函數 creat0()
5. 先序遍歷函數 void preorder()
6. 中序遍歷函數 inorder()
7. 后序遍歷函數 postorder()
8.層序遍歷函數 levelorder()
9. 交換左右子樹函數 preordertswap()
10. 求二叉樹高度函數 theight()
11. 求二叉樹葉子結點個數函數 tleaves()
12. 建立二叉樹遞歸算法函數 *creat()
13. 先序遍歷遞歸算法函數 preorder(NodeType *p)
14. 中序遍歷遞歸算法函數 inorder(NodeType *p)
15. 后序遍歷遞歸算法函數 postorder(NodeType *p)
16. 按層遍歷算法函數 levelorder(NodeType *p)
17. 先序遍歷方法交換左右子樹函數 preorderswap(NodeType *p)
18. 求二叉樹高度遞歸算法函數 height(NodeType *p)
19. 求二叉樹葉子結點個數的遞歸算法函數 leaves(NodeType *p)
20. 刪除二叉樹所有結點函數 destroy(NodeType* &p)
C結構體類型NodeType
(3)本程序的三個文件
1.頭文件BiTree.h
2.源文件 Queue.cpp
BiTree.cpp
(4)函數之間的關系
四.詳細設計
1
//BiTree.h
2//#include <iostream.h>
3#include <iostream> // Visual Studio 2008中要求的
4#include "stdlib.h"
5#define MAXSIZE 2
6typedef int ElemType;
7using namespace std; // Visual Studio 2008中要求的
8
9struct NodeType //定義結點結構體
10
{
11
ElemType data;
12 NodeType *lch,*rch;
13
};
14
15//隊列
16class SeQueue //定義隊列類SeQueue
17{
18private:
19 NodeType elem[MAXSIZE]; //存儲隊列的數組個數
20 int front,rear; //隊頭,隊尾
21public:
22 SeQueue();
23 ~SeQueue();
24 void AddQ(NodeType x); //入隊函數
25 NodeType DelQ(); //出隊函數
26 int IsEmpty() //判斷隊列非空函數
27
{
28 return front == rear;
29
}
30};
31
32//二叉樹
33class BiTree:public SeQueue //定義二叉樹類BiTree 作為隊列類SeQueue的派生類
34{
35 public:
36 BiTree(){ root = NULL; } //構造函數
37 ~BiTree(){ destroy(root); } //析構函數
38 void preorder() //先序遍歷
39 { preorder(root); }
40 void inorder() //中序遍歷
41 { inorder(root); }
42 void postorder() //后序遍歷
43 { postorder(root); }
44
45 void preordertswap() //交換左右子樹
46 { preorderswap(root); }
47 int theight() //求二叉樹高度
48 { return height(root); }
49 int tleaves() //求二叉樹葉子結點個數
50 { return leaves( root ); }
51 void levelorder() //按層遍歷
52 { levelorder(root); }
53 void creat0(); //建立樹函數
54 private:
55 NodeType *root; //數據成員，根結點
56 NodeType *creat(); //建立二叉樹遞歸算法
57 void preorder(NodeType *p); //先序遍歷遞歸算法
58 void inorder(NodeType *p); //中序遍歷遞歸算法
59 void postorder(NodeType *p); //后序遍歷遞歸算法
60 void levelorder(NodeType *p); //按層遍歷算法
61 void preorderswap(NodeType *p); //利用先序遍歷方法交換左右子樹
62 int height(NodeType *p); //求二叉樹高度遞歸算法
63 int leaves(NodeType *p); //求二叉樹葉子結點個數的遞歸算法
64 void destroy(NodeType* &p); //刪除二叉樹所有結點
65};
66
67//BiTree.cpp
68#include "BiTree.h"
69
70void BiTree::creat0() //建立樹函數，
71 {
72 cout << "請按照樹的先序遍歷順序組織數據" << endl;
73 cout << "若結點信息是int，把每個結點的空孩子以輸入;" << endl;
74 cout << "一個結點的二叉樹，輸入：0 0;" << endl;
75 root = creat(); //調用私有creat()(工具函數);
76 }
77NodeType * BiTree::creat() //遞歸建立二叉樹算法
78{
79 NodeType *p;
80 ElemType x;
81 cout << "\n 輸入數據：";
82 cin >> x;
83 if( x == 0 ) //若左或右孩子為空,置當前指針這空.
84 p = NULL;
85 else {
86 p = new NodeType;
87 p->data = x;
88 p->lch = creat(); //遞歸調用自身
89 p->rch = creat();
90 }
91 return p;
92}
93
94//先序遍歷遞歸算法
95void BiTree::preorder(NodeType *p) //先序遍歷顯示
96{
97 if( p != NULL)
98 {
99 cout << p->data;
100 preorder( p->lch ); //遞歸調用自身
101 preorder( p->rch ); //遞歸調用自身
102 }
103 else
104 cout <<"#";
105}
106//中序遍歷遞歸算法
107void BiTree::inorder(NodeType *p) //中序遍歷顯示
108{
109
110 if( p != NULL )
111 {
112 inorder( p->lch ); //遞歸調用自身
113 cout << p->data;
114 inorder( p->rch ); //遞歸調用自身
115 }
116 else
117 cout << "#";
118
119}
120//后序遍歷遞歸算法
121void BiTree::postorder(NodeType *p)
122{
123 if( p != NULL )
124 {
125
126 postorder( p-> lch ); //遞歸調用自身
127 postorder( p-> rch ); //遞歸調用自身
128 cout << p->data;
129 }
130 else
131 cout <<"#";
132}
133void BiTree::preorderswap(NodeType *p) //利用先序遍歷方法交換左右子樹
134{
135 if( p != NULL )
136 {
137 NodeType *r;
138 r = p->lch;
139 p->lch = p->rch;
140 p->rch = r;
141//上面幾條語句可以認為對結點的訪問（交換左右孩子）
142//替換了原來的：cout<<p->data<<" "; 語句
143 preorderswap( p->lch ); //遞歸調用自身
144 preorderswap( p->rch );
145 }
146}
147void BiTree::destroy(NodeType* &p) //刪除二叉樹所有結點
148{
149 if(p != NULL)
150 { destroy( p->lch );
151 destroy( p->rch );
152 delete p;
153 p = NULL;
154 }
155}
156int BiTree::height(NodeType *p) //求二叉樹高度遞歸算法
157{
158 int hl,hr;
159 if( p != NULL )
160 {
161 hl = height( p->lch );
162 hr = height( p->rch );
163 return ( hl > hr ? hl : hr ) + 1; //當前結點高度是以最大的(左右)子樹的高度加得到
164
165 }
166 else
167 return 0;
168
169}
170//求二叉樹葉子結點個數的遞歸算法
171int BiTree::leaves(NodeType *p)
172{
173 if( p == NULL ) //當前結點是否為空,當為空時就沒有左右孩子
174 return 0;
175 if( ( p-> lch == NULL ) && ( p-> rch == NULL )) //當前結點是否有左右孩子
176 {
177 return 1;
178 }
179 return leaves( p-> lch ) + leaves( p-> rch ); //遞歸調用自身累加葉子結點個數
180}
181
182//按層遍歷算法
183void BiTree::levelorder(NodeType *p)
184{
185 SeQueue q; //初始化一個隊列
186 NodeType *t = p;
187 if (p)
188 {
189 q.AddQ(*p); //根結點非空則入隊
190 }
191 while (!q.IsEmpty())
192 {
193 t = &(q.DelQ()); //隊非空則將結點指針出隊
194 cout << t->data; //并打印輸出結點的數據值
195 if (t->lch)
196 {
197 q.AddQ(*(t->lch)); //存在左孩子則將其進隊
198 }
199 else
200 cout << "#";
201
202 if (t->rch)
203 {
204 q.AddQ(*(t->rch)); //存在右孩子則將其進隊
205 }
206 else
207 cout << "#";
208 }
209}
210
211//---------------------------------------------------------------------------
212int main()
213{
214 int k;
215 BiTree root0; //聲明創建二叉樹對象，調用構造函數
216 do{ cout<<"\n\n";
217 cout<<"\n\n 1. 建立二叉樹";
218 cout<<"\n\n 2. 交換左右子樹";
219 cout<<"\n\n 3. 按層序遍歷樹";
220 cout<<"\n\n 4. 求二叉樹深度 ";
221 cout<<"\n\n 5. 求葉子結點個數";
222 cout<<"\n\n 6. 結束程序運行";
223 cout<<"\n======================================";
224 cout<<"\n 請輸入您的選擇(0,1,2,3,4,5,6):";
225 cin>>k;
226 switch(k)
227 {
228 case 1:{
229 cout << "\n\t 輸入（0）結束：";
230 root0.creat0();
231 cout << "\n\t 先序遍歷結果:";
232 root0.preorder();
233 cout << "\n\t 中序遍歷結果:";
234 root0.inorder();
235 cout << "\n\t 后序遍歷結果:";
236 root0.postorder();
237 } break;
238 case 2:{
239 cout <<"\n\t 交換左右子樹結果:";
240 root0.preordertswap();
241 cout << "\n\t 先序遍歷結果:";
242 root0.preorder();
243 cout << "\n\t 中序遍歷結果:";
244 root0.inorder();
245 cout << "\n\t 后序遍歷結果:";
246 root0.postorder();
247 } break;
248 case 3:{
249 cout << "\n\t 按層序遍歷結果:";
250 root0.levelorder();
251 } break;
252 case 4:{
253 int deep;
254 deep = root0.theight();
255 cout << "\n\t 樹的深度是:" << deep;
256 } break;
257 case 5:{
258 int leaf;
259 leaf = root0.tleaves();
260 cout << "\n\t 樹的葉子結點個數是:" << leaf;
261 } break;
262 case 6: exit(0);
263 } // switch
264cout<<"\n ----------------";
265 } while(k>=0 && k<6);
266 return 0;
267}//-----
268
269//Queue.cpp
270#include "BiTree.h"
271SeQueue::SeQueue() //初始化隊列
272{
273 front=0;
274 rear=0;
275}
276
277SeQueue::~SeQueue(){};
278//進隊
279void SeQueue::AddQ(NodeType x)
280{
281 if((rear+1) % MAXSIZE==front)
282 cout<<"QUEUE IS FULL\n";
283 else
284 {
285 rear=(rear+1) % MAXSIZE;
286 elem[rear]=x; //將結點指針入隊
287 }
288}
289
290//出隊
291NodeType SeQueue::DelQ()
292{
293 NodeType q;
294 NodeType *t = NULL;
295 if(front==rear)
296 {
297 return *t; //返回空指針
298 }
299
300 else
301 {
302 front = (front+1) % MAXSIZE;
303 q = elem[front];
304 return q; //返回出棧的指針結點
305 }
306
五.心得:
這次實驗不僅能鞏固理解遞歸的方法,另一方面很能考驗運用指針的能力,還有就是數據類型要使用得當.從levelorder(NodeType *p)函數來看,首先, DelQ()的返回類型要與BiTree二叉樹結點指針的類型一至.其次,在遞歸過程中,傳入AddQ(NodeType x)是整個結點的內容而不是一個指針.值得討論的是,在定義存儲隊列的數組時如何節省存儲空間?因為輸入的結點個數:若為單邊二叉樹(全只有左結點或全只有右結點)則為任意個數(實驗上這時只需要兩個存儲空間);若非單邊二叉則要求結點最多的層個數不得超過MAXSIZE的值.后者時MAXSIZE的值(由性質2得)應該為2(h-1) (h為樹的高度).這一點如何實現呢?BiTree類是SeQueue類的子類,height()函數是BiTree類的函數,如果能把高度傳入SeQueue類的構造函數就可以通過一個for()語句來求得一個合適的值用以初始化MAXSIZE.那么就大大的節省了內存空間,并且還能實現輸入節點的個數為任意的.但把高度傳入SeQueue類的構造函數如何實現?還有其他要考慮的問題,我在今后的學習中深入了解.
六.使用說明
程序名為No4.exe運行環境為DOS,執行后顯示:
在" 請輸入您的選擇(0,1,2,3,4,5,6):"后輸入數字選擇執行的功能.
測試結果:
1)選擇1.后輸入1240003500600.(如右圖的一棵二叉樹)
2)選擇4得
3)選擇5得
4)選擇2得
5)選擇3得
6)選擇6或輸入非"0,1,2,3,4,5,6"的數字
七.調試過程
本程序主要對按層序遍歷操作功能進行調試.用Visual Studio 2008演示.首先把BiTree.h中的" #define MAXSIZE 30"改成" #define MAXSIZE 4",目的是從Visual Studio 2008的監視(Watch)窗口中得到更好的觀察效果.
- 將光標移置BiTree.cpp文件的void BiTree::levelorder(NodeType *p)和第一條語句處Ctrl+F10開始調試
- 選擇1.后輸入1240003500600.(如右圖的一棵二叉樹)
再選擇3.
-
這時Debugger仍停留在void BiTree::levelorder(NodeType *p)的第一條語句上.可以從自動監視窗口中看到已經建立了一棵二叉樹,指針P指向二叉樹的根結點.
-
在監視窗口1中輸入變量名:q,t進行觀察,F10單步調試,這時Debugger停留在 SeQueue q; 語句處
可以在監視1窗口中看到對象q的指針t都未合法初始化.
-
斷續F10單步調試兩步,這時Debugger停留在if(p)語句處,如圖:
在監視1窗口輸入!p進行觀察,這時!p值為0,即if(p)判斷語句值為真.
可以進入f(p)執行,F10斷續,當Debugger停留在q.AddQ(*p)語句時可以從調用堆棧窗口中看到現在調用的函數為F11步入SeQueue類的AddQ(*p)函數.
-
這進Debugger停留在AddQ(*p)函數的第一條語句上.同可以從調用堆棧窗口中看到現在調用的函數為AddQ(*p)
在監視2窗口中輸入rear, elem[rear]進行觀察.同時在自動窗口中可以看到變量X已經指向二叉樹的根結點.
-
斷續F10真到AddQ(NodeType x)結束語句處,可以從監視2窗口看到根結點已經入隊
-
F10后可以看到調用堆棧窗口中當前調用的是levelorder(NodeType *p)函數,同時在監視1窗口中輸入!q.IsEmpty()觀察到值為true,即可以進入while()控制語句執行.
F10單步至 t = &(q.DelQ())處,并F11步入q.DelQ(),這時Debugger停留在DelQ()的第一條語句上,可以從調用堆棧窗口中看到當前調用的是DelQ()函數.
-
在監視3窗口中輸入q進行觀察.斷續F10到Debugger停留在DelQ()函數的return q語句時可以從監視窗口3中看到根結點已經出隊
同時在自動窗口中可以看到從DelQ()函數返回了出隊結點并賦給了指針t
-
F10單步調試直到Debugger停留在levelorder(NodeType *p)函數的cout << t->data語句上,這時可以在調用堆棧窗口中看到當前調用的是levelorder(NodeType *p)函數,在監視窗口1中輸入t->date進行觀察,已經取得根結點數據域的值
-
F10單步調試一步可以在DOS窗口中看到已經輸出根結點
- Shift+F5退出調試,完成調試演示.