《大數(shù)據(jù)結(jié)構(gòu) 二叉樹(shù)遍歷實(shí)驗(yàn)資料報(bào)告材料》由會(huì)員分享，可在線閱讀，更多相關(guān)《大數(shù)據(jù)結(jié)構(gòu) 二叉樹(shù)遍歷實(shí)驗(yàn)資料報(bào)告材料（20頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、word
數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)
實(shí) 驗(yàn) 報(bào) 告
題目:二叉樹(shù)的遍歷和子樹(shù)交換
指導(dǎo)教師:政宇
班級(jí)：通信1202
:徐江
學(xué)號(hào)：0909121127
需求分析
1. 演示程序分別用多種遍歷算法遍歷二叉樹(shù)并把數(shù)據(jù)輸出。
2. 輸入字符序列，遞歸方式建立二叉樹(shù)。
3.在演示過(guò)程序中，用戶(hù)敲擊鍵盤(pán)，輸入數(shù)據(jù)，即可看到數(shù)據(jù)的輸出。
4.實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)的多種遍歷算法。
遍歷算法包括：
a) 中序遞歸遍歷算法、前序遞歸遍歷算法【選
2、】
b) 中序遍歷非遞歸算法
c) 先序或后序遍歷非遞歸算法
d) 建立中序線索，并進(jìn)展中序遍歷和反中序遍歷
6.設(shè)計(jì)一個(gè)測(cè)試用的二叉樹(shù)并創(chuàng)建對(duì)應(yīng)的存二叉樹(shù)，能夠測(cè)試自己算法的邊界(包括樹(shù)節(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ù)類(lèi)型
ADT Stack{
數(shù)據(jù)對(duì)象：D={ai|ai∈char,i=1,2,3……..}
數(shù)據(jù)關(guān)系：R={< ai-1,ai >| ai-1,ai∈D,i=2,3…..}
根本操作：
3、
InitStack〔&S〕
操作結(jié)果：構(gòu)造一個(gè)空棧
StackEmpty( S )初始條件：棧S已存在。操作結(jié)果：假設(shè)S為空棧，如此返回OK，否如此返回ERROR。
Push( &S, e )初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop( &S, &e )初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。
GetTop( S, &e )初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。
}
ADT BinaryTree{
數(shù)據(jù)對(duì)象D：D是具有一樣特性的數(shù)據(jù)元素的集合。
數(shù)據(jù)關(guān)系R：
假設(shè)D=
4、Φ，如此R=Φ，稱(chēng)BinaryTree為空二叉樹(shù)；
假設(shè)D≠Φ，如此R={H}，H是如下二元關(guān)系；
〔1〕在D中存在惟一的稱(chēng)為根的數(shù)據(jù)元素root，它在關(guān)系H下無(wú)前驅(qū)；
〔2〕假設(shè)D-{root}≠Φ，如此存在D-{root}={D1,Dr}，且D1∩Dr =Φ；
〔3〕假設(shè)D1≠Φ，如此D1中存在惟一的元素x1，∈H，且存在D1上的關(guān)系H1 ?H；假設(shè)Dr≠Φ，如此Dr中存在惟一的元素xr，∈H，且存在上的關(guān)系Hr ?H；H={,,H1,Hr}；
5、 〔4〕(D1,{H1})是一棵符合本定義的二叉樹(shù)，稱(chēng)為根的左子樹(shù)；(Dr,{Hr})是一棵符合本定義的二叉樹(shù)，稱(chēng)為根的右子樹(shù)。
根本操作：
CreateBiTree( &T) 初始條件：給出二叉樹(shù)T的定義。
操作結(jié)果：按要求構(gòu)造二叉樹(shù)T。
PreOrderTraverse_re( T, print() ) 初始條件：二叉樹(shù)T存在，print是二叉樹(shù)全部結(jié)點(diǎn)輸出的應(yīng)用函數(shù)。
操作結(jié)果：先序遞歸遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。一旦 print()失敗，如此操作失敗。
InOrderTraverse( T,
6、 print() ) 初始條件：二叉樹(shù)T存在，print是二叉樹(shù)全部結(jié)點(diǎn)輸出的應(yīng)用函數(shù)。
操作結(jié)果：中序非遞歸遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。一旦printf()失敗，如此操作失敗。
InOrderTraverse_re(T,print() )
初始條件：二叉樹(shù)T在在，print是二叉樹(shù)全部結(jié)點(diǎn)輸出的應(yīng)用函數(shù)。
操作結(jié)果：中序遞歸遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。一旦 printf()失敗，如此操作失敗。
PreOrderTraverse(T,print())
初始條件：二叉樹(shù)T存在，print是二叉樹(shù)全部結(jié)
7、點(diǎn)輸出的應(yīng)用函數(shù)。
操作結(jié)果：先序非遞歸遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)print一次且僅一次。一旦print()失敗，如此操作失敗。
Levelorder(T)
初始條件：二叉樹(shù)T在在。
操作結(jié)果：分層遍歷二叉樹(shù)T，并輸出。
InOrderThreading(Thrt,T);
初始條件：二叉樹(shù)T在在。
操作結(jié)果：中序遍歷二叉樹(shù)，并將其中序線索化。
InOrderTraverse_Thr( T, print);
初始條件：二叉樹(shù)T在在。
操作結(jié)果：中序非遞歸遍歷二叉線索樹(shù)T
InThreading(p);
初始條件：結(jié)點(diǎn)p在在。
操作結(jié)果：結(jié)點(diǎn)p與子樹(shù)線
8、索化。
3.主程序的流程：
void main()
{
初始化;
提示;
執(zhí)行二叉數(shù)ADT函數(shù);
}
4.本程序包含三個(gè)模塊
1） 主程序模塊
void main(){
初始化；
{
承受命令；
顯示結(jié)果；
｝
｝
2） 鏈表模塊。遞歸調(diào)用時(shí)實(shí)現(xiàn)鏈表抽象數(shù)據(jù)類(lèi)型。
3） 棧模塊。非遞歸調(diào)用時(shí)實(shí)現(xiàn)棧的抽象數(shù)據(jù)類(lèi)型。
詳細(xì)設(shè)計(jì)
1.宏定義與全局變量
#define TElemType char
#define SElemType BiTree
#define OK 1
#define OVERFLOW 0
#define ERROR 0
9、
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
SqStack S;
BiThrTree pre;
BiThrTree i;
int CreateBiTree(BiTree &T); //創(chuàng)建二叉樹(shù)
void PreOrderTraverse_re(BiTree T,void (*print)(TElemType e)); //先序遞歸遍歷二叉樹(shù)
void InOrderTraverse(BiTree T,int (*print)(TElemType e)); //中序非遞歸遍歷二叉樹(shù)
void
10、 InOrderTraverse_re(BiTree T,int (*print)(TElemType e)) ; //中序遞歸遍歷二叉樹(shù)
void PreOrderTraverse(BiTree T,int (*print)(TElemType e)); //先序非遞歸遍歷二叉樹(shù)
int print(TElemType e); //打印元素
void InitStack(SqStack &S); //棧的初始化
void Pop(SqStack &S,SElemType &e);
void Push(SqStack &S,SElemType &e);
int Stack
11、Empty(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ù)結(jié)構(gòu)：
typedef struct BiTNode{
TElemType data;
struct BiTN
12、ode *lchild ,*rchild;
PointerTag LTag , RTag;
}BiTNode , *BiTree , BiThrNode , *BiThrTree;
根本操作：
a)構(gòu)造二叉樹(shù)T
int CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
return ERROR;
T->data=ch;
if (Cr
13、eateBiTree(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->rchi
14、ld,print);
return ;
}
else
return ;
}
c)中序非遞歸遍歷二叉樹(shù)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);
15、 Pop(S,p);
if(!StackEmpty(S))
{
Pop(S,p);
print(p->data);
Push(S,p->rchild);
}
}
return;
}
d)中序遞歸遍歷二叉樹(shù)T，并輸出全部結(jié)點(diǎn)值
void InOrderTraverse_re(BiTree T,int (*print)(TElemType e))
{
if(T)
{
InOrderTraverse_re(T->lchild,print);
print(
16、T->data);
InOrderTraverse_re(T->rchild,print);
}
}
e)中序遍歷二叉樹(shù)T，并將其中序線索化，Thrt指向頭結(jié)點(diǎn)
void InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{
Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
Thrt->LTag=Link;//建頭結(jié)點(diǎn)
Thrt->RTag=Thread;
Thrt->rchild=Thrt;//右指針回指
if(!T)
Thr
17、t->lchild=Thrt;
else
{
Thrt->lchild=T;
pre=Thrt;
InThreading(T);//中序遍歷進(jìn)展中序線索化
pre->rchild=Thrt;
pre->RTag=Thread;//最后一個(gè)結(jié)點(diǎn)線索化
Thrt->rchild=pre;
}
i=Thrt;
}//InOrderThreading
f)結(jié)點(diǎn)p線索化
void InThreading(BiThrTree p) {
if (p) {
InThreading(p->lchild); // 左子樹(shù)線索化
18、
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); // 右子樹(shù)線索化
}
} // InThreading
g)//中序遍歷線索化二叉樹(shù)
19、
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-
20、>rchild;
}
return OK;
}
數(shù)據(jù)結(jié)構(gòu)：
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
根本操作：
a)創(chuàng)建一個(gè)空棧
void InitStack(SqStack &S)
{
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
S.top=S.base; //初始為空
S.stacksize=STACK_INIT_SIZE;
return;
21、
}
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,SElemTy
22、pe &e)
{
if(S.top==S.base)
return;
e=*--S.top;
return;
}
d)判斷棧是否為空棧
int StackEmpty(SqStack S)
{
if(S.top==S.base)
return OK;
else
return ERROR;
}
e)e返回S的棧頂元素
int GetTop(SqStack S,SElemType &e)
{
if(S.top==S.base)
return ERROR;
e=*(S.top-1);
return OK;
}
vo
23、id main()
{int flag;
BiTree T;
BiThrTree Thrt;
printf("******************************************************\n");
printf("** 實(shí)驗(yàn)12 二叉樹(shù)的遍歷 **\n");
printf("** 1. 實(shí)現(xiàn)二叉樹(shù)的不同遍歷算法和二叉樹(shù)的中序線索化算法 **\n");
printf("** a) 中序遞歸遍歷算法； **\n"
24、);
printf("** b) 先序遞歸遍歷算法； **\n");
printf("** c) 中序遍歷的非遞歸算法； **\n");
printf("** d) 先序或后序遍歷非遞歸算法之一； **\n");
printf("** e) 建立中序線利用線索進(jìn)展中序遍歷和反中序遍歷。 **\n");
printf("** 2. 實(shí)現(xiàn)二叉樹(shù)的按層遍歷算法。 **\n"
25、);
printf("**********************************************************\n");
printf("\n選擇操作：\n\t1.先序與中序遍歷算法\n\t2.中序線索的中序遍歷和反中序遍歷算法\n\t3.按層遍歷算法\n請(qǐng)選擇：");
scanf("%d",&flag);
switch(flag)
{ case 1:
printf("前序遞歸創(chuàng)建二叉樹(shù)〔空格 表示此結(jié)點(diǎn)為空〕:\n");
getchar();
CreateBiTree(T);
printf("中序
26、遞歸遍歷輸出:");
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)建二叉樹(shù)〔空格 表示此結(jié)點(diǎn)為
27、空〕:\n");
getchar();
CreateBiTree(T);
printf("\n中序遍歷線索化二叉樹(shù):");
InOrderThreading(Thrt , T);
InOrderTraverse_Thr(Thrt , print);
break;
case 3: printf("前序遞歸創(chuàng)建二叉樹(shù)〔空格 表示此結(jié)點(diǎn)為空〕:\n");
getchar();
CreateBiTree(T);
printf("\n按層遍歷輸出：");
Levelorder(T);
28、printf("\n");
break;
default:return;
}}
6. 函數(shù)間調(diào)用關(guān)系
main
InOrderTraverse_re
CreateBitree
PreOrderTraverse_re
InOrderTraverse
PreOrderTraverse
InOrderThreading
InOrderTraverse_Thr
Threading
Stack操作
調(diào)試分析
1、二叉樹(shù)的分層遍歷，開(kāi)始時(shí)想用隊(duì)列來(lái)做，但考慮到比擬麻煩，因而改為數(shù)組模擬隊(duì)列，簡(jiǎn)單易懂，課后
29、可自行嘗試用隊(duì)列來(lái)做。
2．? 在線索化二叉樹(shù)時(shí)考慮到如果將兩種存儲(chǔ)結(jié)構(gòu)分開(kāi)將導(dǎo)致兩個(gè)類(lèi)型的指針不能互相傳值，造成許多麻煩。比擬兩種存儲(chǔ)結(jié)構(gòu)發(fā)現(xiàn)，線索二叉樹(shù)比二叉樹(shù)多了兩個(gè)標(biāo)志域LTag,Rtag。于是把兩種存儲(chǔ)結(jié)構(gòu)合并為BiThrNode,并在建立二叉樹(shù)時(shí)把LTag,Rtag均置為L(zhǎng)ink。程序正常運(yùn)行。
3.進(jìn)入演示程序，完成編譯，連接〔即按下Ctrl F5〕進(jìn)入演示界面，或直接打開(kāi)執(zhí)行文件BiTree.exe，產(chǎn)生如如如下圖所示的界面：
⒈ 用戶(hù)需根據(jù)用戶(hù)提示信息操作，輸入二叉樹(shù)〔以空格表示空結(jié)點(diǎn)〕，輸入完成后按回車(chē)鍵，屏幕上打印出對(duì)應(yīng)于該二叉樹(shù)的各種遍歷結(jié)果。如如如
30、下圖：
六、 測(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
中序遍歷線索化二叉樹(shù)：a+b*c-d
七、 附錄
#include
#include
#define QElemType BiTNode
#define TElemType char
#define OK 1
#define OVERFLOW 0
#d
31、efine ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef enum PointerTag{Link,Thread}; //Link==0,指針，Thread==1,線索
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild ,*rchild;
PointerTag LTag , RTag;
}BiTNode , *BiTree , BiThrNode , *BiThrTree; //二叉樹(shù)
32、
#define QElemType BiTNode
#define SElemType BiTree
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
//全局變量
SqStack S;
BiThrTree pre;
BiThrTree i;
/*函數(shù)聲明*/
int CreateBiTree(BiTree &T); //創(chuàng)建二叉樹(shù)
void PreOrderTraverse_
33、re(BiTree T,void (*print)(TElemType e)); //先序遞歸遍歷二叉樹(shù)
void InOrderTraverse(BiTree T,int (*print)(TElemType e)); //中序非遞歸遍歷二叉樹(shù)
void InOrderTraverse_re(BiTree T,int (*print)(TElemType e)) ; //中序遞歸遍歷二叉樹(shù)
void PreOrderTraverse(BiTree T,int (*print)(TElemType e)); //先序非遞歸遍歷二叉樹(shù)
int print(TElemType e);
34、 //打印元素
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(BiThrTr
35、ee T, int (*print)(TElemType e));
void InThreading(BiThrTree p);
/*二叉樹(shù)的創(chuàng)建遞歸創(chuàng)建*/
int CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
return ERROR;
T->data=ch;
if (CreateBiTree(T->lchild)) T-
36、>LTag=Link;
if (CreateBiTree(T->rchild)) T->RTag=Link;
}
return OK;
}
/*******************************************/
/* 先序遞歸遍歷輸出 */
/*******************************************/
void PreOrderTraverse_re(BiTree T,int (*print)(TElemType e))
{
if(T)
{
if
37、(print(T->data))
PreOrderTraverse_re(T->lchild,print);
PreOrderTraverse_re(T->rchild,print);
return ;
}
else
return ;
}
/*******************************************/
/* 中序非遞歸遍歷輸出 */
/*******************************************/
void InOrderTraver
38、se(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
39、);
}
}
return;
}
/*******************************************/
/* 中序遞歸遍歷輸出 */
/*******************************************/
void InOrderTraverse_re(BiTree T,int (*print)(TElemType e))
{
if(T)
{
InOrderTraverse_re(T->lchild,p
40、rint);
print(T->data);
InOrderTraverse_re(T->rchild,print);
}
return ;
}
/*******************************************/
/* 按照前序非遞歸遍歷二叉樹(shù)：棧 */
/*******************************************/
void PreOrderTraverse(BiTree T,int (*print)(
41、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;
}
42、else
{
Pop(S,p);
p=p->rchild;
}
}
return;
}
void InOrderThreading(BiThrTree &Thrt,BiThrTree T)
//中序遍歷二叉樹(shù)T，并將其中序線索化，Thrt指向頭結(jié)點(diǎn)
{
Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
Thrt->LTag=Link;//建頭結(jié)點(diǎn)
Thrt->RTag=Thread;
43、
Thrt->rchild=Thrt;//右指針回指
if(!T)
Thrt->lchild=Thrt;
else
{
Thrt->lchild=T;
pre=Thrt;
InThreading(T);//中序遍歷進(jìn)展中序線索化
pre->rchild=Thrt;
pre->RTag=Thread;//最后一個(gè)結(jié)點(diǎn)線索化
Thrt->rchild=pre;
}
i=Thrt;
}//InOrderThreading
void InThreading(BiThrTree p) {
if (p) {
I
44、nThreading(p->lchild); // 左子樹(shù)線索化
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); // 右子樹(shù)線索化
}
} // InT
45、hreading
int InOrderTraverse_Thr(BiThrTree T, int (*print)(TElemType e))
//中序遍歷線索化后的二叉樹(shù)
{
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;
46、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(S
47、ElemType));
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
48、+=STACKINCREMENT;
}
*S.top++=e;
}
/*棧頂刪除元素*/
void Pop(SqStack &S,SElemType &e)
{
if(S.top==S.base)
return;
e=*--S.top;
return;
}
int StackEmpty(SqStack S) /*假設(shè)棧為空棧，如此返回OK，否如此返回ERROR*/
{
if(S.top==S.base)
return OK;
else
return ERROR;
}
int GetTop(SqStack S,SElem
49、Type &e)
{
if(S.top==S.base)
return ERROR;
e=*(S.top-1);
return OK;
}
/************************************************************/
/* 按層次順序建立一棵二叉樹(shù) */
/************************************************************/
void Levelorder(BiTree T)
{
50、 int i,j;
BiTNode *q[20],*p; /*q[20]用于模擬隊(duì)列，存儲(chǔ)入隊(duì)的結(jié)點(diǎn)*/
p=T;
if(p!=NULL)
{
i=1;q[i]=p;j=2;
} /*i為隊(duì)首位置，j為隊(duì)尾位置*/
while(i!=j)
{
p=q[i];
printf("%c",p->data); /*訪問(wèn)隊(duì)首元素*/
if (p->lchild!=NULL)
{
q[j]=p->lch
51、ild;
j++;
}
/*假設(shè)隊(duì)首元素左鏈域不為空，如此將其入隊(duì)列*/
if (p->rchild!=NULL)
{
q[j]=p->rchild;
j++;
}
/*假設(shè)隊(duì)首元素右鏈域不為空，如此將其入隊(duì)列*/
i++; /*將隊(duì)首移到下一個(gè)位置*/
}
}
void main()
{
int flag;
BiTree T;
BiThrT
52、ree Thrt;
printf("**********************************************************\n");
printf("** 實(shí)驗(yàn)12 二叉樹(shù)的遍歷 **\n");
printf("** 1. 實(shí)現(xiàn)二叉樹(shù)的不同遍歷算法和二叉樹(shù)的中序線索化算法 **\n");
printf("** a) 中序遞歸遍歷算法； **\n");
printf("** b) 先序遞歸遍歷算法；
53、 **\n");
printf("** c) 中序遍歷的非遞歸算法； **\n");
printf("** d) 先序或后序遍歷非遞歸算法之一； **\n");
printf("** e) 建立中序線利用線索進(jìn)展中序遍歷和反中序遍歷。 **\n");
printf("** 2. 實(shí)現(xiàn)二叉樹(shù)的按層遍歷算法。 **\n");
printf("*************************
54、*********************************\n");
/* printf("\n選擇操作：\n\t1.先序與中序遍歷算法\n\t2.中序線索的中序遍歷和反中序遍歷算法\n\t3.按層遍歷算法\n請(qǐng)選擇：");
scanf("%d",&flag);
switch(flag)
{
case 1:
printf("前序遞歸創(chuàng)建二叉樹(shù)〔空格 表示此結(jié)點(diǎn)為空〕:\n");
getchar();
CreateBiTree(T);
printf("中序遞歸遍歷輸出:");
InOrderTraverse_re(
55、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)建二叉樹(shù)〔空格 表示此結(jié)點(diǎn)為空〕:\n");
getchar();
Creat
56、eBiTree(T);
printf("\n中序遍歷線索化二叉樹(shù):");
InOrderThreading(Thrt , T);
InOrderTraverse_Thr(Thrt , print);
break;
case 3: printf("前序遞歸創(chuàng)建二叉樹(shù)〔空格 表示此結(jié)點(diǎn)為空〕:\n");
getchar();
CreateBiTree(T);
printf("\n按層遍歷輸出：");
Levelorder(T);
printf("\n");
break;
defa
57、ult:return;
}*/
printf("前序遞歸創(chuàng)建二叉樹(shù)〔空格 表示此結(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按層遍歷輸出：");
Levelorder(T);
printf("\n中序遍歷線索化二叉樹(shù):");
InOrderThreading(Thrt , T);
InOrderTraverse_Thr(Thrt , print);
printf("\n");
while(1);
return;
}
20 / 20
大數(shù)據(jù)結(jié)構(gòu) 二叉樹(shù)遍歷實(shí)驗(yàn)資料報(bào)告材料
