∪∩deniable Design

          個人JAVA版GAE(google app engine),struts2+jpa+jQuery開發,互相交流 http://iunbug.appspot.com/
            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

          樹和二叉樹

          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,n≥0}
          數據關系:R={<ai,ai+1>|ai,ai+1 D}

          基本操作:

          creat()

          操作結果:建立一棵二叉樹

          preorder()

          初始條件:二叉樹已經存在

          操作結果:先序遍歷顯示二叉樹

          preordertswap()

          初始條件: 二叉樹已經存在

          操作結果:交換二叉樹的左右子樹

          theight()

          初始條件: 二叉樹已經存在

          操作結果:輸出二叉樹的高度

          tleaves()

          初始條件:

          操作結果:輸出二叉樹的葉子結點個數

          levelorder()

          初始條件: 二叉樹已經存在

          操作結果:層序遍歷顯示二叉樹

          }ADT BiTree

          (2) 本程序包含兩個類和一個結構體類型

          A基類:隊列類SeQueue5個函數

              1.構造函數                            SeQueue()

              2.析構函數                            ~SeQueue()

              3.進隊函數                            AddQ(NodeType x)

              4.出隊函數                            DelQ()

              5.判斷非空函數                            IsEmpty()

          B派生類:二叉樹類BiTree20個函數

              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 *= 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 *= 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)窗口中得到更好的觀察效果.

          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進行觀察.斷續F10Debugger停留在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退出調試,完成調試演示.

          評論

          # re: Visual C++ 6.0調試功能 圖解教程(3)--實例二  回復  更多評論   

          2008-12-14 23:33 by 小初初
          #include<iostream.h>
          #include<stdio.h>
          #include<malloc.h>
          #define MaxSize 100
          typedef char ElemType;
          typedef struct tnode//定義二叉樹類型
          {
          ElemType data;
          struct tnode *lchild,*rchild;
          } BTNode;
          void CreateBTree(BTNode * &bt,char *str)//創建二叉樹
          {
          BTNode *St[MaxSize],*p=NULL;
          int top=-1,k,j=0;
          char ch;
          bt=NULL;
          ch=str[j];
          while (ch!='\0')
          {
          switch(ch)
          {
          case '(':top++;St[top]=p;k=1;break;
          case ')':top--;break;
          case ',':k=2;break;
          default:p=(BTNode *)malloc(sizeof(BTNode));
          p->data=ch;p->lchild=p->rchild=NULL;
          if (bt==NULL)
          bt=p;
          else
          {
          switch(k)
          {
          case 1:St[top]->lchild=p;break;
          case 2:St[top]->rchild=p;break;
          }
          }
          }
          j++;
          ch=str[j];
          }
          }
          void DispBTree(BTNode *bt)//輸出二叉樹
          {
          if(bt!=NULL)
          {
          cout << bt->data;
          if(bt->lchild!=NULL || bt->rchild!=NULL)
          {
          cout << "(";
          DispBTree(bt->lchild);
          if(bt->rchild!=NULL) cout << ",";
          DispBTree(bt->rchild);
          cout << ")";
          }
          }
          }
          int BTHeight(BTNode *bt)//求二叉樹的高度
          {
          int lchilddep,rchilddep;
          if (bt==NULL) return(0);
          else
          {
          lchilddep=BTHeight(bt->lchild);
          rchilddep=BTHeight(bt->rchild);
          return (lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);

          }
          }
          int NodeCount(BTNode *bt)//求二叉樹的結點數
          {
          int num1,num2;
          if(bt==NULL)
          return 0;
          else
          {
          num1=NodeCount(bt->lchild);
          num2=NodeCount(bt->rchild);
          return (num1+num2+1);
          }

          }
          int LeafCount(BTNode *bt)//求二叉樹的葉子結點數
          {
          int num1,num2;
          if(bt==NULL)
          return 0;
          else if (bt->lchild==NULL && bt->rchild==NULL)
          return (1);
          else
          {
          num1=LeafCount(bt->lchild);
          num2=LeafCount(bt->rchild);
          return (num1+num2);
          }
          }
          void PreOrder(BTNode *bt)//先序遍歷
          {
          if (bt!=NULL)
          { cout << bt->data;
          PreOrder(bt->lchild);
          PreOrder(bt->rchild);
          }
          }
          void InOrder(BTNode *bt)//中序遍歷
          {
          if (bt!=NULL)
          {
          InOrder(bt->lchild);
          cout << bt ->data;
          InOrder(bt->rchild);
          }

          }
          void PostOrder(BTNode *bt)//后序遍歷
          { if (bt!=NULL)
          { PostOrder(bt->lchild);
          PostOrder(bt->rchild);
          cout << bt->data;
          }
          }
          void main()//主函數
          {
          BTNode *b;
          char *str;
          cout <<"輸出括號表示法的二叉樹為:"<< endl;
          str="A(B(C(E,F)),D(G))";
          CreateBTree(b,str);
          DispBTree(b);cout << endl;
          cout << "二叉樹的高為:" << BTHeight(b) << endl;
          cout << "二叉樹的結點數為:" << NodeCount(b) << endl;
          cout << "二叉樹的葉子結點數為:" << LeafCount(b) << endl;
          cout << "二叉樹的先序遍歷序列:" << PreOrder(b) << endl;
          cout << "二叉樹的中序遍歷序列:"<< InOrder(b) << endl;
          cout << "二叉樹的后序遍歷序列:"<< PostOrder(b) << endl;
          }
          有3個錯誤怎么改啊?

          # re: Visual C++ 6.0調試功能 圖解教程(3)--實例二  回復  更多評論   

          2008-12-15 11:53 by ∪∩BUG
          @小初初
          慢慢調試吧,以前我也是問老師,后來問老師效果不怎么好,我學習了調試就再不用問老師了,在調試中你可以學到很多東西..
          主站蜘蛛池模板: 宁南县| 瓦房店市| 乐昌市| 平利县| 东乡族自治县| 英吉沙县| 铜鼓县| 谢通门县| 阿城市| 淅川县| 石家庄市| 华安县| 渑池县| 麻栗坡县| 临潭县| 星座| 和平区| 富平县| 临武县| 江山市| 嘉义县| 垫江县| 孙吴县| 油尖旺区| 吴忠市| 峨山| 泰宁县| 喀喇沁旗| 易门县| 调兵山市| 桑植县| 吉林市| 崇左市| 朔州市| 丹阳市| 桐柏县| 沐川县| 三穗县| 米脂县| 隆昌县| 蓝山县|