數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的生成和遍歷

1、6、二叉樹(shù)的生成建立一個(gè)二叉樹(shù)是指在內(nèi)存中建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)， 這里討論建立一個(gè)二 叉鏈表的方式生成一個(gè)二叉樹(shù)。 要建立一個(gè)二叉鏈表， 需按照完全二叉樹(shù)的層次 順序，依次輸入結(jié)點(diǎn)信息建立二叉鏈表。 對(duì)于一般的二叉樹(shù)， 必須添加一些虛結(jié) 點(diǎn)，使其成為完全二叉樹(shù)。我用 表示虛結(jié)點(diǎn)， #表示輸入結(jié)束標(biāo)志。同時(shí)設(shè)置一 個(gè)隊(duì)列，隊(duì)列是一個(gè)指針類型的數(shù)組， 保存已輸入的結(jié)點(diǎn)的地址。 根據(jù)對(duì)為指針 奇偶數(shù)的判斷， 來(lái)決定把字符放到左結(jié)點(diǎn)還是有結(jié)點(diǎn)中， 這樣就能生成想要的二 叉樹(shù)。#define maxsize 100#include “ stdio.h ”#include “ malloc.h ”#def

2、ine NULL 0typedef struct btnodechar data;struct btonde lchild,rchild;Btree;Btree*Qmaxsize;Btree*creatree()char ch;int front,rear;Btree *t,*s;t=NULL;front=1;rear=0;ch=getchar();while(ch!= '#')s=NULL;if(ch!= ' ')s=(btree*)mlloc(sizcof(btree);s->data=ch; s->lchild=NULL; s->rchi

3、ld=NULL; rear+;Qrear=s;if(rear=1)T=s;elseif(s&&Qfront)If(rear%2=0)Qfront->lchild=s;ElseQfront->rchild=s; if(rear%2=1)front+; ch=getchar(); returnT;二叉樹(shù)的遍歷上面雖然已經(jīng)生成二叉樹(shù)，但實(shí)際上用戶生成的二叉樹(shù)是抽象，用戶并不太 確信已經(jīng)生成的二叉樹(shù)是否是自己想要的， 于是，可以編制輸出程序進(jìn)一步驗(yàn)證 這個(gè)已經(jīng)存在的二叉樹(shù)的正確性。二叉樹(shù)的遍歷就是對(duì)二叉樹(shù)的每一個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。 我們通過(guò) 二叉樹(shù)的序遍歷的非遞歸算

4、法來(lái)驗(yàn)證其正確性。 二叉樹(shù)非遞歸遍歷是用顯示棧來(lái) 存儲(chǔ)二叉樹(shù)的結(jié)點(diǎn)指針。1、先序遍歷 使用一個(gè)棧，首先將根結(jié)點(diǎn)入棧，開(kāi)始循環(huán)；從棧中退出當(dāng)前結(jié)點(diǎn)，先訪 問(wèn)它，然后將其右結(jié)點(diǎn)入棧，再將其左結(jié)點(diǎn)入棧，如此直到?？諡橹?。Void porder(Btree*T) Btree*stackmaxsize,*p;int top=-1; if(T!=NULL)top+;stacktop=T; while(top>-1) p=stacktop;top-;prinft( “ %c”,p->data); if(p->right!=NULL)top+;stacktop=p->left;2、后序

5、遍歷 先將根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并入棧，出棧一個(gè)結(jié)點(diǎn)，將該結(jié)點(diǎn)的右結(jié)點(diǎn)入棧， 再將該結(jié)點(diǎn)的左結(jié)點(diǎn)入棧， 當(dāng)一個(gè)結(jié)點(diǎn)的左右子樹(shù)均訪問(wèn)該結(jié)點(diǎn)， 如此，直到棧 空為止。void pmorder(Btree*T)Btree*stackmaxsize,*p;int top=-1;dowhile(T)top+;stacktop=T;T=T->left;p=NULL;flag=1;while(top!=-1 &&flag)T=stacktop;ift->right=pprintf( “ %c”,T->data);top+;p=T;elseT=T->right;flag=0;while(top!=-1);中序遍歷先將根結(jié)點(diǎn)的所有左結(jié)點(diǎn)并入棧 ,出棧一個(gè)結(jié)點(diǎn) ,訪問(wèn)該結(jié)點(diǎn) ,將該結(jié)點(diǎn)的右 結(jié)點(diǎn)入棧 ,再將該結(jié)點(diǎn)的左結(jié)點(diǎn)入棧 , 當(dāng)一個(gè)結(jié)點(diǎn)的左子樹(shù)均訪問(wèn)后再訪問(wèn)該結(jié) 點(diǎn),最后訪問(wèn)右結(jié)點(diǎn) . 如此,直到棧空為止。Void psorder(btree*T)Btree*stackmaxsize,*p;int top=-1;dowhile(T)top+;stacktop=T;T=T->left;T=stacktop;printf( “ %c”,