5.樹和二叉樹實(shí)習(xí)報(bào)告

1、實(shí)習(xí)題目：編寫算法判別給定二叉樹是否為完全二叉樹。一、 需求分析1、根據(jù)題目要求，以嵌套括號法輸入二叉樹，用戶需要輸入嵌套形式的字符串，在程序中會自動(dòng)建立一個(gè)二叉樹，并對樹進(jìn)行分析，運(yùn)行結(jié)果會先打印出以嵌套括號表示的二叉樹，而后是判斷的結(jié)果。如果輸入的二叉樹錯(cuò)誤，程序指揮對前面符合二叉樹定義的數(shù)據(jù)進(jìn)行分析，如打入 a(b,c),d(e,f)程序會建立樹a(b,c)并支隊(duì)這樹進(jìn)行分析。2、二、概要設(shè)計(jì)該程序有以下幾個(gè)子程序：Creatree();/該程序要求輸入并根據(jù)嵌套括號表示法的字符串str生成/樹，并返回樹的頭節(jié)點(diǎn)指針；/打印出建立的二叉樹；的二叉Pr(*b);Ctree(*b);/對給定

2、的二叉樹進(jìn)行判斷是否為二叉樹，是，則返回1，否則返回0；三、概要算法#include #define MAX 30#define NULL 0 typedef struct node char data;struct node *left; struct node *right;Btree;/定義二叉樹類型；Btree *Ctr_tree()/根據(jù)輸入的嵌套括號表示法的字符串*str 生成Btree *stackMAX,*p,*b; char str100;的二叉樹top=-1,k,j=0;/top 為棧指針，k 指定是左還是右孩子，j 為str 的指針p=b=NULL;prf(nInput

3、the tree(expressed by embeded brackets):);/輸入嵌套括號法表示的字符串str; gets(str);ch=strj; while(ch!=0)switch(ch)case (:top+;stacktop=p;k=1;break;/左節(jié)點(diǎn)； case ):top-;break;case ,:k=2;break;/右街點(diǎn)； default:p=(Btree *)malloc(sizeof(Btree);p-dh;p-left=p-right=NULL;if(b=NULL)b=p;/根節(jié)點(diǎn)； elseswitch(k)case 1:stacktop-left

4、=p;break; case 2:stacktop-right=p;break;/switch;/if/switch; j+;ch=strj;/while; return b;void Pr(Btree *b)/用嵌套括號表示法輸出一顆二叉樹；if(b!=NULL)prf(%c,b-data);if(b-left|b-right)prf();Pr(b-left);/遞歸處理樹；if(b-right)prf(,);Pr(b-right);/遞歸處理右子樹；prf();Ctree(Btree *b)/判斷給定的數(shù)是否為完全二叉樹，是則返回Btree *queueMAX,*p;/定義一個(gè)隊(duì)列，用于分

5、成判斷；=0,rear=0,bj=1,cm=1;/cm 表示整個(gè)二叉需是否為完全二叉樹，bj 表示到目前為止所有結(jié)點(diǎn)均由左右孩/子if(b!=NULL)rear+; queuerear=b;while(!=rear&cm)/隊(duì)列不空；+;p=queue if(!p-left)bj=0;if(p-right) cm=0; /if elsecm=bj; rear+;queuerear=p-left; if(!p-right) bj=0; elserear+;queuerear=p-right;/while return cm;return 1;/空樹；四、執(zhí)行程序 #include #define

6、 MAX 30#define NULL 0 typedef struct node char data;struct node *left; struct node *right;Btree;Btree *Ctr_tree()Btree *stackMAX,*p,*b; char str100;top=-1,k,j=0; char ch; p=b=NULL;prf(nInput the tree(expressed by embeded brackets):);gets(str); ch=strj; while(ch!=0)switch(ch)case (:top+;stacktop=p;k=

7、1;break; case ):top-;break;case ,:k=2;break;default:p=(Btree *)malloc(sizeof(Btree);p-dh;p-left=p-right=NULL;if(b=NULL)b=p; elseswitch(k)case1:stacktop-left=p;break; case2:stacktop-right=p;break; j+;ch=strj;return b;void Pr(Btree *b)if(b!=NULL)prf(%c,b-data);if(b-left|b-right)prf();Pr(b-left);if(b-r

8、ight)prf(,);Pr(b-right);prf();Ctree(Btree *b)Btree *queueMAX,*p;=0,rear=0,bj=1,cm=1; if(b!=NULL)rear+; queuerear=b;while(!=rear&cm)+;p=queue if(!p-left)bj=0;if(p-right) cm=0; elsecm=bj;rear+; queuerear=p-left; if(!p-right) bj=0; elserear+;queuerear=p-right;return cm; return 1;void main()Btree *root;

9、 root=Ctr_tree();pr Prf(nThe tree:); (root);if(Ctree(root)=1)prf( is);else prf( is not);prf( a complete binary tree.n);五、調(diào)試分析這個(gè)算法編得比較成功，編譯和調(diào)試時(shí)出錯(cuò)很少且易改，但當(dāng)運(yùn)行時(shí)，卻發(fā)現(xiàn)無論輸入什么二叉樹，都不是完全二叉樹，用 pritnf 語句輸出cm,bj 值和判斷過程中碰到的數(shù)的結(jié)點(diǎn)，發(fā)現(xiàn)無錯(cuò)，只是 cm 值多了兩個(gè)且均為 0。重新對照編的算法進(jìn)行分析，沒錯(cuò)，幾經(jīng)調(diào)試仍無結(jié)果，請同學(xué)幫忙修改無結(jié)果，次日上機(jī)時(shí)，仔細(xì)檢查機(jī)上程序才發(fā)覺打錯(cuò)了一個(gè)字母，誤將 p 打?yàn)?b，以至結(jié)果出錯(cuò)。該會后，運(yùn)行成功。得出結(jié)論：機(jī)上的程序不能運(yùn)行或運(yùn)行出錯(cuò)而你編的紙上的算法沒錯(cuò)時(shí)，很可能就是你在打字時(shí)出錯(cuò)了。六、運(yùn)行結(jié)果Input the tree (expressed by embeded brackets):a(b(f),c(d,e) The tree:a(b(