二叉樹(shù)的建立及凹入表打印

1、-作者xxxx-日期xxxx二叉樹(shù)的建立及凹入表打印【精品文檔】先序遞歸建立二叉樹(shù)班級(jí)2012211313 姓名:胡卓 學(xué)號(hào):2012211468 姓名:郭志剛 學(xué)號(hào):2012211475 分工情況: 郭志剛BiTree CreateBiTree(BiTree& T)/先序遞歸創(chuàng)建二叉樹(shù) int main() 胡卓 void Print(BiTree& T,int t) int LEAF(BiTree& T)/計(jì)算葉子節(jié)點(diǎn)完成日期:2013-11-6問(wèn)題描述:1）用先序遞歸過(guò)程建立二叉樹(shù) (存儲(chǔ)結(jié)構(gòu)：二叉鏈表) 輸入數(shù)據(jù)按先序遍歷所得序列輸入，當(dāng)某結(jié)點(diǎn)左子樹(shù)或右子樹(shù)為空時(shí)，輸入*號(hào)，如輸入ab

2、c*d*e*得到的二叉樹(shù)為： e a d b c （選做：由二叉樹(shù)的先序序列和中序序列建立一棵二叉樹(shù)。）2）編寫遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。3）按凹入表方式輸出該二叉樹(shù)。 算法思想:定義二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)類型typedef struct BiTNode/ char data; struct BiTNode*lchild,*rchild;/左右子樹(shù)BiTNode,*BiTree;1.先序遞歸創(chuàng)建二叉樹(shù) BiTree CreateBiTree(BiTree& T) T=(BiTree)malloc(sizeof(BiTNode); T-data=0; char ch; scanf(%c,&

3、ch); if(ch!=*) T-data=ch; T-lchild=CreateBiTree(T-lchild); T-rchild=CreateBiTree(T-rchild); else if(ch=*) return NULL; if(T-lchild=NULL&T-rchild=NULL)|(T-lchild=NULL&T-rchild-data!=0)|(T-lchild-data!=0&T-rchild=NULL)|(T-lchild-data!=0&T-rchild-data!=0) return T; 2. 計(jì)算葉子節(jié)點(diǎn)int LEAF(BiTree& T) if(T-lch

4、ild=NULL&T-rchild=NULL) return 1; else if(T-lchild=NULL&T-rchild-data!=0) return LEAF(T-rchild); else if(T-lchild-data!=0&T-rchild=NULL) return LEAF(T-lchild); else return (LEAF(T-lchild)+LEAF(T-rchild);3.凹入表打印二叉樹(shù)void Print(BiTree& T,int t) int i; if(T) Print(T-rchild,t+5); for(i=0;idata); Print(T-l

5、child,t+5); int main() BiTree T; printf(*n); printf(*歡迎打印二叉樹(shù)*n); printf(*n); printf(請(qǐng)按先序遍歷所得數(shù)據(jù)輸入(當(dāng)某節(jié)點(diǎn)是葉子節(jié)點(diǎn)時(shí)用*表示)：n); T=CreateBiTree(T); printf(葉子節(jié)點(diǎn)的個(gè)數(shù)是: ); printf( %dn,LEAF(T); printf(打印該二叉樹(shù)結(jié)構(gòu)后的結(jié)果為:n); Print(T,5); system(pause); 設(shè)計(jì)描述: 源程序:#include#include#include#define Maxsize 100#define OVERFLOW -

6、1#define ERROR 0int pi=0;typedef struct BiTNode/定義二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)類型 char data; struct BiTNode*lchild,*rchild;/左右子樹(shù)BiTNode,*BiTree;BiTree CreateBiTree(BiTree& T)/先序遞歸創(chuàng)建二叉樹(shù) T=(BiTree)malloc(sizeof(BiTNode); T-data=0; char ch; scanf(%c,&ch); if(ch!=*) T-data=ch; T-lchild=CreateBiTree(T-lchild); T-rchild=Creat

7、eBiTree(T-rchild); else if(ch=*) return NULL; if(T-lchild=NULL&T-rchild=NULL)|(T-lchild=NULL&T-rchild-data!=0)|(T-lchild-data!=0&T-rchild=NULL)|(T-lchild-data!=0&T-rchild-data!=0) return T; int LEAF(BiTree& T)/計(jì)算葉子節(jié)點(diǎn) if(T-lchild=NULL&T-rchild=NULL) return 1; else if(T-lchild=NULL&T-rchild-data!=0) r

8、eturn LEAF(T-rchild); else if(T-lchild-data!=0&T-rchild=NULL) return LEAF(T-lchild); else return (LEAF(T-lchild)+LEAF(T-rchild);void Print(BiTree& T,int t) int i; if(T) Print(T-rchild,t+5); for(i=0;idata); Print(T-lchild,t+5); int main() BiTree T; printf(*n); printf(*歡迎打印二叉樹(shù)*n); printf(*n); printf(請(qǐng)按先序遍歷所得數(shù)據(jù)輸入(當(dāng)某節(jié)點(diǎn)是葉子節(jié)點(diǎn)時(shí)用*表示)：n); T=CreateBiTree(T); printf(葉子節(jié)點(diǎn)的個(gè)數(shù)是: ); printf( %dn,LEAF(T); printf(打印該二叉樹(shù)結(jié)構(gòu)后的結(jié)果為:n); Print(T,5); system(pause); 測(cè)試結(jié)果:用戶使用說(shuō)明:請(qǐng)按先序遍歷所得數(shù)據(jù)輸入（當(dāng)某節(jié)點(diǎn)是葉子時(shí)用*表示