用递归和非递归算法实现二叉树的三种遍历.doc

. .
优选
. . . .
. . . .
. .
}ADT Binarytree
五、详细设计
扩展先序遍历：
* include<>
* include<>
*include<>
typedefstruct binarytree
{
char data;
struct binarytree *lchild,*rchild;
}BiTreeNode,*BiTree;
void CreateBiTree(BiTree *bt)
{char ch;
ch=getchar();
if(ch=='.') *bt=NULL;
else
{
*bt=(BiTreeNode *)malloc(sizeof(BiTreeNode));
(*bt)->data=ch;
CreateBiTree(&((*bt)->lchild));
CreateBiTree(&((*bt)->rchild));
}
}
void PreOder(BiTree root)
{if(root!=NULL)
{printf("%4c",root->data);
PreOder(root->lchild);
PreOder(root->rchild);
}
}
main()
{
BiTree root;
CreateBiTree(&root);
printf("先序遍历:\n");
PreOder(root);
}
递归算法：
*include""
*define PR printf
*define ERROR 0
. .
优选
. . . .
. .
*define MAX 100
/*============================建立各构造体===============================*/
typedefstruct node
{
char data; /*数据域*/
struct node *lchild;
struct node *rchild; /*结点的左右指针，分别指向结点的左右孩子*/
}BTNode;
typedef BTNode *DataType;
typedefstruct
{
DataType data[MAX];
int top;
}SeqStack;
SeqStack *s;
/*============================栈的操作===================================*/
SeqStack *createemptystacks() /*创立一个空栈*/
{
SeqStack *s;
s=(SeqStack*)malloc(sizeof(SeqStack));
s->top=0;
return s;
}
int stackemptys(SeqStack *s) /*判栈空*/
{
return s->top==0;
}
int stackfulls(SeqStack *s) /*判栈满*/
{
return s->top==MAX;
}
void pushs(SeqStack *s,DataType x) /*进栈*/
{
if(stackfulls(s))
PR("over flow\n");
else
s->data[s->top++]=x;
}
void pops(SeqStack *s) /*退栈*/