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

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

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

3、后。4.為了美觀，程序的輸出結果采用了分塊顯示的模式，由虛線及標題隔開，便于用戶檢查和驗證。5.測試數據 如圖，給出一棵樹，若屏幕上顯示如下信息： ->請按樹的先根次序輸入序列，如有空子樹，用空格填充，完成后輸入回車確認 此時，你應當輸入：（表示回車確認） ABE F C DGHI J K 提示：為方便確認輸入了幾個空格，用星號*表示輸入序列中的空格，則序列如下 ABE*F*C*DGHI*J*K*（不是真實的輸入序列，供計算需輸入空格個數時用） 這時，建好的樹的先根和后根次序序列如下： 樹的先根序列 A B E F C D G H I J K 樹的后根序列 E F B C I J K H

4、 G D A 由樹和二叉樹的轉換關系知，二叉樹的先序和中序遍歷所得序列分別與樹的先根和后根遍歷所得序列相同，據此驗證轉化是否正確。二叉樹的先序和中序遍歷序列如下： 二叉樹先序序列 A B E F C D G H I J K 二叉樹中序序列 E F B C I J K H G D A2、 概要設計為了實現上述程序功能，樹采用孩子兄弟表示法，二叉樹采用二叉鏈表表示法。為此，需要兩個抽象數據類型，樹和二叉樹的抽象數據類型。1.樹的抽象數據類型定義ADT Tree  數據對象D：D是具有相同特性的數據元素的集合。   數據關系R：若D為空集，則稱為空樹；

5、0;       若D僅含有一個數據元素，則R為空集，否則R=H，H是如下二元關系：   (1)在D中存在唯一的稱為根的數據元素root，它在關系H下無前驅；   (2)若D-root，則存在D-root的一個劃分D1,D2,D3, ,Dm(m>0)， 對于任意jk(1j,km)有DjDk=,且對任意的i(1im)， 唯一存在數據元素xiDi有<root,xi>H; (3)對應于D-root的劃分，H-<root,xi>,<root,xm&

6、gt;有唯一的一個劃分 H1，H2,Hm(m>0)，對任意jk(1j,km)有HjHk=，且對任意i (1im),Hi是Di上的二元關系，(Di,Hi)是一棵符合本定義的樹， 稱為根root的子樹。  基本操作P：  InitTree(&T);  操作結果：構造空樹T。  DestroyTree(&T);  初始條件：樹T存在。  操作結果：銷毀樹T。  CreateTree(&T,definition);  初始條件：definition給出樹T的定義。  操作結

7、果：按definition構造樹T。  ClearTree(&T);  初始條件：樹T存在。  操作結果：將樹T清為空樹。  TreeEmpty(T);  初始條件：樹T存在。  操作結果：若T為空樹，則返回TRUE，否則返回FALSE。  TreeDepth(T);  初始條件：樹T存在。  操作結果：返回的深度。  Root(T);  初始條件：樹T存在。  操作結果：返回T的根。  Value(T,cur_e);  初始條件：樹T存在，cur

8、_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的非葉子結點，則

9、返回它的最左孩子，否則返回“空”。  RightSibling(T,cur_e);  初始條件：樹T存在，cur_e是T中某個結點。  操作結果：若cur_e有右兄弟，則返回它的右兄弟，否則返回“空”。  InsertChild(&T,&p,I,c);  初始條件：樹存在，指向中某個結點，1ip指結點的度，非空樹與不相交。  操作結果：插入c為中指結點的第棵子樹。  DeleteChild(&T,&p,i);  初始條件：樹T存在，p指向T中某個結點，1ip指結點的度。 

10、操作結果：刪除中所指結點的第棵子樹。  TraverseTree(T,visit();  初始條件：樹T存在，visit是對結點操作的應用函數。  操作結果：按某種次序對T的每個結點調用函數visit( )一次且至多一次。一旦visit( )失敗，則操作失敗。 ADT Tree2.二叉樹的抽象數據類型定義ADT BinaryTree 數據對象D：D是具有相同特性的數據元素的集合。 數據關系R： 若D=，則R=，稱BinaryTree為空二叉樹； 若D，則R=H，H是如下二元關系； （1）在D中存在惟一的稱為根的數據元素root，它在關系H下無前

11、驅； （2）若D-root，則存在D-root=D1,Dr，且D1Dr =； （3）若D1，則D1中存在惟一的元素x1，<root,x1>H，且存在D1上的關系H1 H；若Dr，則Dr中存在惟一的元素xr，<root,xr>H，且存在上的關系Hr H；H=<root,x1>,<root,xr>,H1,Hr； （4）(D1,H1)是一棵符合本定義的二叉樹，稱為根的左子樹；(Dr,Hr)是一棵符合本定義的二叉樹，稱為根的右子樹。 基本操作： InitBiTree( &T ) 操作結果：構造空二叉樹T。 DestroyBiTree( &

12、T ) 初始條件：二叉樹T已存在。 操作結果：銷毀二叉樹T。 CreateBiTree( &T, definition ) 初始條件：definition給出二叉樹T的定義。 操作結果：按definiton構造二叉樹T。 ClearBiTree( &T ) 初始條件：二叉樹T存在。 操作結果：將二叉樹T清為空樹。 BiTreeEmpty( T ) 初始條件：二叉樹T存在。 操作結果：若T為空二叉樹，則返回TRUE，否則返回FALSE。 BiTreeDepth( T ) 初始條件：二叉樹T存在。 操作結果：返回T的深度。 Root( T ) 初始條件：二叉樹T存在。 操作結果：返

13、回T的根。 Value( T, e ) 初始條件：二叉樹T存在，e是T中某個結點。 操作結果：返回e的值。 Assign( T, &e, value ) 初始條件：二叉樹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中某個結點。 操

14、作結果：返回e的右孩子。若e無右孩子，則返回“空”。 LeftSibling( T, e ) 初始條件：二叉樹T存在，e是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所指結點的原有左或右

15、子樹則成為c的右子樹。 DeleteChild( T, p, 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一次且僅一次

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

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

18、以接受數字。 typedef char TElemType; /樹中結點元素類型/-二叉樹的二叉鏈表存儲表示- typedef struct BiNodeTElemType data; /數據域,存儲結點名稱struct BiNode *lchild,*rchild; /孩子結點指針 BiNode,*BiTree;二叉樹的二叉鏈表表示法示意圖：/-樹的孩子兄弟表示法- typedef struct CSNode TElemType data; /數據域,存儲結點名稱 struct CSNode *firstchild, *nextsibling; /孩子指針域和兄弟指針域 CSNode, *C

19、STree;樹的孩子兄弟表示法示意圖：2. 構造一般樹算法：按照樹的先根次序序列構建一棵樹：對于這棵樹，按照需求分析第1頁的測試數據，用戶應當輸入（表示回車確認） ABE F C DGHI J K 正確輸入所需序列后，樹的建立完成。Status CreateCSTree(CSTree &CT) /按先根序列構造樹 /按先根次序輸入樹中結點的值（一個字符），空格字符表示空樹，構造二叉鏈表表示樹Tchar ch;ch=getchar();if(ch=' ') CT=NULL;elseif(!(CT=(CSNode *)malloc(sizeof(CSNode)printf(

20、"內存分配失?。");exit(OVERFLOW); /ifCT->data=ch; /生成根結點 CreateCSTree(CT->firstchild); /構建左子樹 CreateCSTree(CT->nextsibling); /構建右子樹 /else return OK; /CreateCSTree3. 轉換為二叉樹 樹和二叉樹的轉換關鍵在于樹的二叉鏈表與其對應的二叉樹的二叉鏈表是相同的，只是對同一個二叉鏈表的解釋不同，二叉樹的數據域存放結點名稱，左指針域指向左孩子，右指針域指向右孩子；樹的數據域存放結點名稱，左指針域指向孩子結點，右指針域指向

21、與該結點相鄰的一個兄弟結點。當兩者具有相同的存儲結構時，便可以完成轉換，轉換過程的實質是按照二叉樹的定義將二叉鏈表解釋為二叉樹的過程。Status ExchangeToBiTree(CSTree &CT,BiTree &T) /將一棵用二叉鏈表表示的樹遞歸地轉換為二叉樹if(!CT) /樹CT為空時，二叉樹T為空 T=NULL;else /若樹的對應結點不空，申請內存空間if(!(T=(BiNode *)malloc(sizeof(BiNode) printf("內存分配失??！n");exit(OVERFLOW); /if /將樹的數據域復制到二叉樹對應的數

22、據域T->data=CT->data; /若樹的孩子域不為空，則用樹的孩子域創(chuàng)建二叉樹的左子樹 ExchangeToBiTree(CT->firstchild,T->lchild); /若樹的兄弟域不為空，則用樹的兄弟域創(chuàng)建二叉樹的右子樹 ExchangeToBiTree(CT->nextsibling,T->rchild); /else /ExchangeToBiTree4. 二叉樹的遍歷二叉樹有先序、中序、后序、層序四種遍歷方式，而先序、中序、后序遍歷又有遞歸和非遞歸兩種算法，總共有7個遍歷算法。其中，先序、中序、后序非遞歸遍歷算法需要用到棧，層序遍歷需

23、要使用隊列，隊列和棧的相關定義和算法請參考詳細設計P21。二叉樹先序、中序、后序遍歷的區(qū)別僅在于訪問根結點的時機不同，而層序遍歷則是逐層從左到右訪問每一個結點。先序遍歷二叉樹算法的框架是： 若二叉樹為空，則空操作； 否則 訪問根結點 (D)； 先序遍歷左子樹 (L)； 先序遍歷右子樹 (R)。中序遍歷二叉樹算法的框架是： 若二叉樹為空，則空操作； 否則 中序遍歷左子樹 (L)； 訪問根結點 (D)； 中序遍歷右子樹 (R)。后序遍歷二叉樹算法的框架是： 若二叉樹為空，則空操作； 否則 后序遍歷左子樹 (L)； 后序遍歷右子樹 (R)； 訪問根結點 (D)。雖然訪問根結點的時機不同，但是先左后右

24、的規(guī)則并沒有改變。所有的遍歷函數都調用元素訪問函數Visit，他們的參數列表中均含有一個函數指針變量Status(* Visit)(TElemType)，通過主函數向他們傳遞元素訪問函數Visit的函數名，就可以實現按元素訪問函數Visit設定格式輸出的目的。這樣的好處在于當輸出格式改變時，只需修改元素訪問函數Visit的輸出格式而無需更改7個遍歷函數，做到一改全改。以下是所有遍歷算法的實現以及元素訪問函數Visit：/-元素訪問函數Visit- Status PrintElement(TElemType e) /輸出元素e的值 printf(" %c ",e); /元素類

25、型設定為字符型return OK;/PrintElement/-遞歸算法- Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType) /先序遍歷遞歸算法 /采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數/先序遍歷二叉樹T的遞歸算法，對每個數據元素調用函數Visit if(T)if(Visit(T->data) /訪問根結點 if(PreOrderTraverse(T->lchild,Visit) /訪問左子樹 if(PreOrderTraverse(T->rchild,Visit) /訪問右子樹 ret

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

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

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

29、|!(StackEmpty(S)if(p)if(!Visit(p->data) /訪問根結點 return 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

30、的非遞歸算法，對每個數據元素調用函數Visit Stack S;InitStack(S);BiTree p=T;while(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(* Visi

31、t)(TElemType) /后序遍歷非遞歸算法 /采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數/后序遍歷二叉樹T的非遞歸算法，對每個數據元素調用函數Visit BiTree p=T, q=NULL; / int n=0; Stack s; InitStack(s); while(p)|(!StackEmpty(s) while(p) Push(s,p); p=p->lchild; /while q=NULL;while(!StackEmpty(s)GetTop(s, p);if(p->rchild=NULL)|(p->rchild=q) if(!Visit(p

32、->data) /訪問根結點 return ERROR; if(p=T) return ERROR;q=p; Pop(s,p);/ifelse p=p->rchild;break;/else/while /whilereturn OK; /PostOrderTraverse1Status LevelOrderTraverse1(BiTree T,Status(* Visit)(TElemType) /層序遍歷非遞歸算法 /采用二叉鏈表存儲結構，Visit是對數據元素操作的應用函數/層序遍歷二叉樹T的算法，對每個數據元素調用函數Visit Queue Q;BiTree p=T;if(

33、T) /根結點入隊列 InitQueue(Q); /初始化隊列 EnQueue(Q,T); while(!QueueEmpty(Q) /隊列不空 DeQueue(Q,p); if(!Visit(p->data) /訪問根結點 return ERROR; if(p->lchild) EnQueue(Q,p->lchild); /左孩子入隊列 if(p->rchild) EnQueue(Q,p->rchild); /右孩子入隊列 /while printf("n"); /ifreturn OK; /LevelOrderTraverse15.二叉樹的

34、信息int BiTreeDepth(BiTree T) /遞歸求二叉樹高度 /若二叉樹T存在，返回T的深度（高度），否則返回0int Thigh,leftThigh,rightThigh; /分別表示二叉樹高度，左子樹高度，右子樹高度if(!T) return 0; /樹高為0elseleftThigh=BiTreeDepth(T->lchild); /求左子樹高度 rightThigh=BiTreeDepth(T->rchild); /求右子樹高度 if(leftThigh>=rightThigh) /求二叉樹高度 Thigh=leftThigh+1;else Thigh=

35、rightThigh+1; /elsereturn Thigh;/BiTreeDepthint NodeSubNum(BiTree T) /統(tǒng)計二叉樹的結點個數 if(!T) return 0; /二叉樹為空樹，沒有結點 else return(NodeSubNum(T->lchild)+NodeSubNum(T->rchild)+1); /NodeSubNum6.銷毀樹 void DestoryCSTree(CSTree &CT)/按照樹的定義遞歸地銷毀樹if(CT) /非空樹 if(CT->firstchild) /孩子子樹非空 DestoryCSTree(CT-

36、>firstchild);if(CT->nextsibling) /兄弟子樹非空 DestoryCSTree(CT->nextsibling); free(CT); /釋放根結點CT=NULL; /空指針賦0 /if /DestoryTreevoid DestoryBiTree(BiTree &T)/按照二叉樹定義遞歸地銷毀二叉樹if(T) /非空樹 if(T->lchild) /左子樹非空,銷毀左子樹 DestoryBiTree(T->lchild);if(T->rchild) /右子樹非空,銷毀右子樹 DestoryBiTree(T->rc

37、hild); free(T); /釋放根結點T=NULL; /空指針賦0 /if /DestoryTreevoid DestoryTree(CSTree &CT,BiTree &T)/銷毀樹和二叉樹DestoryCSTree(CT);DestoryBiTree(T);printf("->生成的樹和二叉樹已被銷毀！"); /DestoryTree7. 棧和隊列的定義及算法/-棧的順序存儲表示- typedef BiTree SElemType; /棧的元素為二叉樹指針類型 typedef struct /棧的順序存儲表示 SElemType *base;

38、 /棧底指針，在棧構造之前和銷毀之后，base的值為NULL SElemType *top; /棧頂指針int stacksize; /當前已分配的存儲空間，以元素為單位 Stack; /-隊列的鏈式存儲表示- typedef BiTree QElemType; /隊列元素為二叉樹指針類型typedef struct QNode /鏈隊列的C語言表示 QElemType data; /數據域 struct QNode * next; /指針域 QNode,* QueuePtr;typedef structQueuePtr front; /隊頭指針 QueuePtr rear; /隊尾指針 Qu

39、eue; /-棧的相關函數(供非遞歸后序遍歷使用)-Status InitStack(Stack &S)/構造一個空的順序棧 if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)printf("內存分配失?。");exit(OVERFLOW); S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; /InitStackStatus DestoryStack(Stack &S)/釋放順序棧S所占內存空間 free(S.base);S

40、.base=NULL;S.top=NULL; return OK; /DestoryStackStatus StackEmpty(Stack S)/判斷順序棧S是否為空棧,是返回1，否返回0 return S.top=S.base; /StackIsEmptyStatus 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) p

41、rintf("內存分配失??！n"); exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize +=STACKINCREMENT;*S.top+=e; /PushStatus Pop(Stack &S,SElemType &e) /出棧 if(StackEmpty(S) return ERROR; e=*-S.top; return OK; /PopStatus GetTop(Stack S,SElemType &e)/若棧不空，用e返回順序棧S棧頂元素的值，并返回OK，否則返回ERRROR

42、if(StackEmpty(S) return ERROR; e = *(S.top-1); return OK; /GetTop/-隊列的相關函數(供非遞歸層序遍歷使用)-QueuePtr MallocQNode()/為鏈隊列結點申請內存的函數QueuePtr p; /工作指針p if(!(p=(QueuePtr)malloc(sizeof(QNode) /申請結點的內存空間，若失敗則提示并退出程序printf("內存分配失敗，程序即將退出！n");exit(OVERFLOW);return p; /MallocQNode Status InitQueue(Queue &

43、amp;Q) /初始化鏈隊列 /構建一個空隊列 QQ.front=Q.rear=MallocQNode(); /申請頭結點的內存空間，并使隊頭和隊尾指針同時指向它 Q.front->next=NULL; Q.front->data=0; /將隊長設為0 return OK;/InitQueueStatus DestoryQueue(Queue &Q)/銷毀隊列Qwhile(Q.front) /從頭結點開始向后逐個釋放結點內存空間 Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear; /whileprintf("

44、鏈隊列已成功銷毀！n");return OK;/DestoryQueueStatus QueueEmpty(Queue Q) /若Q為空隊列，則返回OK;否則返回ERRORif(Q.rear=Q.front) /隊列為空的標志 return OK; return ERROR; /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

45、->data+; /隊長+1 return OK; /EnQueueStatus DeQueue(Queue &Q,QElemType &e) /若隊列不空,則刪除Q的隊頭元素,用e返回其值,并返回OK,否則返回ERRORif(QueueEmpty(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-; /隊長-1 return OK; /D

46、eQueue8. 主函數int main(int argc,char *argv)printf("- 樹的應用 -n");BiTree T=NULL; /聲明一棵二叉樹CSTree CT=NULL; /聲明一棵普通樹printf(" -樹的建立- n");printf("->請按樹的先根次序輸入序列，如有空子樹，用空格填充，完成后輸入回車確認n"); CreateCSTree(CT);printf(" -樹的轉換- n");printf("->正在將輸入的樹轉換為其對應的二叉樹.n"

47、);ExchangeToBiTree(CT,T); printf("->轉換操作執(zhí)行完畢！n");printf("n -二叉樹的遍歷- ");printf("nn先序遍歷遞歸 算法結果："); PreOrderTraverse(T,PrintElement);printf("nn中序遍歷遞歸 算法結果："); InOrderTraverse(T,PrintElement);printf("nn后序遍歷遞歸 算法結果："); PostOrderTraverse(T,PrintElement)

48、; printf("nn先序遍歷非遞歸算法結果："); PreOrderTraverse1(T,PrintElement);printf("nn中序遍歷非遞歸算法結果："); InOrderTraverse1(T,PrintElement);printf("nn后序遍歷非遞歸算法結果："); PostOrderTraverse1(T,PrintElement); printf("nn層序遍歷非遞歸算法結果："); LevelOrderTraverse1(T,PrintElement); printf("n -二叉樹的信息- "); printf("n該二叉樹的高度：%d",BiTreeDepth(T); printf("n二叉樹總結點數：%d",NodeSubNum(T) );printf("nn - 樹的銷毀 - ");DestoryTree(CT,T); printf("n->算法演示結束！"); system("pause"); return 0;/mai