數(shù)據(jù)結構二叉樹的生成和遍歷

1、6、二叉樹的生成建立一個二叉樹是指在內(nèi)存中建立二叉樹的存儲結構， 這里討論建立一個二 叉鏈表的方式生成一個二叉樹。 要建立一個二叉鏈表， 需按照完全二叉樹的層次 順序，依次輸入結點信息建立二叉鏈表。 對于一般的二叉樹， 必須添加一些虛結 點，使其成為完全二叉樹。我用 表示虛結點， #表示輸入結束標志。同時設置一 個隊列，隊列是一個指針類型的數(shù)組， 保存已輸入的結點的地址。 根據(jù)對為指針 奇偶數(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;二叉樹的遍歷上面雖然已經(jīng)生成二叉樹，但實際上用戶生成的二叉樹是抽象，用戶并不太 確信已經(jīng)生成的二叉樹是否是自己想要的， 于是，可以編制輸出程序進一步驗證 這個已經(jīng)存在的二叉樹的正確性。二叉樹的遍歷就是對二叉樹的每一個結點訪問一次且僅訪問一次。 我們通過 二叉樹的序遍歷的非遞歸算

4、法來驗證其正確性。 二叉樹非遞歸遍歷是用顯示棧來 存儲二叉樹的結點指針。1、先序遍歷 使用一個棧，首先將根結點入棧，開始循環(huá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、遍歷 先將根結點的所有左結點并入棧，出棧一個結點，將該結點的右結點入棧， 再將該結點的左結點入棧， 當一個結點的左右子樹均訪問該結點， 如此，直到棧 空為止。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);中序遍歷先將根結點的所有左結點并入棧 ,出棧一個結點 ,訪問該結點 ,將該結點的右 結點入棧 ,再將該結點的左結點入棧 , 當一個結點的左子樹均訪問后再訪問該結 點,最后訪問右結點 . 如此,直到?？諡橹?。Void psorder(btree*T)Btree*stackmaxsize,*p;int top=-1;dowhile(T)top+;stacktop=T;T=T->left;T=stacktop;printf( “ %c”,