樹和二叉樹(一)數(shù)據(jù)結(jié)構(gòu)實驗

1、實驗報告五月 142015姓名：陳斌 學號：E11314079 專業(yè)：13計算機科學與技術(shù)數(shù)據(jù)結(jié)構(gòu) 第三次實驗學號 E11314079 專業(yè) 計算機科學與技術(shù) 姓名 陳 斌 實驗日期 2015.05.14 教師簽字 成績 實 驗 報 告【實驗名稱】 樹和二叉樹（一） 【實驗目的】 1. 掌握二叉樹的二叉鏈表存儲表示；2. 掌握二叉樹的遍歷算法；3. 運用遍歷算法求解有關(guān)問題?！緦嶒瀮?nèi)容】1. 必做內(nèi)容任務1：以算法6.4創(chuàng)建二叉樹的存儲結(jié)構(gòu)，樹的具體形態(tài)自定。任務2：對任務1中的二叉樹分別實現(xiàn)先序、中序、后序遍歷（遞歸實現(xiàn)）和中序遍歷的非遞歸實現(xiàn)以及層序遍歷；任務3：統(tǒng)計1中樹的結(jié)點總數(shù)、葉子

2、結(jié)點總數(shù)以及樹的高度；源代碼：head.h: #include<string.h>#include<ctype.h>#include<malloc.h> /malloc( )#include<limits.h> / INT ,MAX#include<stdio.h> /EOF,NULL#include<stdlib.h> /atoi( )#include<io.h> /eof( )#include<math.h> /floor( ),ceil( ),abs( )#include<process

3、.h> /exit( )#include<iostream.h> /cout,cin/函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/OVERFLOW 在 math.h 中已定義為3typedef int Status;typedef int Boolean; / 布爾類型head2.h:#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structSElemType *base;SE

4、lemType *top;int stacksize;SqStack;typedef struct QNode QElemType data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front,rear; /* 隊頭、隊尾指針 */LinkQueue;Status InitStack(SqStack &S) /* 構(gòu)造一個空棧S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(OVERFLOW

5、); /* 存儲分配失敗 */ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;Status StackEmpty(SqStack &S) /* 若棧S為空棧，則返回TRUE，否則返回FALSE */ if(S.top=S.base) return TRUE; else return FALSE;Status GetTop(SqStack &S,QElemType &e) /* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */ if(S.top>S.base) e=*(S.top-1)

6、; return OK; else return ERROR;Status Push(SqStack &S,QElemType &e) /* 插入元素e為新的棧頂元素 */ if(S.top-S.base>=S.stacksize) /* 棧滿，追加存儲空間 */ S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); /* 存儲分配失敗 */ S.top=S.base+S.stacksize; S.stac

7、ksize+=STACKINCREMENT; *S.top+=e; return OK;Status Pop(SqStack &S,QElemType &e) /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ if(S.top=S.base) return ERROR; e=*-S.top; return OK;Status InitQueue(LinkQueue &Q) /* 構(gòu)造一個空隊列Q */ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) exit(O

8、VERFLOW); Q.front->next=NULL; return OK;Status QueueEmpty(LinkQueue &Q) /* 若Q為空隊列,則返回TRUE,否則返回FALSE */ if(Q.front=Q.rear) return TRUE; else return FALSE;Status EnQueue(LinkQueue &Q,QElemType e) /* 插入元素e為Q的新的隊尾元素 */ QueuePtr p=(QueuePtr)malloc(sizeof(QNode); if(!p) /* 存儲分配失敗 */ exit(OVERFL

9、OW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK;Status DeQueue(LinkQueue &Q,QElemType &e) /* 若隊列不空,刪除Q的隊頭元素,用e返回其值,并返回OK,否則返回ERROR */ QueuePtr p; if(Q.front=Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear=p) Q.rear=Q.f

10、ront; free(p); return OK;main.cpp:typedef char TElemType;#include"head.h"typedef struct BiTNodeTElemTypedata;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef BiTree QElemType; /* 設(shè)隊列元素為二叉樹的指針類型 */typedef BiTree SElemType; /* 設(shè)棧元素為二叉樹的指針類型 */#include"head2.h"Status InitBiTre

11、e(BiTree &T) /* 操作結(jié)果: 構(gòu)造空二叉樹T */ T=NULL; return OK;Status CreateBiTree(BiTree &T) / 算法6.4:按先序次序輸入二叉樹中結(jié)點的值(字符型)，構(gòu)造二叉鏈表表示的二叉樹T。 TElemType ch; scanf("%c",&ch); if(ch=' ') /* 空 */ T=NULL; else T=(BiTree)malloc(sizeof(BiTNode); if(!T) exit(OVERFLOW); T->data=ch; /* 生成根結(jié)點

12、*/ CreateBiTree(T->lchild); /* 構(gòu)造左子樹 */ CreateBiTree(T->rchild); /* 構(gòu)造右子樹 */ return OK;Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 初始條件: 二叉樹T存在,Visit是對結(jié)點操作的應用函數(shù)。算法6.1 */ /* 操作結(jié)果: 先序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次 */ if(T) /* T不空 */ if(Visit(T->data) /* 先訪問根結(jié)點 */if(PreOrderTrave

13、rse(T->lchild,Visit) /* 再先序遍歷左子樹 */if(PreOrderTraverse(T->rchild,Visit) /* 最后先序遍歷右子樹 */return OK;return ERROR; else return OK;Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 初始條件: 二叉樹T存在,Visit是對結(jié)點操作的應用函數(shù) */ /* 操作結(jié)果: 中序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次 */ if(T) if(InOrderTraverse(T->lc

14、hild,Visit) /* 先中序遍歷左子樹 */if(Visit(T->data) /* 再訪問根結(jié)點 */if(InOrderTraverse(T->rchild,Visit) /* 最后中序遍歷右子樹 */return OK;return ERROR; else return OK;Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 初始條件: 二叉樹T存在,Visit是對結(jié)點操作的應用函數(shù) */ /* 操作結(jié)果: 后序遞歸遍歷T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次 */ if(T) /* T不

15、空 */ if(PostOrderTraverse(T->lchild,Visit) /* 先后序遍歷左子樹 */if(PostOrderTraverse(T->rchild,Visit) /* 再后序遍歷右子樹 */if(Visit(T->data) /* 最后訪問根結(jié)點 */return OK;return ERROR; else return OK;Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType) /* 采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應用函數(shù)。 */ /* 中序遍歷二叉樹T的非遞歸算

16、法(利用棧)，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit */ SqStack S; InitStack(S); while(T|!StackEmpty(S) if(T) /* 根指針進棧,遍歷左子樹 */ Push(S,T); T=T->lchild; else /* 根指針退棧,訪問根結(jié)點,遍歷右子樹 */ Pop(S,T); if(!Visit(T->data) return ERROR; T=T->rchild; printf("n"); return OK;Status InOrderTraverse2(BiTree T,Status(*Visit)(TE

17、lemType) /* 采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應用函數(shù)。算法6.2 */ /* 中序遍歷二叉樹T的非遞歸算法(利用棧)，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit */ SqStack S; BiTree p; InitStack(S); Push(S,T); /* 根指針進棧 */ while(!StackEmpty(S) while(GetTop(S,p)&&p) Push(S,p->lchild); /* 向左走到盡頭 */ Pop(S,p); /* 空指針退棧 */ if(!StackEmpty(S) /* 訪問結(jié)點,向右一步 */ Pop(S,

18、p); if(!Visit(p->data) return ERROR; Push(S,p->rchild); printf("n"); return OK;void LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType) /* 初始條件：二叉樹T存在,Visit是對結(jié)點操作的應用函數(shù) */ /* 操作結(jié)果：層序遞歸遍歷T(利用隊列),對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次 */ LinkQueue q; QElemType a; if(T) InitQueue(q); EnQueue(q,T); while

19、(!QueueEmpty(q) DeQueue(q,a); Visit(a->data); if(a->lchild!=NULL) EnQueue(q,a->lchild); if(a->rchild!=NULL) EnQueue(q,a->rchild); printf("n"); Status visitT(TElemType e) printf("%c ",e); return OK;Status BiTreeNodeNum(BiTree T)/結(jié)點總個數(shù)if(T)return BiTreeNodeNum(T->

20、lchild)+BiTreeNodeNum(T->rchild)+1;elsereturn 0;Status BiTreeLeafNodeNum(BiTree T)/葉子結(jié)點個數(shù)if(T)if(!T->lchild&&!T->rchild)return 1;elsereturn BiTreeLeafNodeNum(T->lchild)+BiTreeLeafNodeNum(T->rchild);else return 0;Status BiTreeDepth(BiTree T)/樹的深度if(!T)return 0;elsereturn (BiTre

21、eDepth(T->lchild)>BiTreeDepth(T->rchild)?BiTreeDepth(T->lchild):BiTreeDepth(T->rchild)+1;void main()BiTree T;InitBiTree(T);cout<<"請先序輸入二叉樹(如:ab三個空格表示a為根結(jié)點,b為左子樹的二叉樹):"<<endl;CreateBiTree(T);cout<<"先序遍歷序列:"<<endl;PreOrderTraverse(T,visitT);co

22、ut<<endl;cout<<"中序遍歷序列:"<<endl;InOrderTraverse(T,visitT);cout<<endl;cout<<"后序遍歷序列:"<<endl;PostOrderTraverse(T,visitT);cout<<endl;cout<<"中序遍歷的非遞歸實現(xiàn)1(利用棧):"<<endl;InOrderTraverse1(T,visitT);cout<<"中序遍歷的非遞歸實現(xiàn)

23、2(利用棧):"<<endl;InOrderTraverse2(T,visitT);cout<<"層序遍歷(利用隊列):"<<endl;LevelOrderTraverse(T,visitT);cout<<"樹的結(jié)點總數(shù)為:"<<BiTreeNodeNum(T)<<endl;cout<<"樹的葉子結(jié)點總數(shù)為:"<<BiTreeLeafNodeNum(T)<<endl;cout<<"樹的深度為:&q

24、uot;<<BiTreeDepth(T)<<endl;運行結(jié)果：A樹的形狀：BCDGEFH先序輸入：ABG CDE H F ( “ ” 代表空格)2. 選做內(nèi)容任務4：修改算法6.4（結(jié)點及二叉樹類型分別用BiThrNode，BiThrTree，創(chuàng)建根結(jié)點的語句也要進行修改），然后對所創(chuàng)建的二叉樹進行中序線索化；任務5：對任務4得到的中序線索化樹進行中序遍歷。源代碼：head.h: #include<string.h>#include<ctype.h>#include<malloc.h> /malloc( )#include<l

25、imits.h> / INT ,MAX#include<stdio.h> /EOF,NULL#include<stdlib.h> /atoi( )#include<io.h> /eof( )#include<math.h> /floor( ),ceil( ),abs( )#include<process.h> /exit( )#include<iostream.h> /cout,cin/函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#d

26、efine INFEASIBLE -1/OVERFLOW 在 math.h 中已定義為3typedef int Status;typedef int Boolean; / 布爾類型head2.h:typedef char TElemType; typedef enumLink,ThreadPointerTag; /* Link(0):指針,Thread(1):線索 */typedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; /* 左右孩子指針 */ PointerTag LTag,RTag; /* 左

27、右標志 */BiThrNode,*BiThrTree;main.cpp:#include"head.h"#include"head2.h"Status CreateBiThrTree(BiThrTree &T) /* 按先序輸入二叉線索樹中結(jié)點的值,構(gòu)造二叉線索樹T */ /* 空格表示空結(jié)點 */ TElemType h; scanf("%c",&h); if(h=' ') T=NULL; else T=(BiThrTree)malloc(sizeof(BiThrNode); if(!T) exit(

28、OVERFLOW); T->data=h; /* 生成根結(jié)點(先序) */ CreateBiThrTree(T->lchild); /* 遞歸構(gòu)造左子樹 */ if(T->lchild) /* 有左孩子 */ T->LTag=Link; CreateBiThrTree(T->rchild); /* 遞歸構(gòu)造右子樹 */ if(T->rchild) /* 有右孩子 */ T->RTag=Link; return OK;BiThrTree pre;void InThreading(BiThrTree p) /* 中序遍歷進行中序線索化。算法6.7 */ i

29、f(p) InThreading(p->lchild); /* 遞歸左子樹線索化 */ if(!p->lchild) /* 沒有左孩子 */ p->LTag=Thread; /* 前驅(qū)線索 */ p->lchild=pre; /* 左孩子指針指向前驅(qū) */ if(!pre->rchild) /* 前驅(qū)沒有右孩子 */ pre->RTag=Thread; /* 后繼線索 */ pre->rchild=p; /* 前驅(qū)右孩子指針指向后繼(當前結(jié)點p) */ pre=p; /* 保持pre指向p的前驅(qū) */ InThreading(p->rchild)

30、; /* 遞歸右子樹線索化 */ Status InOrderThreading(BiThrTree &Thrt,BiThrTree T) /* 中序遍歷二叉樹T,并將其中序線索化,Thrt指向頭結(jié)點。算法6.6 */ Thrt=(BiThrTree)malloc(sizeof(BiThrNode); if(!Thrt) exit(OVERFLOW); Thrt->LTag=Link; /* 建頭結(jié)點 */ Thrt->RTag=Thread; Thrt->rchild=Thrt; /* 右指針回指 */ if(!T) /* 若二叉樹空，則左指針回指 */ Thrt-

31、>lchild=Thrt; else Thrt->lchild=T; pre=Thrt; InThreading(T); /* 中序遍歷進行中序線索化 */ pre->rchild=Thrt; pre->RTag=Thread; /* 最后一個結(jié)點線索化 */ Thrt->rchild=pre; return OK;Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType) /* 中序遍歷二叉線索樹T(頭結(jié)點)的非遞歸算法。算法6.5 */ BiThrTree p; p=T->lchild; /* p指