Visual_C++_6.0调试功能_图解教程(3)--实例

1、Visual C+ 6.0调试功能 图解教程(3)-实例二树和二叉树 1. 实验目的 1.熟悉二叉树的二叉链表存储结构； 2.掌握构造二叉树的方法； 3.加深对二叉树的遍历的理解。 二.需求分析     本程序演示用C+编写,完成按先序遍历生成二叉树,先序遍历打印输出二叉树, 后序遍历打印输出二叉树, 中序遍历打印输出二叉树, 层序遍历打印输出二叉树, 先序遍历方法交换左右子树,求树的高度,求树的叶子结点个数. 输入值的范围:建立一棵二叉时,要求结点的的左右孩子为空时输入0代替.所有输入值必须为整形.输入的结点个数:若为单边二叉树(全只有左结点或全只有右

2、结点)则为任意个数;若非单边二叉则要求结点最多的层个数不得超过MAXSIZE的值. 输出形式:输出时如果结点的左右指针这空则以" #"代替输出. 程序所能完成的功能:程序能完成按先序遍历生成二叉树,先序遍历打印输出二叉树, 后序遍历打印输出二叉树, 中序遍历打印输出二叉树, 层序遍历打印输出二叉树, 先序遍历方法交换左右子树,求树的高度,求树的叶子结点个数.操作. 测试数据 A建立二叉树中输入1230000 生成一棵树123# B交换左右子树得到一棵二叉树1#2#3# C按层序遍历树得到一棵二叉树1#2#3# D求二叉树的高度得到高度3 E求叶子结点个数得到个数1 三.设计

3、概要 (1)为了实现上述程序的功能,需要定义二叉树的抽象数据类型: ADT BiTree is 数据对象：D=ai|aiIntegerSet,i=0,1,2,n,n0 数据关系：R=<ai,ai+1>|ai,ai+1 D 基本操作: creat() 操作结果:建立一棵二叉树 preorder() 初始条件:二叉树已经存在 操作结果:先序遍历显示二叉树 preordertswap() 初始条件: 二叉树已经存在 操作结果:交换二叉树的左右子树 theight() 初始条件: 二叉树已经存在 操作结果:输出二叉树的高度 tleaves() 初始条件: 操作结果:输出二叉树的叶子结点个数

4、 levelorder() 初始条件: 二叉树已经存在 操作结果:层序遍历显示二叉树 ADT BiTree (2) 本程序包含两个类和一个结构体类型 A基类:队列类SeQueue有5个函数     1.构造函数                            SeQueue

5、()     2.析构函数                            SeQueue()     3.进队函数          

6、;                  AddQ(NodeType x)     4.出队函数                        

7、    DelQ()     5.判断非空函数                            IsEmpty() B派生类:二叉树类BiTree有20个函数     1主函数 

8、60;                              main() 2. 构造函数                 &

9、#160;          BiTree()     3. 析构函数                            BiTree()    

10、 4. 建立树函数                            creat0()     5. 先序遍历函数            

11、0;           void preorder()     6. 中序遍历函数                        inorder()     7. 后序

12、遍历函数                        postorder()     8.层序遍历函数                  

13、          levelorder()     9. 交换左右子树函数                    preordertswap()     10. 求二叉树高度函数   &#

14、160;                theight()     11. 求二叉树叶子结点个数函数                tleaves()     12. 建立二叉树递归算法函数 

15、;               *creat()     13. 先序遍历递归算法函数                preorder(NodeType *p)     14. 中序遍历递归算法函数 

16、               inorder(NodeType *p)     15. 后序遍历递归算法函数                postorder(NodeType *p)     16. 按层遍历

17、算法函数                    levelorder(NodeType *p)     17. 先序遍历方法交换左右子树函数            preorderswap(NodeType *p)   

18、  18. 求二叉树高度递归算法函数                height(NodeType *p)     19. 求二叉树叶子结点个数的递归算法函数    leaves(NodeType *p)     20. 删除二叉树所有结点函数    

19、0;           destroy(NodeType* &p) C结构体类型NodeType (3)本程序的三个文件 1.头文件BiTree.h 2.源文件     Queue.cpp         BiTree.cpp (4)函数之间的关系   四.详细设计    1/BiTree.h &#

20、160;2/#include <iostream.h>  3#include <iostream>    / Visual Studio 2008中要求的  4#include "stdlib.h"  5#define MAXSIZE 2      6typedef int ElemType;&

21、#160; 7using namespace std;    / Visual Studio 2008中要求的  8  9struct NodeType                         

22、;  /定义结点结构体 10        11    ElemType   data;                     12    NodeType 

23、 *lch,*rch; 13; 14 15/队列 16class SeQueue                                /定义队列类SeQueue 17   

24、;18private: 19       NodeType elemMAXSIZE;        /存储队列的数组个数 20        int front,rear;             &

25、#160;  /队头,队尾 21public: 22        SeQueue(); 23        SeQueue(); 24        void AddQ(NodeType x);       

26、 /入队函数 25        NodeType DelQ();            /出队函数 26        int IsEmpty()          &

27、#160;     /判断队列非空函数 27         28            return front = rear; 29         30; 31 32/二叉树

28、 33class BiTree:public SeQueue              /定义二叉树类BiTree 作为队列类SeQueue的派生类 34 35 public: 36     BiTree()    root = NULL;  

29、60;                 /构造函数 37     BiTree()    destroy(root);            /析构函数 38   

30、60; void preorder()                    /先序遍历 39             preorder(root);       

31、60; 40     void inorder()                          /中序遍历 41           inord

32、er(root);                   42     void postorder()                    

33、0;/后序遍历 43             postorder(root);     44 45     void preordertswap()                

34、   /交换左右子树 46           preorderswap(root);   47     int  theight()                  

35、        /求二叉树高度 48           return height(root);   49     int tleaves()             

36、            /求二叉树叶子结点个数 50             return leaves( root );     51     void levelorder() 

37、0;                     /按层遍历 52             levelorder(root);         53 &#

38、160;    void creat0();                        /建立树函数 54  private: 55     NodeType *root;   

39、;                 /数据成员，根结点 56     NodeType *creat();                    /建立二叉树递

40、归算法 57    void    preorder(NodeType *p);            /先序遍历递归算法 58     void    inorder(NodeType *p);      &

41、#160;     /中序遍历递归算法 59    void    postorder(NodeType *p);            /后序遍历递归算法 60    void    levelorder(NodeType *p

42、);            /按层遍历算法 61     void    preorderswap(NodeType *p);       /利用先序遍历方法交换左右子树 62     int    

43、height(NodeType *p);            /求二叉树高度递归算法 63    int    leaves(NodeType *p);            /求二叉树叶子结点个数的递归算法 64  

44、   void destroy(NodeType* &p);            /删除二叉树所有结点 65; 66 67/BiTree.cpp 68#include "BiTree.h" 69 70void  BiTree:creat0()     

45、0;                   /建立树函数， 71      72    cout << "请按照树的先序遍历顺序组织数据" << endl; 73    

46、; cout << "若结点信息是int，把每个结点的空孩子以输入;" << endl; 74     cout << "一个结点的二叉树，输入：0 0;" << endl; 75     root = creat();    &#

47、160;     /调用私有creat()(工具函数); 76      77NodeType * BiTree:creat()      /递归建立二叉树算法 78  79    NodeType *p;    80    ElemTyp

48、e x; 81    cout << "n 输入数据："  82    cin >> x; 83    if( x = 0 )        /若左或右孩子为空,置当前指针这空. 84  

49、;      p = NULL; 85    else  86            p = new NodeType;  87            p-&g

50、t;data = x; 88            p->lch = creat();                  /递归调用自身 89       

51、0;    p->rch = creat(); 90           91   return p; 92 93 94/先序遍历递归算法 95void BiTree:preorder(NodeType *p)        

52、0;     /先序遍历显示 96 97    if( p != NULL) 98     99        cout << p->data;100        preorder( p-&

53、gt;lch );        /递归调用自身101        preorder( p->rch );        /递归调用自身102    103    else104     &#

54、160;  cout <<"#"105106/中序遍历递归算法107void BiTree:inorder(NodeType *p)     /中序遍历显示108  109 110    if( p != NULL )111    112      

55、0; inorder( p->lch );        /递归调用自身113        cout << p->data;114        inorder( p->rch );      &#

56、160; /递归调用自身115    116    else117        cout << "#"    118119120/后序遍历递归算法121void BiTree:postorder(NodeType *p)122123    if( p !=

57、 NULL )124    125        126        postorder( p-> lch );        /递归调用自身127        postorder

58、( p-> rch );        /递归调用自身128        cout << p->data;129    130    else131        cout <<&q

59、uot;#"132133void BiTree:preorderswap(NodeType *p)         /利用先序遍历方法交换左右子树134      135    if( p != NULL )136          

60、60;137        NodeType *r; 138        r = p->lch;139        p->lch = p->rch; 140        p->rc

61、h = r;141/上面几条语句可以认为对结点的访问（交换左右孩子）142/替换了原来的：cout<<p->data<<" "  语句143        preorderswap( p->lch );        /递归调用自身144      &#

62、160; preorderswap( p->rch );145    146147void  BiTree:destroy(NodeType* &p)            /删除二叉树所有结点148149    if(p != NULL)150     

63、   destroy( p->lch );151        destroy( p->rch );152        delete p;153        p = NULL;154    155156i

64、nt BiTree:height(NodeType *p)                /求二叉树高度递归算法157       158    int hl,hr;159    if( p != NULL )160&#

65、160;   161        hl = height( p->lch );162        hr = height( p->rch );163        return ( hl >

66、0;hr ? hl : hr ) + 1;        /当前结点高度是以最大的(左右)子树的高度加得到164        165    166    else167        return 

67、0;168169170/求二叉树叶子结点个数的递归算法171int BiTree:leaves(NodeType *p)172173    if( p = NULL )            /当前结点是否为空,当为空时就没有左右孩子174        return 0;175 

68、;   if( ( p-> lch = NULL ) && ( p-> rch = NULL )    /当前结点是否有左右孩子176    177        return 1;178    179

69、    return leaves( p-> lch ) + leaves( p-> rch );    /递归调用自身累加叶子结点个数180181182/按层遍历算法183void BiTree:levelorder(NodeType *p)184185    SeQueue q;     &#

70、160;      /初始化一个队列186    NodeType *t = p;187    if (p)188    189        q.AddQ(*p);        /根结点非空则入队190 &

71、#160;  191    while (!q.IsEmpty()192    193        t = &(q.DelQ();    /队非空则将结点指针出队194        cout << t->data;

72、60;   /并打印输出结点的数据值195        if (t->lch)196        197            q.AddQ(*(t->lch);    /存在左孩子则将其进队198  &

73、#160;     199        else200            cout << "#"201202        if (t->rch)203   

74、0;    204            q.AddQ(*(t->rch);    /存在右孩子则将其进队205        206        else207      

75、;      cout << "#"208    209210211/-212int main()213 214  int k;    215  BiTree root0;             

76、        /声明创建二叉树对象，调用构造函数216  do cout<<"nn"217      cout<<"nn     1. 建立二叉树"218      cout<<"nn   &

77、#160; 2. 交换左右子树"219      cout<<"nn     3. 按层序遍历树"  220      cout<<"nn     4. 求二叉树深度 "221     

78、 cout<<"nn     5. 求叶子结点个数"  222      cout<<"nn     6. 结束程序运行"223      cout<<"n="224     

79、0;cout<<"n     请输入您的选择(0,1,2,3,4,5,6):" 225      cin>>k;226      switch(k)227           228       

80、   case 1:  229                    cout << "nt 输入（0）结束："230             &#

81、160;      root0.creat0();231                     cout << "nt 先序遍历结果:"232          &#

82、160;         root0.preorder();233                    cout << "nt 中序遍历结果:" 234       

83、             root0.inorder();235                    cout << "nt 后序遍历结果:" 236    

84、;                root0.postorder();                    237          &#

85、160;         break;238           case 2:  239                    cout <<&q

86、uot;nt 交换左右子树结果:"240                    root0.preordertswap();241                    cout&

87、#160;<< "nt 先序遍历结果:"242                    root0.preorder();             243     

88、60;              cout << "nt 中序遍历结果:"244                    root0.inorder();245   &#

89、160;                cout << "nt 后序遍历结果:" 246                    root0.postorder();&#

90、160;   247                    break;248           case 3:  249         

91、;           cout << "nt 按层序遍历结果:"250                    root0.levelorder();    251  

92、                  break;   252           case 4:  253            

93、       int deep;254                   deep = root0.theight();255               &

94、#160;   cout << "nt 树的深度是:" << deep;256                   break;257           case 

95、5:258                    int leaf;259                    leaf = root0.tleaves();260&#

96、160;                   cout << "nt 树的叶子结点个数是:" << leaf;261                

97、0;  break;262           case 6: exit(0);263           /  switch264cout<<"n -"265       while(k>=0

98、0;&& k<6); 266   return 0;267/-  268269/Queue.cpp270#include "BiTree.h"271SeQueue:SeQueue()        /初始化队列272  273    front=0;274    rear=0;275276277SeQueue:SeQueue();278/进队279void SeQueue:AddQ(NodeType x)    280   281    if(rear+1) % MAXSIZE=front)282         cout<<"QUEUE IS