大數(shù)據(jù)結構 二叉樹遍歷實驗資料報告材料

word數(shù)據(jù)結構之二叉樹實 驗 報 告 題目:二叉樹的遍歷和子樹交換 指導教師:政宇 班級：通信1202 :徐江 學號：0909121127需求分析1. 演示程序分別用多種遍歷算法遍歷二叉樹并把數(shù)據(jù)輸出。2. 輸入字符序列，遞歸方式建立二叉樹。3.在演示過程序中，用戶敲擊鍵盤，輸入數(shù)據(jù)，即可看到數(shù)據(jù)的輸出。4.實現(xiàn)鏈式存儲的二叉樹的多種遍歷算法。遍歷算法包括：a) 中序遞歸遍歷算法、前序遞歸遍歷算法【選】b) 中序遍歷非遞歸算法c) 先序或后序遍歷非遞歸算法d) 建立中序線索，并進展中序遍歷和反中序遍歷6.設計一個測試用的二叉樹并創(chuàng)建對應的存二叉樹，能夠測試自己算法的邊界(包括樹節(jié)點數(shù)為0、1以與>1 的不同情形)。7.測試數(shù)據(jù)：輸入數(shù)據(jù)：-+a *b -c d -e f 概要設計說明：本程序在遞歸調用中用到了鏈表，在非遞歸調用時用到了棧。1. 棧的抽象數(shù)據(jù)類型ADT Stack數(shù)據(jù)對象：D=ai|aichar,i=1,2,3.數(shù)據(jù)關系：R=< ai-1,ai >| ai-1,aiD,i=2,3.根本操作：InitStack&S 操作結果：構造一個空棧StackEmpty( S )初始條件：棧S已存在。操作結果：假設S為空棧，如此返回OK，否如此返回ERROR。 Push( &S, e )初始條件：棧S已存在。操作結果：插入元素e為新的棧頂元素。Pop( &S, &e )初始條件：棧S已存在且非空。操作結果：刪除S的棧頂元素，并用e返回其值。 GetTop( S, &e )初始條件：棧S已存在且非空。操作結果：用e返回S的棧頂元素。 ADT BinaryTree 數(shù)據(jù)對象D：D是具有一樣特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關系R： 假設D=，如此R=，稱BinaryTree為空二叉樹； 假設D，如此R=H，H是如下二元關系； 1在D中存在惟一的稱為根的數(shù)據(jù)元素root，它在關系H下無前驅； 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)是一棵符合本定義的二叉樹，稱為根的右子樹。 根本操作： CreateBiTree( &T) 初始條件：給出二叉樹T的定義。 操作結果：按要求構造二叉樹T。PreOrderTraverse_re( T, print() ) 初始條件：二叉樹T存在，print是二叉樹全部結點輸出的應用函數(shù)。 操作結果：先序遞歸遍歷T，對每個結點調用函數(shù)print一次且僅一次。一旦 print()失敗，如此操作失敗。 InOrderTraverse( T, print() ) 初始條件：二叉樹T存在，print是二叉樹全部結點輸出的應用函數(shù)。 操作結果：中序非遞歸遍歷T，對每個結點調用函數(shù)print一次且僅一次。一旦printf()失敗，如此操作失敗。 InOrderTraverse_re(T,print() ) 初始條件：二叉樹T在在，print是二叉樹全部結點輸出的應用函數(shù)。操作結果：中序遞歸遍歷T，對每個結點調用函數(shù)print一次且僅一次。一旦 printf()失敗，如此操作失敗。 PreOrderTraverse(T,print() 初始條件：二叉樹T存在，print是二叉樹全部結點輸出的應用函數(shù)。 操作結果：先序非遞歸遍歷T，對每個結點調用函數(shù)print一次且僅一次。一旦print()失敗，如此操作失敗。 Levelorder(T) 初始條件：二叉樹T在在。操作結果：分層遍歷二叉樹T，并輸出。InOrderThreading(Thrt,T);初始條件：二叉樹T在在。操作結果：中序遍歷二叉樹，并將其中序線索化。InOrderTraverse_Thr( T, print);初始條件：二叉樹T在在。操作結果：中序非遞歸遍歷二叉線索樹TInThreading(p);初始條件：結點p在在。操作結果：結點p與子樹線索化。3.主程序的流程：void main()初始化;提示;執(zhí)行二叉數(shù)ADT函數(shù);4.本程序包含三個模塊1） 主程序模塊void main()初始化；承受命令；顯示結果；2） 鏈表模塊。遞歸調用時實現(xiàn)鏈表抽象數(shù)據(jù)類型。3） 棧模塊。非遞歸調用時實現(xiàn)棧的抽象數(shù)據(jù)類型。詳細設計1.宏定義與全局變量#define TElemType char#define SElemType BiTree#define OK 1#define OVERFLOW 0#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10SqStack S;BiThrTree pre;BiThrTree i;int CreateBiTree(BiTree &T);/創(chuàng)建二叉樹void PreOrderTraverse_re(BiTree T,void (*print)(TElemType e);/先序遞歸遍歷二叉樹void InOrderTraverse(BiTree T,int (*print)(TElemType e);/中序非遞歸遍歷二叉樹void InOrderTraverse_re(BiTree T,int (*print)(TElemType e) ;/中序遞歸遍歷二叉樹void PreOrderTraverse(BiTree T,int (*print)(TElemType e);/先序非遞歸遍歷二叉樹int print(TElemType e);/打印元素void InitStack(SqStack &S);/棧的初始化void Pop(SqStack &S,SElemType &e);void Push(SqStack &S,SElemType &e);int StackEmpty(SqStack S);int GetTop(SqStack S,SElemType &e);void Levelorder(BiTree T) ;void InOrderThreading(BiThrTree &Thrt,BiThrTree T);int InOrderTraverse_Thr(BiThrTree T, int (*print)(TElemType e);void InThreading(BiThrTree p);數(shù)據(jù)結構：typedef struct BiTNodeTElemType data;struct BiTNode *lchild ,*rchild;PointerTag LTag , RTag;BiTNode , *BiTree , BiThrNode , *BiThrTree; 根本操作：a)構造二叉樹Tint CreateBiTree(BiTree &T)char ch;scanf("%c",&ch);if(ch=' ')T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode)return ERROR;T->data=ch;if (CreateBiTree(T->lchild) T->LTag=Link;if (CreateBiTree(T->rchild) T->RTag=Link;return OK;b)先序遞歸遍歷二叉數(shù)T，并輸出全部結點值。void PreOrderTraverse_re(BiTree T,int (*print)(TElemType e)if(T)if(print(T->data) PreOrderTraverse_re(T->lchild,print);PreOrderTraverse_re(T->rchild,print);return ;elsereturn ;c)中序非遞歸遍歷二叉樹T，并輸出全部結點值void InOrderTraverse(BiTree T,int (*print)(TElemType e)SqStack S;S.base=NULL;S.top=NULL;SElemType p=NULL;InitStack(S);Push(S,T);while(!StackEmpty(S)while(GetTop(S,p)&&p)Push(S,p->lchild);Pop(S,p);if(!StackEmpty(S)Pop(S,p);print(p->data);Push(S,p->rchild);return;d)中序遞歸遍歷二叉樹T，并輸出全部結點值void InOrderTraverse_re(BiTree T,int (*print)(TElemType e) if(T) InOrderTraverse_re(T->lchild,print); print(T->data); InOrderTraverse_re(T->rchild,print); e)中序遍歷二叉樹T，并將其中序線索化，Thrt指向頭結點 void InOrderThreading(BiThrTree &Thrt,BiThrTree T)Thrt=(BiThrTree)malloc(sizeof(BiThrNode);Thrt->LTag=Link;/建頭結點Thrt->RTag=Thread;Thrt->rchild=Thrt;/右指針回指if(!T)Thrt->lchild=Thrt;elseThrt->lchild=T;pre=Thrt;InThreading(T);/中序遍歷進展中序線索化pre->rchild=Thrt;pre->RTag=Thread;/最后一個結點線索化Thrt->rchild=pre;i=Thrt;/InOrderThreadingf)結點p線索化void InThreading(BiThrTree p) if (p) InThreading(p->lchild); / 左子樹線索化 if (!p->lchild) / 建前驅線索 p->LTag = Thread; p->lchild = pre; if (!pre->rchild) / 建后繼線索 pre->RTag = Thread; pre->rchild = p; pre = p; / 保持pre指向p的前驅 InThreading(p->rchild); / 右子樹線索化 / InThreadingg)/中序遍歷線索化二叉樹int InOrderTraverse_Thr(BiThrTree T, int (*print)(TElemType e)BiThrTree p=NULL;p=T->lchild;while(p!=T)while(p->LTag=Link)p=p->lchild;if(!print(p->data)return ERROR;while(p->RTag=Thread && p->rchild!=T)p=p->rchild;print(p->data);p=p->rchild;return OK;數(shù)據(jù)結構：typedef structSElemType *base;SElemType *top;int stacksize;SqStack;根本操作：a)創(chuàng)建一個空棧void InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);S.top=S.base;/初始為空S.stacksize=STACK_INIT_SIZE;return;b)棧頂插入元素void Push(SqStack &S,SElemType &e)if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;c)棧頂刪除元素void Pop(SqStack &S,SElemType &e)if(S.top=S.base)return;e=*-S.top;return;d)判斷棧是否為空棧int StackEmpty(SqStack S)if(S.top=S.base)return OK;elsereturn ERROR;e)e返回S的棧頂元素int GetTop(SqStack S,SElemType &e)if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;void main()int flag;BiTree T;BiThrTree Thrt;printf("*n");printf("* 實驗12 二叉樹的遍歷 *n");printf("* 1. 實現(xiàn)二叉樹的不同遍歷算法和二叉樹的中序線索化算法 *n");printf("* a) 中序遞歸遍歷算法； *n");printf("* b) 先序遞歸遍歷算法； *n");printf("* c) 中序遍歷的非遞歸算法； *n");printf("* d) 先序或后序遍歷非遞歸算法之一； *n");printf("* e) 建立中序線利用線索進展中序遍歷和反中序遍歷。 *n");printf("* 2. 實現(xiàn)二叉樹的按層遍歷算法。 *n");printf("*n");printf("n選擇操作：nt1.先序與中序遍歷算法nt2.中序線索的中序遍歷和反中序遍歷算法nt3.按層遍歷算法n請選擇：");scanf("%d",&flag);switch(flag) case 1:printf("前序遞歸創(chuàng)建二叉樹空格 表示此結點為空:n");getchar();CreateBiTree(T);printf("中序遞歸遍歷輸出:");InOrderTraverse_re(T,print);printf("n前序遞歸遍歷輸出：");PreOrderTraverse_re(T,print);printf("n中序非遞歸遍歷輸出：");InOrderTraverse(T,print);printf("n前序非遞歸遍歷輸出：");PreOrderTraverse(T,print); printf("n");break;case 2:printf("前序遞歸創(chuàng)建二叉樹空格 表示此結點為空:n");getchar();CreateBiTree(T);printf("n中序遍歷線索化二叉樹:");InOrderThreading(Thrt , T);InOrderTraverse_Thr(Thrt , print);break;case 3: printf("前序遞歸創(chuàng)建二叉樹空格 表示此結點為空:n");getchar();CreateBiTree(T);printf("n按層遍歷輸出：");Levelorder(T);printf("n");break;default:return;6. 函數(shù)間調用關系mainInOrderTraverse_reCreateBitreePreOrderTraverse_reInOrderTraversePreOrderTraverseInOrderThreadingInOrderTraverse_ThrThreadingStack操作調試分析1、二叉樹的分層遍歷，開始時想用隊列來做，但考慮到比擬麻煩，因而改為數(shù)組模擬隊列，簡單易懂，課后可自行嘗試用隊列來做。2  在線索化二叉樹時考慮到如果將兩種存儲結構分開將導致兩個類型的指針不能互相傳值，造成許多麻煩。比擬兩種存儲結構發(fā)現(xiàn)，線索二叉樹比二叉樹多了兩個標志域LTag,Rtag。于是把兩種存儲結構合并為BiThrNode,并在建立二叉樹時把LTag,Rtag均置為Link。程序正常運行。 3.進入演示程序，完成編譯，連接即按下Ctrl F5進入演示界面，或直接打開執(zhí)行文件BiTree.exe，產生如如如下圖所示的界面： 用戶需根據(jù)用戶提示信息操作，輸入二叉樹以空格表示空結點，輸入完成后按回車鍵，屏幕上打印出對應于該二叉樹的各種遍歷結果。如如如下圖：六、 測試結果輸入：-+a *b -c d -e f 屏幕輸出：中序遞歸遍歷輸出：a+b*c-d前序遞歸遍歷輸出：+a*b-cd中序非遞歸遍歷輸出：a+b*c-d前序非遞歸遍歷輸出：+a*b-cd按層遍歷輸出：+a*b-cd中序遍歷線索化二叉樹：a+b*c-d七、 附錄#include<stdio.h>#include<stdlib.h>#define QElemType BiTNode#define TElemType char#define OK 1#define OVERFLOW 0#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef enum PointerTagLink,Thread;/Link=0,指針，Thread=1,線索typedef struct BiTNodeTElemType data;struct BiTNode *lchild ,*rchild;PointerTag LTag , RTag;BiTNode , *BiTree , BiThrNode , *BiThrTree;/二叉樹#define QElemType BiTNode#define SElemType BiTreetypedef structSElemType *base;SElemType *top;int stacksize;SqStack;/全局變量SqStack S;BiThrTree pre;BiThrTree i;/*函數(shù)聲明*/ int CreateBiTree(BiTree &T);/創(chuàng)建二叉樹void PreOrderTraverse_re(BiTree T,void (*print)(TElemType e);/先序遞歸遍歷二叉樹void InOrderTraverse(BiTree T,int (*print)(TElemType e);/中序非遞歸遍歷二叉樹void InOrderTraverse_re(BiTree T,int (*print)(TElemType e) ;/中序遞歸遍歷二叉樹void PreOrderTraverse(BiTree T,int (*print)(TElemType e);/先序非遞歸遍歷二叉樹int print(TElemType e);/打印元素void InitStack(SqStack &S);/棧的初始化void Pop(SqStack &S,SElemType &e);void Push(SqStack &S,SElemType &e);int StackEmpty(SqStack S);int GetTop(SqStack S,SElemType &e);void Levelorder(BiTree T) ;void InOrderThreading(BiThrTree &Thrt,BiThrTree T);int InOrderTraverse_Thr(BiThrTree T, int (*print)(TElemType e);void InThreading(BiThrTree p);/*二叉樹的創(chuàng)建遞歸創(chuàng)建*/int CreateBiTree(BiTree &T)char ch;scanf("%c",&ch);if(ch=' ')T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode)return ERROR;T->data=ch;if (CreateBiTree(T->lchild) T->LTag=Link;if (CreateBiTree(T->rchild) T->RTag=Link;return OK; /*/ /* 先序遞歸遍歷輸出 */ /*/void PreOrderTraverse_re(BiTree T,int (*print)(TElemType e)if(T)if(print(T->data) PreOrderTraverse_re(T->lchild,print);PreOrderTraverse_re(T->rchild,print);return ;elsereturn ; /*/ /* 中序非遞歸遍歷輸出 */ /*/void InOrderTraverse(BiTree T,int (*print)(TElemType e)SqStack S;S.base=NULL;S.top=NULL;SElemType p=NULL;InitStack(S);Push(S,T);while(!StackEmpty(S)while(GetTop(S,p)&&p)Push(S,p->lchild);Pop(S,p);if(!StackEmpty(S)Pop(S,p);print(p->data);Push(S,p->rchild);return; /*/ /* 中序遞歸遍歷輸出 */ /*/void InOrderTraverse_re(BiTree T,int (*print)(TElemType e) if(T) InOrderTraverse_re(T->lchild,print); print(T->data); InOrderTraverse_re(T->rchild,print); return ; /*/ /* 按照前序非遞歸遍歷二叉樹：棧 */ /*/ void PreOrderTraverse(BiTree T,int (*print)(TElemType e) SqStack S;S.base=NULL;S.top=NULL;SElemType p=T;/p指向當前訪問的結點 InitStack(S); while(p|!StackEmpty(S) if(p) print(p->data); Push(S,p); p=p->lchild; else Pop(S,p); p=p->rchild; return; void InOrderThreading(BiThrTree &Thrt,BiThrTree T)/中序遍歷二叉樹T，并將其中序線索化，Thrt指向頭結點Thrt=(BiThrTree)malloc(sizeof(BiThrNode);Thrt->LTag=Link;/建頭結點Thrt->RTag=Thread;Thrt->rchild=Thrt;/右指針回指if(!T)Thrt->lchild=Thrt;elseThrt->lchild=T;pre=Thrt;InThreading(T);/中序遍歷進展中序線索化pre->rchild=Thrt;pre->RTag=Thread;/最后一個結點線索化Thrt->rchild=pre;i=Thrt;/InOrderThreadingvoid InThreading(BiThrTree p) if (p) InThreading(p->lchild); / 左子樹線索化 if (!p->lchild) / 建前驅線索 p->LTag = Thread; p->lchild = pre; if (!pre->rchild) / 建后繼線索 pre->RTag = Thread; pre->rchild = p; pre = p; / 保持pre指向p的前驅 InThreading(p->rchild); / 右子樹線索化 / InThreadingint InOrderTraverse_Thr(BiThrTree T, int (*print)(TElemType e)/中序遍歷線索化后的二叉樹BiThrTree p=NULL;p=T->lchild;while(p!=T)while(p->LTag=Link)p=p->lchild;if(!print(p->data)return ERROR;while(p->RTag=Thread && p->rchild!=T)p=p->rchild;print(p->data);p=p->rchild;return OK;/*以下為輔助函數(shù)*/int print(TElemType e)printf("%c",e);return OK;/*棧函數(shù)*/*棧的初始化*/void InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);S.top=S.base;/初始為空S.stacksize=STACK_INIT_SIZE;return;/*棧頂插入元素*/void Push(SqStack &S,SElemType &e)if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;/*棧頂刪除元素*/void Pop(SqStack &S,SElemType &e)if(S.top=S.base)return;e=*-S.top;return;int StackEmpty(SqStack S)/*假設棧為空棧，如此返回OK，否如此返回ERROR*/if(S.top=S.base)return OK;elsereturn ERROR;int GetTop(SqStack S,SElemType &e)if(S.top=S.base)return ERROR;e=*(S.top-1);return OK; /*/ /* 按層次順序建立一棵二叉樹 */ /*/ void Levelorder(BiTree T) int i,j; BiTNode *q20,*p; /*q20用于模擬隊列，存儲入隊的結點*/ p=T; if(p!=NULL) i=1;qi=p;j=2; /*i為隊首位置，j為隊尾位置*/ while(i!=j) p=qi; printf("%c",p->data); /*訪問隊首元素*/ if (p->lchild!=NULL) qj=p->lchild; j+; /*假設隊首元素左鏈域不為空，如此將其入隊列*/ if (p->rchild!=NULL) qj=p->rchild; j+; /*假設隊首元素右鏈域不為空，如此將其入隊列*/ i+; /*將隊首移到下一個位置*/ void main()int flag;BiTree T;BiThrTree Thrt;printf("*n");printf("* 實驗12 二叉樹的遍歷 *n");printf("* 1. 實現(xiàn)二叉樹的不同遍歷算法和二叉樹的中序線索化算法 *n");printf("* a) 中序遞歸遍歷算法； *n");printf("* b) 先序遞歸遍歷算法； *n");printf("* c) 中序遍歷的非遞歸算法； *n");printf("* d) 先序或后序遍歷非遞歸算法之一； *n");printf("* e) 建立中序線利用線索進展中序遍歷和反中序遍歷。 *n");printf("* 2. 實現(xiàn)二叉樹的按層遍歷算法。 *n");printf("*n");/*printf("n選擇操作：nt1.先序與中序遍歷算法nt2.中序線索的中序遍歷和反中序遍歷算法nt3.按層遍歷算法n請選擇：");scanf("%d",&flag);switch(flag)case 1:printf("前序遞歸創(chuàng)建二叉樹空格 表示此結點為空:n");getchar();CreateBiTree(T);printf("中序遞歸遍歷輸出:");InOrderTraverse_re(T,print);printf("n前序遞歸遍歷輸出：");PreOrderTraverse_re(T,print);printf("n中序非遞歸遍歷輸出：");InOrderTraverse(T,print);printf("n前序非遞歸遍歷輸出：");PreOrderTraverse(T,print); printf("n");break;case 2:printf("前序遞歸創(chuàng)建二叉樹空格 表示此結點為空:n");getchar();CreateBiTree(T);printf("n中序遍歷線索化二叉樹:");InOrderThreading(Thrt , T);InOrderTraverse_Thr(Thrt , print);break;case 3: printf("前序遞歸創(chuàng)建二叉樹空格 表示此結點為空:n");getchar();CreateBiTree(T);printf("n按層遍歷輸出：");Levelorder(T);printf("n");break;default:return;*/printf("前序遞歸創(chuàng)建二叉樹空格 表示此結點為空:n");getchar();CreateBiTree(T);printf("中序遞歸遍歷輸出:");InOrderTraverse_re(T,print);printf("n前序遞歸遍歷輸出：");PreOrderTraverse_re(T,print);printf("n中序非遞歸遍歷輸出：");InOrderTraverse(T,print);printf("n前序非遞歸遍歷輸出：");PreOrderTraverse(T,print); printf("n按層遍歷輸出：");Levelorder(T);printf("n中序遍歷線索化二叉樹:");InOrderThreading(Thrt , T);InOrderTraverse_Thr(Thrt , print);printf("n");while(1);return;20 / 20