二叉樹的建立及凹入表打印

1、先序遞歸建立二叉樹班級2012211313 姓名:胡卓 學(xué)號:2012211468 姓名:郭志剛 學(xué)號:2012211475 分工情況: 郭志剛BiTree CreateBiTree(BiTree& T)/先序遞歸創(chuàng)建二叉樹 int main() 胡卓 void Print(BiTree& T,int t) int LEAF(BiTree& T)/計算葉子節(jié)點完成日期:2013-11-6問題描述:1）用先序遞歸過程建立二叉樹 (存儲結(jié)構(gòu)：二叉鏈表) 輸入數(shù)據(jù)按先序遍歷所得序列輸入，當(dāng)某結(jié)點左子樹或右子樹為空時，輸入*號，如輸入abc*d*e*得到的二叉樹為： e a d

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

3、c",&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-&

4、gt;data!='0'&&T->rchild=NULL)|(T->lchild->data!='0'&&T->rchild->data!='0') return T; 2. 計算葉子節(jié)點int LEAF(BiTree& T) if(T->lchild=NULL&&T->rchild=NULL) return 1; else if(T->lchild=NULL&&T->rchild->data!='0'

5、;) 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.凹入表打印二叉樹void Print(BiTree& T,int t) int i; if(T) Print(T->rchild,t+5); for(i=0;i<t;i+) printf(" ");

6、 printf("%5cn",T->data); Print(T->lchild,t+5); 4.主函數(shù)int main() BiTree T; printf("*n"); printf("*歡迎打印二叉樹*n"); printf("*n"); printf("請按先序遍歷所得數(shù)據(jù)輸入(當(dāng)某節(jié)點是葉子節(jié)點時用'*'表示)：n"); T=CreateBiTree(T); printf("葉子節(jié)點的個數(shù)是: "); printf(" %dn&

7、quot;,LEAF(T); printf("打印該二叉樹結(jié)構(gòu)后的結(jié)果為:n"); Print(T,5); system("pause"); 設(shè)計描述: 源程序:#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define Maxsize 100#define OVERFLOW -1#define ERROR 0int pi=0;typedef struct BiTNode/定義二叉樹的數(shù)據(jù)結(jié)構(gòu)類型 char data; struct BiTNode*lchi

8、ld,*rchild;/左右子樹BiTNode,*BiTree;BiTree CreateBiTree(BiTree& T)/先序遞歸創(chuàng)建二叉樹 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=CreateBiTree(T->rchild); else if(c

9、h='*') 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

10、LEAF(BiTree& T)/計算葉子節(jié)點 if(T->lchild=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(

11、T->lchild)+LEAF(T->rchild);void Print(BiTree& T,int t) int i; if(T) Print(T->rchild,t+5); for(i=0;i<t;i+) printf(" "); printf("%5cn",T->data); Print(T->lchild,t+5); int main() BiTree T; printf("*n"); printf("*歡迎打印二叉樹*n"); printf("*n"); printf("請按先序遍歷所得數(shù)據(jù)輸入(當(dāng)某節(jié)點是葉子節(jié)點時用'*'表示)：n"); T=CreateBiTree(T); printf("葉子節(jié)點的個數(shù)是: "); printf(" %dn",LEAF(T); printf("打印該二叉樹結(jié)構(gòu)后的結(jié)果為:n"); Print(T,5); system(&q