Visual-C++-6.0調(diào)試功能-圖解教程(3)--實例

1、Visual C+ 6.0調(diào)試功能 圖解教程(3)-實例二樹和二叉樹 1. 實驗?zāi)康?1.熟悉二叉樹的二叉鏈表存儲結(jié)構(gòu)； 2.掌握構(gòu)造二叉樹的方法； 3.加深對二叉樹的遍歷的理解。 二.需求分析     本程序演示用C+編寫,完成按先序遍歷生成二叉樹,先序遍歷打印輸出二叉樹, 后序遍歷打印輸出二叉樹, 中序遍歷打印輸出二叉樹, 層序遍歷打印輸出二叉樹, 先序遍歷方法交換左右子樹,求樹的高度,求樹的葉子結(jié)點個數(shù). 輸入值的范圍:建立一棵二叉時,要求結(jié)點的的左右孩子為空時輸入0代替.所有輸入值必須為整形.輸入的結(jié)點個數(shù):若為單邊二叉樹(全只有左結(jié)點或全只有右

2、結(jié)點)則為任意個數(shù);若非單邊二叉則要求結(jié)點最多的層個數(shù)不得超過MAXSIZE的值. 輸出形式:輸出時如果結(jié)點的左右指針這空則以" #"代替輸出. 程序所能完成的功能:程序能完成按先序遍歷生成二叉樹,先序遍歷打印輸出二叉樹, 后序遍歷打印輸出二叉樹, 中序遍歷打印輸出二叉樹, 層序遍歷打印輸出二叉樹, 先序遍歷方法交換左右子樹,求樹的高度,求樹的葉子結(jié)點個數(shù).操作. 測試數(shù)據(jù) A建立二叉樹中輸入1230000 生成一棵樹123# B交換左右子樹得到一棵二叉樹1#2#3# C按層序遍歷樹得到一棵二叉樹1#2#3# D求二叉樹的高度得到高度3 E求葉子結(jié)點個數(shù)得到個數(shù)1 三.設(shè)計

3、概要 (1)為了實現(xiàn)上述程序的功能,需要定義二叉樹的抽象數(shù)據(jù)類型: ADT BiTree is 數(shù)據(jù)對象：D=ai|aiIntegerSet,i=0,1,2,n,n0 數(shù)據(jù)關(guān)系：R=<ai,ai+1>|ai,ai+1 D 基本操作: creat() 操作結(jié)果:建立一棵二叉樹 preorder() 初始條件:二叉樹已經(jīng)存在 操作結(jié)果:先序遍歷顯示二叉樹 preordertswap() 初始條件: 二叉樹已經(jīng)存在 操作結(jié)果:交換二叉樹的左右子樹 theight() 初始條件: 二叉樹已經(jīng)存在 操作結(jié)果:輸出二叉樹的高度 tleaves() 初始條件: 操作結(jié)果:輸出二叉樹的葉子結(jié)點個數(shù)

4、 levelorder() 初始條件: 二叉樹已經(jīng)存在 操作結(jié)果:層序遍歷顯示二叉樹 ADT BiTree (2) 本程序包含兩個類和一個結(jié)構(gòu)體類型 A基類:隊列類SeQueue有5個函數(shù)     1.構(gòu)造函數(shù)                            SeQueue

5、()     2.析構(gòu)函數(shù)                            SeQueue()     3.進隊函數(shù)          

6、;                  AddQ(NodeType x)     4.出隊函數(shù)                        

7、    DelQ()     5.判斷非空函數(shù)                            IsEmpty() B派生類:二叉樹類BiTree有20個函數(shù)     1主函數(shù) 

8、60;                              main() 2. 構(gòu)造函數(shù)                 &

9、#160;          BiTree()     3. 析構(gòu)函數(shù)                            BiTree()    

10、 4. 建立樹函數(shù)                            creat0()     5. 先序遍歷函數(shù)            

11、0;           void preorder()     6. 中序遍歷函數(shù)                        inorder()     7. 后序

12、遍歷函數(shù)                        postorder()     8.層序遍歷函數(shù)                  

13、          levelorder()     9. 交換左右子樹函數(shù)                    preordertswap()     10. 求二叉樹高度函數(shù)   &#

14、160;                theight()     11. 求二叉樹葉子結(jié)點個數(shù)函數(shù)                tleaves()     12. 建立二叉樹遞歸算法函數(shù) 

15、;               *creat()     13. 先序遍歷遞歸算法函數(shù)                preorder(NodeType *p)     14. 中序遍歷遞歸算法函數(shù) 

16、               inorder(NodeType *p)     15. 后序遍歷遞歸算法函數(shù)                postorder(NodeType *p)     16. 按層遍歷

17、算法函數(shù)                    levelorder(NodeType *p)     17. 先序遍歷方法交換左右子樹函數(shù)            preorderswap(NodeType *p)   

18、  18. 求二叉樹高度遞歸算法函數(shù)                height(NodeType *p)     19. 求二叉樹葉子結(jié)點個數(shù)的遞歸算法函數(shù)    leaves(NodeType *p)     20. 刪除二叉樹所有結(jié)點函數(shù)    

19、0;           destroy(NodeType* &p) C結(jié)構(gòu)體類型NodeType (3)本程序的三個文件 1.頭文件BiTree.h 2.源文件     Queue.cpp         BiTree.cpp (4)函數(shù)之間的關(guān)系   四.詳細設(shè)計    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、;  /定義結(jié)點結(jié)構(gòu)體 10        11    ElemType   data;                     12    NodeType 

23、 *lch,*rch; 13; 14 15/隊列 16class SeQueue                                /定義隊列類SeQueue 17   

24、;18private: 19       NodeType elemMAXSIZE;        /存儲隊列的數(shù)組個數(shù) 20        int front,rear;             &

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

26、 /入隊函數(shù) 25        NodeType DelQ();            /出隊函數(shù) 26        int IsEmpty()          &

27、#160;     /判斷隊列非空函數(shù) 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;                 /構(gòu)造函數(shù) 37     BiTree()    destroy(root);            /析構(gòu)函數(shù) 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、            /求二叉樹葉子結(jié)點個數(shù) 50             return leaves( root );     51     void levelorder() 

37、0;                     /按層遍歷 52             levelorder(root);         53 &#

38、160;    void creat0();                        /建立樹函數(shù) 54  private: 55     NodeType *root;   

39、;                 /數(shù)據(jù)成員，根結(jié)點 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);            /求二叉樹葉子結(jié)點個數(shù)的遞歸算法 64  

44、   void destroy(NodeType* &p);            /刪除二叉樹所有結(jié)點 65; 66 67/BiTree.cpp 68#include "BiTree.h" 69 70void  BiTree:creat0()     

45、0;                   /建立樹函數(shù)， 71      72    cout << "請按照樹的先序遍歷順序組織數(shù)據(jù)" << endl; 73    

46、; cout << "若結(jié)點信息是int，把每個結(jié)點的空孩子以輸入;" << endl; 74     cout << "一個結(jié)點的二叉樹，輸入：0 0;" << endl; 75     root = creat();    &#

47、160;     /調(diào)用私有creat()(工具函數(shù)); 76      77NodeType * BiTree:creat()      /遞歸建立二叉樹算法 78  79    NodeType *p;    80    ElemTyp

48、e x; 81    cout << "n 輸入數(shù)據(jù)："  82    cin >> x; 83    if( x = 0 )        /若左或右孩子為空,置當(dāng)前指針這空. 84  

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

50、t;data = x; 88            p->lch = creat();                  /遞歸調(diào)用自身 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 );        /遞歸調(diào)用自身101        preorder( p->rch );        /遞歸調(diào)用自身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 );        /遞歸調(diào)用自身113        cout << p->data;114        inorder( p->rch );      &#

56、160; /遞歸調(diào)用自身115    116    else117        cout << "#"    118119120/后序遍歷遞歸算法121void BiTree:postorder(NodeType *p)122123    if( p !=

57、 NULL )124    125        126        postorder( p-> lch );        /遞歸調(diào)用自身127        postorder

58、( p-> rch );        /遞歸調(diào)用自身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/上面幾條語句可以認為對結(jié)點的訪問（交換左右孩子）142/替換了原來的：cout<<p->data<<" "  語句143        preorderswap( p->lch );        /遞歸調(diào)用自身144      &#

62、160; preorderswap( p->rch );145    146147void  BiTree:destroy(NodeType* &p)            /刪除二叉樹所有結(jié)點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;        /當(dāng)前結(jié)點高度是以最大的(左右)子樹的高度加得到164        165    166    else167        return 

67、0;168169170/求二叉樹葉子結(jié)點個數(shù)的遞歸算法171int BiTree:leaves(NodeType *p)172173    if( p = NULL )            /當(dāng)前結(jié)點是否為空,當(dāng)為空時就沒有左右孩子174        return 0;175 

68、;   if( ( p-> lch = NULL ) && ( p-> rch = NULL )    /當(dāng)前結(jié)點是否有左右孩子176    177        return 1;178    179

69、    return leaves( p-> lch ) + leaves( p-> rch );    /遞歸調(diào)用自身累加葉子結(jié)點個數(shù)180181182/按層遍歷算法183void BiTree:levelorder(NodeType *p)184185    SeQueue q;     &#

70、160;      /初始化一個隊列186    NodeType *t = p;187    if (p)188    189        q.AddQ(*p);        /根結(jié)點非空則入隊190 &

71、#160;  191    while (!q.IsEmpty()192    193        t = &(q.DelQ();    /隊非空則將結(jié)點指針出隊194        cout << t->data;

72、60;   /并打印輸出結(jié)點的數(shù)據(jù)值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、        /聲明創(chuàng)建二叉樹對象，調(diào)用構(gòu)造函數(shù)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. 求葉子結(jié)點個數(shù)"  222      cout<<"nn     6. 結(jié)束程序運行"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）結(jié)束："230             &#

81、160;      root0.creat0();231                     cout << "nt 先序遍歷結(jié)果:"232          &#

82、160;         root0.preorder();233                    cout << "nt 中序遍歷結(jié)果:" 234       

83、             root0.inorder();235                    cout << "nt 后序遍歷結(jié)果:" 236    

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

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

86、uot;nt 交換左右子樹結(jié)果:"240                    root0.preordertswap();241                    cout&

87、#160;<< "nt 先序遍歷結(jié)果:"242                    root0.preorder();             243     

88、60;              cout << "nt 中序遍歷結(jié)果:"244                    root0.inorder();245   &#

89、160;                cout << "nt 后序遍歷結(jié)果:" 246                    root0.postorder();&#

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

91、;           cout << "nt 按層序遍歷結(jié)果:"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 樹的葉子結(jié)點個數(shù)是:" << 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;27527

99、6277SeQueue:SeQueue();278/進隊279void SeQueue:AddQ(NodeType x)    280   281    if(rear+1) % MAXSIZE=front)282         cout<<"QUEUE IS FULLn"283    else284