數據結構課程設計說明書樹的應用樹和二叉樹的轉換

1、中北大學數據結構與算法課程設計說 明 書學院、系：軟件學院專業(yè)：軟件工程班級：1314010xxx學生姓名：學 號： 1314010xxx設計題目：樹的應用起迄日期 :2015 年 1 月 12 日- 2015年1月29日指導教師 :尹四清.2015 年1月29 日一、需求分析1. 設計內容及設計要求A. 設計內容：（ 1）建立一棵樹；（ 2）將樹轉換成二叉樹；（ 3）實現(xiàn)二叉樹的前序、中序、后序的遞歸和非遞歸遍歷算法。B. 設計要求：(1) 符合課題要求，實現(xiàn)相應功能；(2) 要求界面友好美觀，操作方便易行；(3) 注意程序的實用性、安全性；2. 本演示程序中，元素為單個字符，以空格表示空樹

2、 ( 即結點為空 ) ，以回車符作為輸入結束標志，樹采用孩子兄弟表示法，二叉樹采用二叉鏈表表示法。在真實的運行過程中，由用戶手動輸入待創(chuàng)建樹的含有空格的先根次序序列， 并按回車結束， 程序會將其轉化為其對應的二叉樹，然后對二叉樹進行先序、中序、后序的遞歸及非遞歸遍歷以及層序遍歷，然后顯示轉化后二叉樹的高度和總結點數，以驗證所創(chuàng)建的二叉樹是否正確，最后，銷毀創(chuàng)建的樹和二叉樹，程序結束。3. 演示程序以用戶和計算機對話方式執(zhí)行，即在計算機終端（屏幕）上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序規(guī)定的運算命令，相應的輸入數據和運算結果顯示在其后。4. 為了美觀，程序的輸出結果采用了分塊顯示的模

3、式，由虛線及標題隔開，便于用戶檢查和驗證。5. 測試數據如圖，給出一棵樹，若屏幕上顯示如下信息：->請按樹的先根次序輸入序列，如有空子樹，用空格填充，完成后輸入回車確認此時，你應當輸入：（表示回車確認）ABEF CDGHIJK提示：為方便確認輸入了幾個空格，用星號* 表示輸入序列中的空格，則序列如下ABE*F*C*DGHI*J*K*（不是真實的輸入序列，供計算需輸入空格個數時用）這時，建好的樹的先根和后根次序序列如下：.樹的先根序列ABEFCDGHIJK樹的后根序列EFBCIJKHGDA由樹和二叉樹的轉換關系知，二叉樹的先序和中序遍歷所得序列分別與樹的先根和后根遍歷所得序列相同，據此驗證

4、轉化是否正確。二叉樹的先序和中序遍歷序列如下：二叉樹先序序列ABEFCDGHIJK二叉樹中序序列EFBCIJKHGDA二、概要設計為了實現(xiàn)上述程序功能，樹采用孩子兄弟表示法，二叉樹采用二叉鏈表表示法。為此，需要兩個抽象數據類型，樹和二叉樹的抽象數據類型。1. 樹的抽象數據類型定義ADT Tree數據對象D： D 是具有相同特性的數據元素的集合。數據關系R：若 D為空集，則稱為空樹；若 D僅含有一個數據元素，則R為空集，否則R=H ， H是如下二元關系：(1)在 D 中存在唯一的稱為根的數據元素root ，它在關系 H 下無前驅；(2)若 D-root ，則存在 D-root 的一個劃分 D1,

5、D2,D3, ,Dm(m>0)，對于任意 j k(1 j,k m)有 Dj Dk= , 且對任意的 i(1 i m)，唯一存在數據元素xi Di 有 <root,xi> H;(3)對應于 D-root的劃分， H-<root,xi>, ,<root,xm> 有唯一的一個劃分H1， H2, , ,Hm(m>0)，對任意 j k(1 j,k m)有 Hj Hk=，且對任意 i(1 i m),Hi 是 Di 上的二元關系， (Di,Hi)是一棵符合本定義的樹，稱為根 root 的子樹?；静僮鱌：InitTree(&T);操作結果：構造空樹T。

6、DestroyTree(&T);初始條件：樹T 存在。操作結果：銷毀樹T。CreateTree(&T,definition);初始條件： definition給出樹 T 的定義。.操作結果：按definition構造樹 T。ClearTree(&T);初始條件：樹T 存在。操作結果：將樹T 清為空樹。TreeEmpty(T);初始條件：樹T 存在。操作結果：若T 為空樹，則返回TRUE，否則返回FALSE。TreeDepth(T);初始條件：樹T 存在。操作結果：返回的深度。Root(T);初始條件：樹T 存在。操作結果：返回T 的根。Value(T,cur_e);初始

7、條件：樹T 存在， cur_e 是 T 中某個結點。操作結果：返回cur_e 的值。Assign(T,cur_e,value);初始條件：樹T 存在， cur_e 是 T 中某個結點。操作結果：結點cur_e 賦值為 value 。Parent(T,cur_e);初始條件：樹T 存在， cur_e 是 T 中某個結點。操作結果：若cur_e 是 T 的非根結點，則返回它的雙親，否則函數值為“空”。LeftChild(T,cur_e);初始條件：樹T 存在， cur_e 是 T 中某個結點。操作結果：若cur_e 是 T 的非葉子結點，則返回它的最左孩子，否則返回“空”。RightSibling

8、(T,cur_e);初始條件：樹T 存在， cur_e 是 T 中某個結點。操作結果：若cur_e 有右兄弟，則返回它的右兄弟，否則返回“空”。InsertChild(&T,&p,I,c);初始條件：樹存在，指向中某個結點，1 i p 指結點的度，非空樹與.不相交。操作結果：插入c 為中指結點的第棵子樹。DeleteChild(&T,&p,i);初始條件：樹T 存在， p 指向 T 中某個結點， 1 i p 指結點的度。操作結果：刪除中所指結點的第棵子樹。TraverseTree(T,visit();初始條件：樹T 存在， visit是對結點操作的應用函數。操作

9、結果：按某種次序對T 的每個結點調用函數visit() 一次且至多一次。 一旦 visit()失敗，則操作失敗。ADTTree2. 二叉樹的抽象數據類型定義ADT BinaryTree數據對象D： D 是具有相同特性的數據元素的集合。數據關系R：若 D=，則 R=，稱 BinaryTree 為空二叉樹；若 D，則 R=H ， H 是如下二元關系；（ 1）在 D 中存在惟一的稱為根的數據元素root ，它在關系H下無前驅；（ 2）若 D-root，則存在D-root=D1,Dr，且 D1Dr = ；（ 3）若 D1，則 D1 中存在惟一的元素x1，<root,x1> H，且存在 D1

10、 上的關系H1 ?H；若Dr，則Dr 中存在惟一的元素xr ， <root,xr> H，且存在上的關系Hr ? H；H=<root,x1>,<root,xr>,H1,Hr；（ 4） (D1,H1)是一棵符合本定義的二叉樹，稱為根的左子樹；(Dr,Hr)是一棵符合本定義的二叉樹，稱為根的右子樹?；静僮鳎篒nitBiTree( &T )操作結果：構造空二叉樹T。DestroyBiTree( &T )初始條件：二叉樹T 已存在。操作結果：銷毀二叉樹T。CreateBiTree( &T, definition ).初始條件： definit

11、ion給出二叉樹T 的定義。操作結果：按definiton構造二叉樹T。ClearBiTree( &T )初始條件：二叉樹T 存在。操作結果：將二叉樹T 清為空樹。BiTreeEmpty( T )初始條件：二叉樹T 存在。操作結果：若T 為空二叉樹，則返回TRUE，否則返回FALSE。BiTreeDepth( T )初始條件：二叉樹T 存在。操作結果：返回T 的深度。Root( T )初始條件：二叉樹T 存在。操作結果：返回T 的根。Value( T, e )初始條件：二叉樹T 存在， e 是 T 中某個結點。操作結果：返回e 的值。Assign( T, &e, value )

12、初始條件：二叉樹T 存在， e 是 T 中某個結點。操作結果：結點e 賦值為 value 。Parent( T, e )初始條件：二叉樹T 存在， e 是 T 中某個結點。操作結果：若e 是 T 的非根結點，則返回它的雙親，否則返回“空”。LeftChild( T, e )初始條件：二叉樹T 存在， e 是 T 中某個結點。操作結果：返回e 的左孩子。若e 無左孩子，則返回“空”。RightChild( T, e )初始條件：二叉樹T 存在， e 是 T 中某個結點。操作結果：返回e 的右孩子。若e 無右孩子，則返回“空”。LeftSibling( T, e ).初始條件：二叉樹T 存在， e

13、 是 T 中某個結點。操作結果：返回e 的左兄弟。若e 是 T 的左孩子或無左兄弟，則返回“空”。RightSibling( T, e )初始條件：二叉樹T 存在， e 是 T 中某個結點。操作結果：返回e 的右兄弟。若e 是 T 的右孩子或無右兄弟，則返回“空”。InsertChild( T, p, LR, c )初始條件：二叉樹T 存在， p 指向 T 中某個結點，LR 為 0 或 1，非空二叉樹c 與 T不相交且右子樹為空。操作結果：根據LR 為 0 或 1，插入 c 為 T 中 p 所指結點的左或右子樹。p 所指結點的原有左或右子樹則成為c 的右子樹。DeleteChild( T, p

14、, LR )初始條件：二叉樹T 存在， p 指向 T 中某個結點， LR 為 0 或 1。操作結果：根據LR 為 0 或 1，刪除 T 中 p 所指結點的左或右子樹。PreOrderTraverse( T, visit() )初始條件：二叉樹T 存在， Visit是對結點操作的應用函數。操作結果：先序遍歷T，對每個結點調用函數Visit一次且僅一次。一旦visit()失敗，則操作失敗。InOrderTraverse( T, visit() )初始條件：二叉樹T 存在， Visit是對結點操作的應用函數。操作結果：中序遍歷T，對每個結點調用函數Visit一次且僅一次。一旦visit()失敗，則操

15、作失敗。PostOrderTraverse( T, visit() )初始條件：二叉樹T 存在， Visit是對結點操作的應用函數。操作結果：后序遍歷T，對每個結點調用函數Visit一次且僅一次。一旦visit()失敗，則操作失敗。LevelOrderTraverse( T, visit() )初始條件：二叉樹T 存在， Visit是對結點操作的應用函數。操作結果：層次遍歷T，對每個結點調用函數Visit一次且僅一次。一旦visit()失敗，則操作失敗。ADT BinaryTree.3. 本程序包括個模塊【1】主程序模塊先聲明一棵樹和一棵二叉樹，然后輸入樹的含空格先根次序序列，構建一棵樹，然后

16、將其轉化為二叉樹，并對二叉樹進行先序、中序、后序的遞歸和非遞歸遍歷以及層序遍歷，然后輸出二叉樹的高度和總結點數，最后銷毀這兩棵樹?！?】建立樹模塊按照樹的先根序列創(chuàng)建樹?！?】樹轉化二叉樹模塊將樹轉化為二叉樹?！?】二叉樹的遍歷二叉樹的先序、中序、后序的遞歸和非遞歸遍歷以及層序遍歷?！?】二叉樹的相關信息二叉樹的高度和總結點數?！?】銷毀樹和二叉樹模塊銷毀創(chuàng)建的樹和轉換出的二叉樹?！?】棧和隊列的模塊供二叉樹先序、中序、后序的非遞歸算法調用各模塊之間關系：三、詳細設計1. 元素類型、結點類型和指針類型.樹的結點元素類型設置為字符型，這樣既可以接收字符也可以接受數字。typedef char T

17、ElemType;/樹中結點元素類型/-二叉樹的二叉鏈表存儲表示-typedef struct BiNodeTElemType data; /數據域 , 存儲結點名稱struct BiNode *lchild,*rchild;/孩子結點指針BiNode,*BiTree;二叉樹的二叉鏈表表示法示意圖：/-樹的孩子兄弟表示法-typedef struct CSNodeTElemType data; /數據域 , 存儲結點名稱struct CSNode *firstchild, *nextsibling; /孩子指針域和兄弟指針域 CSNode, *CSTree;樹的孩子兄弟表示法示意圖：.2. 構

18、造一般樹算法：按照樹的先根次序序列構建一棵樹：對于這棵樹，按照需求分析第1 頁的測試數據，用戶應當輸入（表示回車確認）ABEF CDGHIJK正確輸入所需序列后，樹的建立完成。Status CreateCSTree(CSTree &CT) /按先根序列構造樹/ 按先根次序輸入樹中結點的值（一個字符），空格字符表示空樹，構造二叉鏈表表示樹Tchar ch;ch=getchar();if(ch=' ')CT=NULL;elseif(!(CT=(CSNode *)malloc(sizeof(CSNode)printf("內存分配失?。");exit(OV

19、ERFLOW);/ifCT->data=ch;/生成根結點CreateCSTree(CT->firstchild);/構建左子樹CreateCSTree(CT->nextsibling);/構建右子樹/else.return OK;/CreateCSTree3. 轉換為二叉樹樹和二叉樹的轉換關鍵在于樹的二叉鏈表與其對應的二叉樹的二叉鏈表是相同的，只是對同一個二叉鏈表的解釋不同，二叉樹的數據域存放結點名稱，左指針域指向左孩子，右指針域指向右孩子；樹的數據域存放結點名稱，左指針域指向孩子結點，右指針域指向與該結點相鄰的一個兄弟結點。當兩者具有相同的存儲結構時， 便可以完成轉換，轉

20、換過程的實質是按照二叉樹的定義將二叉鏈表解釋為二叉樹的過程。Status ExchangeToBiTree(CSTree &CT,BiTree &T)/ 將一棵用二叉鏈表表示的樹遞歸地轉換為二叉樹if(!CT) /樹 CT 為空時，二叉樹T 為空T=NULL;else/ 若樹的對應結點不空，申請內存空間if(!(T=(BiNode *)malloc(sizeof(BiNode)printf("內存分配失?。");exit(OVERFLOW);/if/ 將樹的數據域復制到二叉樹對應的數據域T->data=CT->data;/ 若樹的孩子域不為空，

21、則用樹的孩子域創(chuàng)建二叉樹的左子樹ExchangeToBiTree(CT->firstchild,T->lchild);/ 若樹的兄弟域不為空，則用樹的兄弟域創(chuàng)建二叉樹的右子樹ExchangeToBiTree(CT->nextsibling,T->rchild);/else./ExchangeToBiTree4. 二叉樹的遍歷二叉樹有先序、中序、后序、層序四種遍歷方式，而先序、中序、后序遍歷又有遞歸和非遞歸兩種算法，總共有7 個遍歷算法。其中，先序、中序、后序非遞歸遍歷算法需要用到棧，層序遍歷需要使用隊列，隊列和棧的相關定義和算法請參考詳細設計P21。二叉樹先序、中序、后

22、序遍歷的區(qū)別僅在于訪問根結點的時機不同，而層序遍歷則是逐層從左到右訪問每一個結點。先序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問根結點(D) ；先序遍歷左子樹(L)；先序遍歷右子樹(R) 。中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)； 訪問根結點(D) ；中序遍歷右子樹(R) 。后序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則后序遍歷左子樹(L)； 后序遍歷右子樹(R) ；訪問根結點(D) 。雖然訪問根結點的時機不同，但是先左后右的規(guī)則并沒有改變。所有的遍歷函數都調用元素訪問函數Visit，他們的參數列表中均含有一個函數指針變量Statu

23、s(* Visit)(TElemType)，通過主函數向他們傳遞元素訪問函數Visit的函數名，就可以實現(xiàn)按元素訪問函數Visit設定格式輸出的目的。這樣的好處在于當輸出格式改變時，只需修改元素訪問函數Visit的輸出格式而無需更改7 個遍歷函數，做到一改全改。以下是所有遍歷算法的實現(xiàn)以及元素訪問函數Visit：/-元素訪問函數Visit-Status PrintElement(TElemType e) /輸出元素e 的值printf(" %c ",e); /元素類型設定為字符型return OK;/PrintElement/-遞歸算法 -Status PreOrderTr

24、averse(BiTree T,Status(* Visit)(TElemType) /先序遍歷遞歸算法./ 采用二叉鏈表存儲結構， Visit 是對數據元素操作的應用函數/ 先序遍歷二叉樹T 的遞歸算法，對每個數據元素調用函數Visitif(T)if(Visit(T->data) /訪問根結點if(PreOrderTraverse(T->lchild,Visit) /訪問左子樹if(PreOrderTraverse(T->rchild,Visit) /訪問右子樹return OK;return ERROR; /ifelse return OK;/PreOrderTraver

25、seStatus InOrderTraverse(BiTree T,Status(* Visit)(TElemType) /中序遍歷遞歸算法/ 采用二叉鏈表存儲結構， Visit 是對數據元素操作的應用函數/ 中序遍歷二叉樹T 的遞歸算法，對每個數據元素調用函數Visitif(T)if(InOrderTraverse(T->lchild,Visit) /訪問左子樹if(Visit(T->data) /訪問根結點if(InOrderTraverse(T->rchild,Visit) /訪問右子樹return OK;return ERROR; /ifelse return OK;

26、/InOrderTraverseStatus PostOrderTraverse(BiTree T,Status(* Visit)(TElemType) /后序遍歷遞歸算法/ 采用二叉鏈表存儲結構， Visit 是對數據元素操作的應用函數/ 后序遍歷二叉樹T 的遞歸算法，對每個數據元素調用函數Visitif(T)if(PostOrderTraverse(T->lchild,Visit) /訪問左子樹if(PostOrderTraverse(T->rchild,Visit) /訪問右子樹if(Visit(T->data) /訪問根結點.return OK;return ERRO

27、R;/ifelse return OK;/PostOrderTraverse/-非遞歸遍歷算法-Status PreOrderTraverse1(BiTree T,Status(* Visit)(TElemType) /先序遍歷非遞歸算法/ 采用二叉鏈表存儲結構， Visit 是對數據元素操作的應用函數/ 先序遍歷二叉樹T 的非遞歸算法，對每個數據元素調用函數VisitStack S;InitStack(S); /初始化棧BiTree p=T;/設置工作指針p 并對其賦初值while(p|!(StackEmpty(S)if(p)if(!Visit(p->data)/訪問根結點return

28、 ERROR;Push(S,p);/根指針進棧p=p->lchild;/遍歷左子樹/ifelsePop(S,p);/根指針退棧p=p->rchild;/遍歷右子樹/else/whilereturn OK; /PreOrderTraverse1Status InOrderTraverse1(BiTree T,Status(* Visit)(TElemType) /中序遍歷非遞歸算法/ 采用二叉鏈表存儲結構， Visit 是對數據元素操作的應用函數/ 中序遍歷二叉樹T 的非遞歸算法，對每個數據元素調用函數VisitStack S;.InitStack(S);BiTree p=T;whi

29、le(p|!(StackEmpty(S)if(p)Push(S,p);/根指針進棧p=p->lchild;/遍歷左子樹/ifelsePop(S,p);/根指針退棧if(!Visit(p->data)/訪問根結點return ERROR;p=p->rchild;/遍歷右子樹/else/whilereturn OK; /InOrderTraverse1Status PostOrderTraverse1(BiTree T,Status(* Visit)(TElemType) /后序遍歷非遞歸算法/ 采用二叉鏈表存儲結構， Visit 是對數據元素操作的應用函數/ 后序遍歷二叉樹T

30、的非遞歸算法，對每個數據元素調用函數VisitBiTree p=T, q=NULL; / int n=0;Stack s;InitStack(s);while(p)|(!StackEmpty(s) while(p)Push(s,p);p=p->lchild;/whileq=NULL;while(!StackEmpty(s)GetTop(s, p);.if(p->rchild=NULL)|(p->rchild=q)if(!Visit(p->data)/訪問根結點return ERROR;if(p=T) return ERROR;q=p;Pop(s,p);/ifelsep=

31、p->rchild;break;/else/while/whilereturn OK; /PostOrderTraverse1Status LevelOrderTraverse1(BiTree T,Status(* Visit)(TElemType) /層序遍歷非遞歸算法/ 采用二叉鏈表存儲結構， Visit 是對數據元素操作的應用函數/ 層序遍歷二叉樹T 的算法，對每個數據元素調用函數VisitQueue Q;BiTree p=T;if(T)/根結點入隊列InitQueue(Q);/初始化隊列EnQueue(Q,T);while(!QueueEmpty(Q)/隊列不空DeQueue(Q

32、,p);if(!Visit(p->data)/訪問根結點return ERROR;if(p->lchild)EnQueue(Q,p->lchild);/左孩子入隊列if(p->rchild).EnQueue(Q,p->rchild);/右孩子入隊列/whileprintf("n");/ifreturn OK; /LevelOrderTraverse15. 二叉樹的信息int BiTreeDepth(BiTree T) /遞歸求二叉樹高度/ 若二叉樹T 存在，返回T 的深度（高度），否則返回0int Thigh,leftThigh,rightTh

33、igh; /分別表示二叉樹高度，左子樹高度，右子樹高度if(!T) return 0; /樹高為 0elseleftThigh=BiTreeDepth(T->lchild);/求左子樹高度rightThigh=BiTreeDepth(T->rchild);/求右子樹高度if(leftThigh>=rightThigh)/求二叉樹高度Thigh=leftThigh+1;elseThigh=rightThigh+1;/elsereturn Thigh;/BiTreeDepthint NodeSubNum(BiTree T) /統(tǒng)計二叉樹的結點個數if(!T) return 0;

34、/二叉樹為空樹，沒有結點else return(NodeSubNum(T->lchild)+NodeSubNum(T->rchild)+1); /NodeSubNum6. 銷毀樹void DestoryCSTree(CSTree &CT)/ 按照樹的定義遞歸地銷毀樹if(CT) /非空樹if(CT->firstchild)/孩子子樹非空.DestoryCSTree(CT->firstchild);if(CT->nextsibling) /兄弟子樹非空DestoryCSTree(CT->nextsibling);free(CT); /釋放根結點CT=N

35、ULL;/空指針賦0/if/DestoryTreevoid DestoryBiTree(BiTree &T)/ 按照二叉樹定義遞歸地銷毀二叉樹if(T) /非空樹if(T->lchild) /左子樹非空 , 銷毀左子樹DestoryBiTree(T->lchild);if(T->rchild) /右子樹非空 , 銷毀右子樹DestoryBiTree(T->rchild);free(T); /釋放根結點T=NULL;/空指針賦0/if/DestoryTreevoid DestoryTree(CSTree &CT,BiTree &T)/ 銷毀樹和二叉

36、樹DestoryCSTree(CT);DestoryBiTree(T);printf("->生成的樹和二叉樹已被銷毀！");/DestoryTree7. 棧和隊列的定義及算法/-棧的順序存儲表示-typedef BiTree SElemType;/棧的元素為二叉樹指針類型typedef struct /棧的順序存儲表示SElemType *base;/棧底指針，在棧構造之前和銷毀之后，base 的值為 NULLSElemType *top;/棧頂指針.int stacksize;/當前已分配的存儲空間，以元素為單位Stack;/-隊列的鏈式存儲表示-typedef B

37、iTree QElemType;/隊列元素為二叉樹指針類型typedef struct QNode /鏈隊列的C 語言表示QElemType data;/數據域struct QNode * next;/指針域QNode,* QueuePtr;typedef structQueuePtr front; /隊頭指針QueuePtr rear;/隊尾指針Queue;/-棧的相關函數 ( 供非遞歸后序遍歷使用)-Status InitStack(Stack &S)/構造一個空的順序棧if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(S

38、ElemType)printf("內存分配失??！n");exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStackStatus DestoryStack(Stack &S)/釋放順序棧S 所占內存空間free(S.base);S.base=NULL;S.top=NULL;return OK;/DestoryStackStatus StackEmpty(Stack S)/判斷順序棧S 是否為空棧 , 是返回 1，否返回0.return S.top=S.base;/StackI

39、sEmptyStatus Push(Stack &S,SElemType e) /入棧if(S.top-S.base >= S.stacksize)if(!(S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType)printf("內存分配失??！n");exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize +=STACKINCREMENT;*S.top+=e;/PushStatus Pop(St

40、ack &S,SElemType &e) /出棧if(StackEmpty(S)return ERROR;e=*-S.top;return OK;/PopStatus GetTop(Stack S,SElemType &e)/ 若棧不空，用 e 返回順序棧 S 棧頂元素的值，并返回 OK，否則返回 ERRROR if(StackEmpty(S)return ERROR;e = *(S.top-1);return OK;/GetTop/-隊列的相關函數( 供非遞歸層序遍歷使用)-QueuePtr MallocQNode()/為鏈隊列結點申請內存的函數QueuePtr p;

41、 /工作指針p.if(!(p=(QueuePtr)malloc(sizeof(QNode) /申請結點的內存空間， 若失敗則提示并退出程序printf("內存分配失敗，程序即將退出！n");exit(OVERFLOW);return p; /MallocQNodeStatus InitQueue(Queue &Q) /初始化鏈隊列 / 構建一個空隊列 QQ.front=Q.rear=MallocQNode();/申請頭結點的內存空間，并使隊頭和隊尾指針同時指向它Q.front->next=NULL;Q.front->data=0;/將隊長設為0retur

42、n OK;/InitQueueStatus DestoryQueue(Queue &Q)/銷毀隊列Qwhile(Q.front) / 從頭結點開始向后逐個釋放結點內存空間 Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;/whileprintf("鏈隊列已成功銷毀！n");return OK;/DestoryQueueStatus QueueEmpty(Queue Q)/若 Q為空隊列，則返回OK;否則返回ERRORif(Q.rear=Q.front) /隊列為空的標志return OK;return ERR

43、OR;/QueueEmptyStatus EnQueue(Queue &Q,QElemType e)./ 插入元素 e 為 Q的新的隊尾元素QueuePtr p=MallocQNode();p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;Q.front->data+; /隊長 +1return OK;/EnQueueStatus DeQueue(Queue &Q,QElemType &e) / 若隊列不空 , 則刪除 Q的隊頭元素 , 用 e 返回其值 , 并返回 OK,否則返回 ERROR if(Q

44、ueueEmpty(Q)return ERROR; QueuePtr p= Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear=p)Q.rear=Q.front;free(p);Q.front->data-; /隊長 -1return OK;/DeQueue8. 主函數int main(int argc,char *argv)printf("-樹的應用-n");BiTree T=NULL;/聲明一棵二叉樹CSTree CT=NULL;/聲明一棵普通樹printf("-樹的建立-n");printf("->請按樹的先根次序輸入序列，如有空子樹， 用空格填充， 完成后輸入回車確認 n");CreateCSTree(CT);.printf("-樹的轉換 -n");printf("->正在將輸入的樹轉換為其對應的二叉樹.n");ExchangeToBiTree(CT,T);printf("->