二叉树中以广义表先序中序后序递归中序非递归输出Word文件下载.docx

二叉树中以广义表先序中序后序递归中序非递归输出Word文件下载.docx

《二叉树中以广义表先序中序后序递归中序非递归输出Word文件下载.docx》由会员分享，可在线阅读，更多相关《二叉树中以广义表先序中序后序递归中序非递归输出Word文件下载.docx（7页珍藏版）》请在冰点文库上搜索。

typedefstructBiTNode{//二叉链表储存结构

TElemTypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

StatusCreateBiTree（BiTree&

T）{//先序序列建立二叉树

charch;

PrintBiTree（T->

lchild）;

if（T->

rchild!

=NULL）

{

printf（"

"

）;

}

rchild）;

）"

}

}

StatusPrintElement（TElemTypee）{//访问函数

%c"

e）;

returnOK;

StatusPreOrderTraverse（BiTreeT,Status（*Visit）（TElemTypee））{//先序遍历二叉树的递归算法

if（T）{

if（Visit（T->

data））

//printf（"

（"

if（PreOrderTraverse（T->

lchild,Visit））

//printf（"

if（PreOrderTraverse（T->

rchild,Visit））

//printf（"

returnOK;

returnERROR;

}

else

returnOK;

StatusInOrderTraverse（BiTreeT,Status（*Visit）（TElemType））{//中序遍历二叉树的递归算法

if（T）{

if（InOrderTraverse（T->

lchild,Visit））

if（Visit（T->

data））

if（InOrderTraverse（T->

rchild,Visit））

}

StatusPostOrderTraverse（BiTreeT,Status（*Visit）（TElemType））{//后序遍历二叉树的递归算法

if（PostOrderTraverse（T->

if（PostOrderTraverse（T->

rchild,Visit））

if（Visit（T->

//中序遍历二叉树的非递归算法

typedefstruct{//栈存储结构及操作

BiTree*base;

BiTree*top;

intstacksize;

}Stack;

StatusInitStack（Stack&

S）{//构造空栈

S.base=（BiTree*）malloc（STACK_INIT_SIZE*sizeof（BiTree））;

if（!

S.base）exit（OVERFLOW）;

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

StatusGetTop（StackS,BiTree&

e）{//读栈顶元素

if（S.top==S.base）returnERROR;

e=*（S.top-1）;

StatusPush（Stack&

S,BiTreee）{//入栈

if（S.top-S.base>

=S.stacksize）{

S.base=（BiTree*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（BiTree））;

if（!

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

*S.top++=e;

StatusPop（Stack&

S,BiTree&

e）{//出栈

e=*--S.top;

StatusStackEmpty（StackS）{//判栈空

if（S.base==S.top）returnTRUE;

elsereturnFALSE;

StatusInOrderTraverse2（BiTreeT,Status（*Visit）（TElemType））{//中序遍历二叉树的非递归算法

StackS;

BiTreep;

InitStack（S）;

Push（S,T）;

while（!

StackEmpty（S））{

while（

GetTop（S,p）&

&

p）Push（S,p->

Pop（S,p）;

Pop（S,p）;

if（!

Visit（p->

data））returnERROR;

Push（S,p->

}

intmain（）

{

BiTreeT;

请输入二叉树先序序列：

"

CreateBiTree（T）;

\n"

以广义表的形式输出：

PrintBiTree（T）;

\n\n"

先序递归遍历顺序：

PreOrderTraverse（T,PrintElement）;

中序递归遍历顺序：

InOrderTraverse（T,PrintElement）;

后序递归遍历顺序：

PostOrderTraverse（T,PrintElement）;

中序非递归遍历顺序：

"

InOrderTraverse2（T,PrintElement）;

return0;