Visual C++ 6.0调试功能图解教程(3)--实例二
树和二叉树
1.实验目的
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={
基本操作:
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
3#include
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]; //存储队列的数组个数
20int front,rear; //队头,队尾
21public:
22 SeQueue();
23 ~SeQueue();
24void AddQ(NodeType x); //入队函数
25 NodeType DelQ(); //出队函数
26int IsEmpty() //判断队列非空函数
27 {
28return front == rear;
29 }
30};
31
32//二叉树
33class BiTree:public SeQueue //定义二叉树类BiTree 作为队列类SeQueue的派生类
34{
35public:
36 BiTree(){ root = NULL; } //构造函数
37 ~BiTree(){ destroy(root); } //析构函数
38void preorder() //先序遍历
39 { preorder(root); }
40void inorder() //中序遍历
41 { inorder(root); }
42void postorder() //后序遍历
43 { postorder(root); }
44
45void preordertswap() //交换左右子树
46 { preorderswap(root); }
47int theight() //求二叉树高度
48 { return height(root); }
49int tleaves() //求二叉树叶子结点个数
50 { return leaves( root ); }
51void levelorder() //按层遍历
52 { levelorder(root); }
53void creat0(); //建立树函数
54private:
55 NodeType *root; //数据成员，根结点
56 NodeType *creat(); //建立二叉树递归算法
57void preorder(NodeType *p); //先序遍历递归算法
58void inorder(NodeType *p); //中序遍历递归算法
59void postorder(NodeType *p); //后序遍历递归算法
60void levelorder(NodeType *p); //按层遍历算法
61void preorderswap(NodeType *p); //利用先序遍历方法交换左右子树 62int height(NodeType *p); //求二叉树高度递归算法
63int leaves(NodeType *p); //求二叉树叶子结点个数的递归算法 64void 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;
83if( x == 0 ) //若左或右孩子为空,置当前指针这空.
84 p = NULL;
85else {
86 p = new NodeType;
87 p->data = x;
88 p->lch = creat(); //递归调用自身
89 p->rch = creat();
90 }
91return p;
92}
93
94//先序遍历递归算法
95void BiTree::preorder(NodeType *p) //先序遍历显示
96{
97if( p != NULL)
98 {
99 cout << p->data;
100 preorder( p->lch ); //递归调用自身
101 preorder( p->rch ); //递归调用自身
102 }
103else
104 cout <<"#";
105}
106//中序遍历递归算法
107void BiTree::inorder(NodeType *p) //中序遍历显示
108{
109
110if( p != NULL )
111 {
112 inorder( p->lch ); //递归调用自身
113 cout << p->data;
114 inorder( p->rch ); //递归调用自身
115 }
116else
117 cout << "#";
118
119}
120//后序遍历递归算法
121void BiTree::postorder(NodeType *p)
122{
123if( p != NULL )
124 {
125
126 postorder( p-> lch ); //递归调用自身
127 postorder( p-> rch ); //递归调用自身
128 cout << p->data;
129 }
130else
131 cout <<"#";
132}
133void BiTree::preorderswap(NodeType *p) //利用先序遍历方法交换左右子树134{
135if( p != NULL )
136 {
137 NodeType *r;
138 r = p->lch;
139 p->lch = p->rch;
140 p->rch = r;
141//上面几条语句可以认为对结点的访问（交换左右孩子）
142//替换了原来的：cout<
143 preorderswap( p->lch ); //递归调用自身
144 preorderswap( p->rch );
145 }
146}
147void BiTree::destroy(NodeType* &p) //删除二叉树所有结点
148{
149if(p != NULL)
150 { destroy( p->lch );
151 destroy( p->rch );
152 delete p;
153 p = NULL;
154 }
155}
156int BiTree::height(NodeType *p) //求二叉树高度递归算法
157{
158int hl,hr;
159if( p != NULL )
160 {
161 hl = height( p->lch );
162 hr = height( p->rch );
163return ( hl > hr ? hl : hr ) + 1; //当前结点高度是以最大的(左右)子树的高度加得到
164
165 }
166else
167return 0;
168
169}
170//求二叉树叶子结点个数的递归算法
171int BiTree::leaves(NodeType *p)
172{
173if( p == NULL ) //当前结点是否为空,当为空时就没有左右孩子
174return 0;
175if( ( p-> lch == NULL ) && ( p-> rch == NULL )) //当前结点是否有左右孩子
176 {
177return 1;
178 }
179return leaves( p-> lch ) + leaves( p-> rch ); //递归调用自身累加叶子结点个数180}
181
182//按层遍历算法
183void BiTree::levelorder(NodeType *p)
184{
185 SeQueue q; //初始化一个队列
186 NodeType *t = p;
187if (p)
188 {
189 q.AddQ(*p); //根结点非空则入队
190 }
191while (!q.IsEmpty())
192 {
193 t = &(q.DelQ()); //队非空则将结点指针出队
194 cout << t->data; //并打印输出结点的数据值
195if (t->lch)
196 {
197 q.AddQ(*(t->lch)); //存在左孩子则将其进队
198 }
199else
200 cout << "#";
201
202if (t->rch)
203 {
204 q.AddQ(*(t->rch)); //存在右孩子则将其进队
205 }
206else
207 cout << "#";
208 }
209}
210
211//--------------------------------------------------------------------------- 212int main()
213{
214int k;
215 BiTree root0; //声明创建二叉树对象，调用构造函数
216do{ 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;
226switch(k)
227 {
228case 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;
238case 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;
248case 3:{
249 cout << "\n\t 按层序遍历结果:";
250 root0.levelorder();
251 } break;
252case 4:{
253int deep;
254 deep = root0.theight();
255 cout << "\n\t 树的深度是:" << deep;
256 } break;
257case 5:{
258int leaf;
259 leaf = root0.tleaves();
260 cout << "\n\t 树的叶子结点个数是:" << leaf; 261 } break;
262case 6: exit(0);
263 } // switch
264cout<<"\n ----------------";
265 } while(k>=0 && k<6);
266return 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{
281if((rear+1) % MAXSIZE==front)
282 cout<<"QUEUE IS FULL\n";
283else
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;
295if(front==rear)
296 {
297return *t; //返回空指针
298 }
299
300else
301 {
302 front = (front+1) % MAXSIZE;
303 q = elem[front];
304return 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)窗口中得到更好的观察效果.
1.将光标移置BiTree.cpp文件的void BiTree::levelorder(NodeType *p)和第一条语句处Ctrl+F10开
始调试
2.选择1.后输入1240003500600.(如右图的一棵二叉树)再选
择3.
3.这时Debugger仍停留在void BiTree::levelorder(NodeType *p)的第一条语句上.可以从自动监视
窗口中看到已经建立了一棵二叉树,指针P指向二叉树的根结点.
4.在监视窗口1中输入变量名:q,t进行观察,F10单步调试,这时Debugger停留在 SeQueue q; 语
句处
可以在监视1窗口中看到对象q的指针t都未合法初始化.
5.断续F10单步调试两步,这时Debugger停留在if(p)语句处,如图:
在监视1窗口输入!p进行观察,这时!p值为0,即if(p)判断语句值为真.
可以进入f(p)执行,F10断续,当Debugger停留在q.AddQ(*p)语句时可以从调用堆栈窗口中看到现在调用的函数为F11步入SeQueue类的AddQ(*p)函数.
6.这进Debugger停留在AddQ(*p)函数的第一条语句上.同可以从调用堆栈窗口中看到现在调用的
函数为AddQ(*p)
在监视2窗口中输入rear,elem[rear]进行观察.同时在自动窗口中可以看到变量X已经指向二叉树的根结点.
7.断续F10真到AddQ(NodeType x)结束语句处,可以从监视2窗口看到根结点已经入队
8.F10后可以看到调用堆栈窗口中当前调用的是levelorder(NodeType *p)函数,同时在监视1窗口中
输入!q.IsEmpty()观察到值为true,即可以进入while()控制语句执行.
F10单步至 t = &(q.DelQ())处,并F11步入q.DelQ(),这时Debugger停留在DelQ()的第一条语句上,可以从调用堆栈窗口中看到当前调用的是DelQ()函数.
9.在监视3窗口中输入q进行观察.断续F10到Debugger停留在DelQ()函数的return q语句时可以
从监视窗口3中看到根结点已经出队
同时在自动窗口中可以看到从DelQ()函数返回了出队结点并赋给了指针t
10.F10单步调试直到Debugger停留在levelorder(NodeType *p)函数的cout << t->data语句上,这
时可以在调用堆栈窗口中看到当前调用的是levelorder(NodeType *p)函数,在监视窗口1中输入t->date进行观察,已经取得根结点数据域的值
11.F10单步调试一步可以在DOS窗口中看到已经输出根结点
12.Shift+F5退出调试,完成调试演示.