二叉樹遍歷第六次實驗

1、實驗十：高校本科招生最低錄取分?jǐn)?shù)線查詢系統(tǒng)【問題描述】 二叉樹采用二叉鏈表作存儲結(jié)構(gòu)，編程實現(xiàn)二叉樹的如下基本操作：按先序序列構(gòu)造一棵二叉鏈表表示的二叉樹 T；對這棵二叉樹進(jìn)行遍歷：先序、中序、后序以及層次遍歷序列，分別輸出結(jié)點的遍歷序 列；求二叉樹的深度/結(jié)點數(shù)目/葉結(jié)點數(shù)目；【數(shù)據(jù)描述】/ 二叉樹的二叉鏈表存儲表示 typedef struct BiTNodeTElemType data;Struct BiTNode * lchild, * rchild; /左右孩子指針BiTNode, * BiTree;【算法描述】建立一棵二叉樹 BiTree CreateBiTree(BiTree &

2、T) / 算法6.4/ 按先序次序輸入二叉樹中結(jié)點的值(一個字符)，空格字符表示空樹， /構(gòu)造二叉鏈表表示的二叉樹T。char ch;scanf(%c,&ch);if (ch=#) T = NULL;else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) return ERROR; T-data = ch;/ 生成根結(jié)點CreateBiTree(T-lchild);/ 構(gòu)造左子樹CreateBiTree(T-rchild);/ 構(gòu)造右子樹return T; / CreateBiTree先序遍歷二叉樹遞歸算法void Preorder (BiTree T

3、, void( *visit)(TElemType& e) / 先序遍歷二叉樹if (T) visit(T-data); / 訪問結(jié)點 Preorder(T-lchild, visit); / 遍歷左子樹 Preorder(T-rchild, visit);/ 遍歷右子樹中序遍歷的遞歸算法void Inorder (BiTree T, void( *visit)(TElemType& e) / 中序遍歷二叉樹if (T) Inorder(T-lchild, visit); / 遍歷左子樹 visit(T-data); / 訪問結(jié)點 Inorder(T-rchild, visit);/ 遍歷右子

4、樹后序遍歷遞歸算法void Postorder (BiTree T, void( *visit)(TElemType& e) / 后序遍歷二叉樹if (T) Postorder(T-lchild, visit); / 遍歷左子樹 Postorder(T-rchild, visit);/ 遍歷右子樹 visit(T-data); / 訪問結(jié)點中序遍歷非遞歸算法之一Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法6.2/采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)。 /中序遍歷二叉樹T的非遞歸算法，對每個數(shù)

5、據(jù)元素調(diào)用函數(shù)Visit。 stack S;BiTree p;InitStack(S); Push(S, T); / 根指針進(jìn)棧while (!StackEmpty(S) while (GetTop(S, p) & p) Push(S, p-lchild); / 向左走到盡頭 Pop(S, p);/ 空指針退棧if (!StackEmpty(S) / 訪問結(jié)點，向右一步Pop(S, p);if (!Visit(p-data) return ERROR;Push(S, p-rchild);return OK; / InOrderTraverse中序遍歷非遞歸算法之二Status InOrderT

6、raverse(BiTree T, Status (*Visit)(ElemType) / 算法 6.3/采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)。/中序遍歷二叉樹T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit。stack S;BiTree p;InitStack(S); p = T;while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lchild; /非空指針進(jìn)棧，繼續(xù)左 進(jìn)else / 上層指針退棧，訪問其所指結(jié)點，再向右進(jìn)Pop(S, p);if (!Visit(p-data) return ERROR;p = p-r

7、child;return OK; / InOrderTraverse7 層次遍歷二叉樹的非遞歸算法Status LevelOrder(BiTree T)按層次遍歷二叉樹T, Q為隊列InitQueue(Q);If (T!=NULL)/ 若樹非空EnQueue(Q,T);根結(jié)點入隊列While (!QueueEmpty(Q)DeQueue(Q,b); /隊首元素出隊列Visit(b-data); /訪問結(jié)點If (b-lchild!=NULL) EnQueue(Q,b-lchild);左子樹非空，則入隊列If (b-rchold!=Null) EnQueue(Q,b-rchild); 右子樹非空

8、，則入隊列/while/ifLevelOrder8 求二叉樹的深度int depth(BiTree T)若T為空樹，則深度為0否則其深度等于左子樹或右子樹的最大深度加1if (T=NULL) return 0;else dep1=depth(T-lchild);dep2=depth(T-rchild);return dep1dep2?dep1+1:dep2+1;【C 源程序】#include #include #define MAX 20#define NULL 0typedef char TElemType;typedef int Status;typedef struct BiTNodeT

9、ElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;Status CreateBiTree(BiTree *T)char ch; ch=getchar();if (ch=#) (*T)=NULL;/* #代表空指針*/else (*T)=(BiTree) malloc(sizeof(BiTNode);/* 申請結(jié)點 */(*T)-data=ch;/*生成根結(jié)點 */CreateBiTree(&(*T)-lchild) ;/*構(gòu)造左子樹 */CreateBiTree(&(*T)-rchild) ;/*構(gòu)造右子樹 */retur

10、n 1;void PreOrder(BiTree T)if (T) printf(%2c,T-data); /*訪問根結(jié)點，此處簡化為輸出根結(jié)點的數(shù)據(jù)值*/PreOrder(T-lchild); /*先序遍歷左子樹*/PreOrder(T-rchild); /*先序遍歷右子樹*/void LevleOrder(BiTree T)/*層次遍歷二叉樹T,從第一層開始，每層從左到右*/BiTree QueueMAX,b;/*用一維數(shù)組表示隊列，front和rear分別表示隊首和隊尾指針 */BiTree QueueMAX,b;int front,rear;front=rear=0;/*根結(jié)點入隊列*

11、/*當(dāng)隊列非空/*根結(jié)點入隊列*/*當(dāng)隊列非空*/*隊首元素出隊列，并訪問這個結(jié)點*/Queuerear+=T; while (front!=rear) b=Queuefront+;printf(%2c,b-data);if (b-lchild!=NULL) Queuerear+=b-lchild; /*左子樹非空，則入隊列*/ if (b-rchild!=NULL) Queuerear+=b-rchild; /*右子樹非空，則入隊列*/LevelOrderint depth(BiTree T) /*求二叉樹的深度*/int dep1,dep2; if (T=NULL) return 0;el

12、se dep1=depth(T-lchild); dep2=depth(T-rchild); return dep1dep2?dep1+1:dep2+1;/depthmain()BiTree T=NULL;printf(nCreate a Binary Treen); CreateBiTree(&T); /*建立一棵二叉樹 T*/ printf(nThe preorder is:n);PreOrder(T);/*先序遍歷二叉樹*/printf(nThe level order is:n);LevleOrder(T); /*層次遍歷二叉樹*/ printf(nThe depth is:%dn,depth(T); 【測試數(shù)據(jù)】輸入：#/，建立一棵空樹，先序遍歷和層次遍歷沒有輸出，樹的深度輸出為 0輸入：A/先序和層次遍歷輸出均為 A；深度輸出為： 1輸入：ABC#DE#G#F#/,先序輸出為： AB C D E G F層次遍歷輸出為： A B C D E F G深度輸出為： 5二叉樹中葉子結(jié)點的個數(shù): 3二叉樹中以值為 B 的結(jié)點為根的子樹深度: 4 【說明】1. 按先序次序輸入二叉樹中結(jié)點的值，用#表示空樹，對