數(shù)據(jù)結(jié)構(gòu)二叉樹遍歷實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)之二叉樹實(shí) 驗(yàn) 報(bào) 告 題目:二叉樹的遍歷和子樹交換 指導(dǎo)老師:楊政宇 班級(jí)：通信1202 姓名:徐江 學(xué)號(hào)：0909121127需求分析1. 演示程序分別用多種遍歷算法遍歷二叉樹并把數(shù)據(jù)輸出。2. 輸入字符序列，遞歸方式建立二叉樹。3.在演示過(guò)程序中，用戶敲擊鍵盤，輸入數(shù)據(jù)，即可看到數(shù)據(jù)的輸出。4.實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)的二叉樹的多種遍歷算法。遍歷算法包括：a) 中序遞歸遍歷算法、前序遞歸遍歷算法【選】b) 中序遍歷非遞歸算法c) 先序或后序遍歷非遞歸算法d) 建立中序線索，并進(jìn)行中序遍歷和反中序遍歷5.實(shí)現(xiàn)二叉樹的按層遍歷算法6.設(shè)計(jì)一個(gè)測(cè)試用的二叉樹并創(chuàng)建對(duì)應(yīng)的內(nèi)存二叉樹，能夠測(cè)試自己算法

2、的邊界(包括樹節(jié)點(diǎn)數(shù)為0、1以及1 的不同情形)。7.測(cè)試數(shù)據(jù)：輸入數(shù)據(jù)：-+a *b -c d -e f 概要設(shè)計(jì)說(shuō)明：本程序在遞歸調(diào)用中用到了鏈表，在非遞歸調(diào)用時(shí)用到了棧。1. 棧的抽象數(shù)據(jù)類型adt stack數(shù)據(jù)對(duì)象：d=ai|aichar,i=1,2,3.數(shù)據(jù)關(guān)系：r=| ai -1,ai d,i=2,3.基本操作：initstack（&s） 操作結(jié)果：構(gòu)造一個(gè)空棧stackempty( s ) 初始條件：棧s已存在。 操作結(jié)果：若s為空棧，則返回ok，否則返回error。 push( &s, e ) 初始條件：棧s已存在。 操作結(jié)果：插入元素e為新的棧頂元素。 pop( &s, &

3、e ) 初始條件：棧s已存在且非空。 操作結(jié)果：刪除s的棧頂元素，并用e返回其值。 gettop( s, &e ) 初始條件：棧s已存在且非空。 操作結(jié)果：用e返回s的棧頂元素。 2.二叉樹的抽象數(shù)據(jù)類型adt binarytree 數(shù)據(jù)對(duì)象d：d是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系r： 若d=，則r=，稱binarytree為空二叉樹； 若d，則r=h，h是如下二元關(guān)系； （1）在d中存在惟一的稱為根的數(shù)據(jù)元素root，它在關(guān)系h下無(wú)前驅(qū)； （2）若d-root，則存在d-root=d1,dr，且d1dr =； （3）若d1，則d1中存在惟一的元素x1，h，且存在d1上的 關(guān)系h1 h

4、；若dr，則dr中存在惟一的元素xr，h，且 存在上的關(guān)系hr h；h=,h1,hr； （4）(d1,h1)是一棵符合本定義的二叉樹，稱為根的左子樹；(dr,hr)是一 棵符合本定義的二叉樹，稱為根的右子樹。 基本操作： createbitree( &t) 初始條件：給出二叉樹t的定義。 操作結(jié)果：按要求構(gòu)造二叉樹t。 preordertraverse_re( t, print() ) 初始條件：二叉樹t存在，print是二叉樹全部結(jié)點(diǎn)輸出的應(yīng)用函數(shù)。 操作結(jié)果：先序遞歸遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。一旦 print()失敗，則操作失敗。 inordertraverse(

5、t, print() ) 初始條件：二叉樹t存在，print是二叉樹全部結(jié)點(diǎn)輸出的應(yīng)用函數(shù)。 操作結(jié)果：中序非遞歸遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。一 旦printf()失敗，則操作失敗。 inordertraverse_re(t,print() ) 初始條件：二叉樹t在在，print是二叉樹全部結(jié)點(diǎn)輸出的應(yīng)用函數(shù)。操作結(jié)果：中序遞歸遍歷t，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。一旦 printf()失敗，則操作失敗。 preordertraverse(t,print() 初始條件：二叉樹t存在，print是二叉樹全部結(jié)點(diǎn)輸出的應(yīng)用函數(shù)。 操作結(jié)果：先序非遞歸遍歷t，對(duì)每個(gè)

6、結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。一 旦print()失敗，則操作失敗。 levelorder(t) 初始條件：二叉樹t在在。操作結(jié)果：分層遍歷二叉樹t，并輸出。inorderthreading(thrt,t);初始條件：二叉樹t在在。操作結(jié)果：中序遍歷二叉樹，并將其中序線索化。inordertraverse_thr( t, print);初始條件：二叉樹t在在。操作結(jié)果：中序非遞歸遍歷二叉線索樹tinthreading(p);初始條件：結(jié)點(diǎn)p在在。操作結(jié)果：結(jié)點(diǎn)p及子樹線索化。3.主程序的流程：void main()初始化;提示;執(zhí)行二叉數(shù)adt函數(shù);4.本程序包含三個(gè)模塊1） 主程序模塊

7、void main()初始化；接受命令；顯示結(jié)果；2） 鏈表模塊。遞歸調(diào)用時(shí)實(shí)現(xiàn)鏈表抽象數(shù)據(jù)類型。3） 棧模塊。非遞歸調(diào)用時(shí)實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型。詳細(xì)設(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;2.函數(shù)定義int createbitree(bitree &t);

8、/創(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(telemtyp

9、e 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)

10、(telemtype e);void inthreading(bithrtree p);3.二叉樹鏈表數(shù)據(jù)結(jié)構(gòu)：typedef struct bitnodetelemtype data;struct bitnode *lchild ,*rchild;pointertag ltag , rtag;bitnode , *bitree , bithrnode , *bithrtree; 基本操作：a)構(gòu)造二叉樹tint createbitree(bitree &t)char ch;scanf(%c,&ch);if(ch= )t=null;elseif(!(t=(bitnode *)malloc(si

11、zeof(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，并輸出全部結(jié)點(diǎn)值。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);r

12、eturn ;elsereturn ;c)中序非遞歸遍歷二叉樹t，并輸出全部結(jié)點(diǎn)值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

13、)中序遞歸遍歷二叉樹t，并輸出全部結(jié)點(diǎn)值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指向頭結(jié)點(diǎn) void inorderthreading(bithrtree &thrt,bithrtree t)thrt=(bithrtree)malloc(sizeof(bithrnode);thrt-lt

14、ag=link;/建頭結(jié)點(diǎn)thrt-rtag=thread;thrt-rchild=thrt;/右指針回指if(!t)thrt-lchild=thrt;elsethrt-lchild=t;pre=thrt;inthreading(t);/中序遍歷進(jìn)行中序線索化pre-rchild=thrt;pre-rtag=thread;/最后一個(gè)結(jié)點(diǎn)線索化thrt-rchild=pre;i=thrt;/inorderthreadingf)結(jié)點(diǎn)p線索化void inthreading(bithrtree p) if (p) inthreading(p-lchild); / 左子樹線索化 if (!p-lchi

15、ld) / 建前驅(qū)線索 p-ltag = thread; p-lchild = pre; if (!pre-rchild) / 建后繼線索 pre-rtag = thread; pre-rchild = p; pre = p; / 保持pre指向p的前驅(qū) 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=

16、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;4.棧數(shù)據(jù)結(jié)構(gòu)：typedef structselemtype *base;selemtype *top;int stacksize;sqstack;基本操作：a)創(chuàng)建一個(gè)空棧void initstack(sqstack &s)s.base=(selemtype*)malloc(stack_init_size*sizeof(selemtype);

17、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,s

18、elemtype &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;5.主函數(shù)void main()int flag;bitree t;bithrtree thrt;printf(*n);printf(* 實(shí)驗(yàn)12

19、 二叉樹的遍歷 *n);printf(* 1. 實(shí)現(xiàn)二叉樹的不同遍歷算法和二叉樹的中序線索化算法 *n);printf(* a) 中序遞歸遍歷算法； *n);printf(* b) 先序遞歸遍歷算法； *n);printf(* c) 中序遍歷的非遞歸算法； *n);printf(* d) 先序或后序遍歷非遞歸算法之一； *n);printf(* e) 建立中序線利用線索進(jìn)行中序遍歷和反中序遍歷。 *n);printf(* 2. 實(shí)現(xiàn)二叉樹的按層遍歷算法。 *n);printf(*n);printf(n選擇操作：nt1.先序與中序遍歷算法nt2.中序線索的中序遍歷和反中序遍歷算法nt3.按層遍歷

20、算法n請(qǐng)選擇：);scanf(%d,&flag);switch(flag) case 1:printf(前序遞歸創(chuàng)建二叉樹（空格 表示此結(jié)點(diǎn)為空）: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);b

21、reak;case 2:printf(前序遞歸創(chuàng)建二叉樹（空格 表示此結(jié)點(diǎn)為空）:n);getchar();createbitree(t);printf(n中序遍歷線索化二叉樹:);inorderthreading(thrt , t);inordertraverse_thr(thrt , print);break;case 3: printf(前序遞歸創(chuàng)建二叉樹（空格 表示此結(jié)點(diǎn)為空）:n);getchar();createbitree(t);printf(n按層遍歷輸出：);levelorder(t);printf(n);break;default:return;6. 函數(shù)間調(diào)用關(guān)系main

22、inordertraverse_recreatebitreepreordertraverse_reinordertraversepreordertraverseinorderthreadinginordertraverse_thrthreadingstack操作調(diào)試分析1、二叉樹的分層遍歷，開始時(shí)想用隊(duì)列來(lái)做，但考慮到比較麻煩，因而改為數(shù)組模擬隊(duì)列，簡(jiǎn)單易懂，課后可自行嘗試用隊(duì)列來(lái)做。2 在線索化二叉樹時(shí)考慮到如果將兩種存儲(chǔ)結(jié)構(gòu)分開將導(dǎo)致兩個(gè)類型的指針不能互相傳值，造成許多麻煩。比較兩種存儲(chǔ)結(jié)構(gòu)發(fā)現(xiàn)，線索二叉樹比二叉樹多了兩個(gè)標(biāo)志域ltag,rtag。于是把兩種存儲(chǔ)結(jié)構(gòu)合并為bithrnode

23、,并在建立二叉樹時(shí)把ltag,rtag均置為link。程序正常運(yùn)行。 3.進(jìn)入演示程序bitree.cpp，完成編譯，連接（即按下ctrl f5）進(jìn)入演示界面，或直接打開執(zhí)行文件bitree.exe，產(chǎn)生如下圖所示的界面：1 用戶需根據(jù)用戶提示信息操作，輸入二叉樹（以空格表示空結(jié)點(diǎn)），輸入完成后按回車鍵，屏幕上打印出對(duì)應(yīng)于該二叉樹的各種遍歷結(jié)果。如下圖：6、 測(cè)試結(jié)果輸入：-+a *b -c d -e f 屏幕輸出：中序遞歸遍歷輸出：a+b*c-d前序遞歸遍歷輸出：+a*b-cd中序非遞歸遍歷輸出：a+b*c-d前序非遞歸遍歷輸出：+a*b-cd按層遍歷輸出：+a*b-cd中序遍歷線索化二叉樹

24、：a+b*c-d7、 附錄bitree.cppbitree.exe#include#include#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 bitnod

25、e *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 preor

26、dertraverse_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 i

27、nitstack(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);vo

28、id 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 preordertra

29、verse_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);p

30、ush(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-r

31、child,print); return ; /*/ /* 按照前序非遞歸遍歷二叉樹：棧 */ /*/ void preordertraverse(bitree t,int (*print)(telemtype e) sqstack s;s.base=null;s.top=null;selemtype p=t;/p指向當(dāng)前訪問(wèn)的結(jié)點(diǎn) 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 inorderthre

32、ading(bithrtree &thrt,bithrtree t)/中序遍歷二叉樹t，并將其中序線索化，thrt指向頭結(jié)點(diǎn)thrt=(bithrtree)malloc(sizeof(bithrnode);thrt-ltag=link;/建頭結(jié)點(diǎn)thrt-rtag=thread;thrt-rchild=thrt;/右指針回指if(!t)thrt-lchild=thrt;elsethrt-lchild=t;pre=thrt;inthreading(t);/中序遍歷進(jìn)行中序線索化pre-rchild=thrt;pre-rtag=thread;/最后一個(gè)結(jié)點(diǎn)線索化thrt-rchild=pre;i=

33、thrt;/inorderthreadingvoid inthreading(bithrtree p) if (p) inthreading(p-lchild); / 左子樹線索化 if (!p-lchild) / 建前驅(qū)線索 p-ltag = thread; p-lchild = pre; if (!pre-rchild) / 建后繼線索 pre-rtag = thread; pre-rchild = p; pre = p; / 保持pre指向p的前驅(qū) inthreading(p-rchild); / 右子樹線索化 / inthreadingint inordertraverse_thr(b

34、ithrtree 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ù)*/*棧的初始化*/v

35、oid 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

36、=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=*

37、(s.top-1);return ok; /*/ /* 按層次順序建立一棵二叉樹 */ /*/ void levelorder(bitree t) int i,j; bitnode *q20,*p; /*q20用于模擬隊(duì)列，存儲(chǔ)入隊(duì)的結(jié)點(diǎn)*/ p=t; if(p!=null) i=1;qi=p;j=2; /*i為隊(duì)首位置，j為隊(duì)尾位置*/ while(i!=j) p=qi; printf(%c,p-data); /*訪問(wèn)隊(duì)首元素*/ if (p-lchild!=null) qj=p-lchild; j+; /*若隊(duì)首元素左鏈域不為空，則將其入隊(duì)列*/ if (p-rchild!=null) qj=p-rchild; j+; /*若隊(duì)首元素右鏈域不為空，則將其入隊(duì)列*/ i+; /*將隊(duì)首移到下一個(gè)位置*/ void main()int flag;bitree t;bithrtree thrt;printf(*n);printf(* 實(shí)驗(yàn)12 二叉樹的遍歷 *n);printf(* 1.