Visual C++ 60调试功能 图解教程(3)--实例.doc

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|aiIntegerSet,i=0,1,2,n,n0 数据关系：R=|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.h2/#include3#include/VisualStudio2008中要求的4#includestdlib.h5#defineMAXSIZE26typedefintElemType;7usingnamespacestd;/VisualStudio2008中要求的89structNodeType/定义结点结构体1011ElemTypedata;12NodeType*lch,*rch;13;1415/队列16classSeQueue/定义队列类SeQueue1718private:19NodeTypeelemMAXSIZE;/存储队列的数组个数20intfront,rear;/队头,队尾21public:22SeQueue();23SeQueue();24voidAddQ(NodeTypex);/入队函数25NodeTypeDelQ();/出队函数26intIsEmpty()/判断队列非空函数2728returnfront=rear;2930;3132/二叉树33classBiTree:publicSeQueue/定义二叉树类BiTree作为队列类SeQueue的派生类3435public:36BiTree()root=NULL;/构造函数37BiTree()destroy(root);/析构函数38voidpreorder()/先序遍历39preorder(root);40voidinorder()/中序遍历41inorder(root);42voidpostorder()/后序遍历43postorder(root);4445voidpreordertswap()/交换左右子树46preorderswap(root);47inttheight()/求二叉树高度48returnheight(root);49inttleaves()/求二叉树叶子结点个数50returnleaves(root);51voidlevelorder()/按层遍历52levelorder(root);53voidcreat0();/建立树函数54private:55NodeType*root;/数据成员，根结点56NodeType*creat();/建立二叉树递归算法57voidpreorder(NodeType*p);/先序遍历递归算法58voidinorder(NodeType*p);/中序遍历递归算法59voidpostorder(NodeType*p);/后序遍历递归算法60voidlevelorder(NodeType*p);/按层遍历算法61voidpreorderswap(NodeType*p);/利用先序遍历方法交换左右子树62intheight(NodeType*p);/求二叉树高度递归算法63intleaves(NodeType*p);/求二叉树叶子结点个数的递归算法64voiddestroy(NodeType*&p);/删除二叉树所有结点65;6667/BiTree.cpp68#includeBiTree.h6970voidBiTree:creat0()/建立树函数，7172cout请按照树的先序遍历顺序组织数据endl;73cout若结点信息是int，把每个结点的空孩子以输入;endl;74cout一个结点的二叉树，输入：00;endl;75root=creat();/调用私有creat()(工具函数);7677NodeType*BiTree:creat()/递归建立二叉树算法7879NodeType*p;80ElemTypex;81coutx;83if(x=0)/若左或右孩子为空,置当前指针这空.84p=NULL;85else86p=newNodeType;87p-data=x;88p-lch=creat();/递归调用自身89p-rch=creat();9091returnp;929394/先序遍历递归算法95voidBiTree:preorder(NodeType*p)/先序遍历显示9697if(p!=NULL)9899coutdata;100preorder(p-lch);/递归调用自身101preorder(p-rch);/递归调用自身102103else104coutlch);/递归调用自身113coutdata;114inorder(p-rch);/递归调用自身115116else117coutlch);/递归调用自身127postorder(p-rch);/递归调用自身128coutdata;129130else131coutlch;139p-lch=p-rch;140p-rch=r;141/上面几条语句可以认为对结点的访问（交换左右孩子）142/替换了原来的：coutdatalch);/递归调用自身144preorderswap(p-rch);145146147voidBiTree:destroy(NodeType*&p)/删除二叉树所有结点148149if(p!=NULL)150destroy(p-lch);151destroy(p-rch);152deletep;153p=NULL;154155156intBiTree:height(NodeType*p)/求二叉树高度递归算法157158inthl,hr;159if(p!=NULL)160161hl=height(p-lch);162hr=height(p-rch);163return(hlhr?hl:hr)+1;/当前结点高度是以最大的(左右)子树的高度加得到164165166else167return0;168169170/求二叉树叶子结点个数的递归算法171intBiTree:leaves(NodeType*p)172173if(p=NULL)/当前结点是否为空,当为空时就没有左右孩子174return0;175if(p-lch=NULL)&(p-rch=NULL)/当前结点是否有左右孩子176177return1;178179returnleaves(p-lch)+leaves(p-rch);/递归调用自身累加叶子结点个数180181182/按层遍历算法183voidBiTree:levelorder(NodeType*p)184185SeQueueq;/初始化一个队列186NodeType*t=p;187if(p)188189q.AddQ(*p);/根结点非空则入队190191while(!q.IsEmpty()192193t=&(q.DelQ();/队非空则将结点指针出队194coutdata;/并打印输出结点的数据值195if(t-lch)196197q.AddQ(*(t-lch);/存在左孩子则将其进队198199else200coutrch)203204q.AddQ(*(t-rch);/存在右孩子则将其进队205206else207cout#;208209210211/-212intmain()213214intk;215BiTreeroot0;/声明创建二叉树对象，调用构造函数216docoutnn;217coutnn1.建立二叉树;218coutnn2.交换左右子树;219coutnn3.按层序遍历树;220coutnn4.求二叉树深度;221coutnn5.求叶子结点个数;222coutnn6.结束程序运行;223coutn=;224coutk;226switch(k)227228case1:229coutnt输入（0）结束：;230root0.creat0();231coutnt先序遍历结果:;232root0.preorder();233coutnt中序遍历结果:;234root0.inorder();235coutnt后序遍历结果:;236root0.postorder();237break;238case2:239coutnt交换左右子树结果:;240root0.preordertswap();241coutnt先序遍历结果:;242root0.preorder();243coutnt中序遍历结果:;244root0.inorder();245coutnt后序遍历结果:;246root0.postorder();247break;248case3:249coutnt按层序遍历结果:;250root0.levelorder();251break;252case4:253intdeep;254deep=root0.theight();255coutnt树的深度是:deep;256break;257case5:258intleaf;259leaf=root0.tleaves();260coutnt树的叶子结点个数是:leaf;261break;262case6:exit(0);263/switch264cout=0&k6);266return0;267/-268269/Queue.cpp270#includeBiTree.h271SeQueue:SeQueue()/初始化队列272273front=0;274rear=0;275276277SeQueue:SeQueue();278/进队279voidSeQueue:AddQ(NodeTypex)280281if(rear+1)%MAXSIZE=front)282coutQUEUEISFULLn;283else284285rear=(rear+1)%MAXSIZE;286elemrear=x;/将结点指针入队287288289290/出队291NodeTypeSeQueue:DelQ()292293NodeTypeq;294NodeType*t=NULL;295if(front=rear)296297return*t;/返回空指针298299300else301302front=(front+1)%MAXSIZE;303q=elemfront;304returnq;/返回出栈的指针结点305306五.心得: 这次实验不仅能巩固理解递归的方法,另一方面很能考验运用指针的能力,还有就是数据类型要使用得当.从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