二叉树的中序的递归非递归遍历算法文档格式.docx
《二叉树的中序的递归非递归遍历算法文档格式.docx》由会员分享，可在线阅读，更多相关《二叉树的中序的递归非递归遍历算法文档格式.docx（17页珍藏版）》请在冰点文库上搜索。
structtree*rchild;
//右孩子
}TreeNode,*Tree;
typedefstruct//层序遍历的队列结构体定义
QElemTypebase[MAXQSIZEZ];
intfront;
//定义队头
intrear;
//定义队尾
}Sqstack1;
typedefstructstack//非递归遍历栈
Tree*base;
//定义栈底
Tree*top;
//定义栈顶
intstackszie;
//指示栈内剩余空间
}Sqstack;
六．详细设计（程序代码及核心代码流程图）
总体操作步骤：
returnOK;
}
StatusDeQueue（Sqstack1*Q,QElemType*e）//删除元素
if（Q->
front==Q->
rear）//队为空，不能删除
returnERROR;
*e=Q->
base[Q->
front];
Q->
front=（Q->
front+1）%MAXQSIZEZ;
StatusQueueEmpty（Sqstack1Q）//判断队列是否为空
if（Q.rear==Q.front）
returnTRUE;
else
returnFALSE;
voidTraverse（TreeT）//层序遍历
Sqstack1Q;
Treep;
p=T;
InitQueue（&
Q）;
//初始化
if（p）
ErQueue（&
Q,p）;
while（!
QueueEmpty（Q））
{
DeQueue（&
Q,&
p）;
//出队
printf（"
%c"
p->
data）;
if（p->
lchild）
ErQueue（&
Q,p->
lchild）;
rchild）
rchild）;
}
printf（"
\n"
）;
//**********************************
//使用递归完成中序遍历
voidInOrder（Treeroot）
if（root）//如果根节点不为空，一句左根右的顺序遍历
InOrder（root->
root->
//初始化栈
voidInStack（Sqstack*s）
s->
base=（Tree*）malloc（STACKINITSIZE*sizeof（TreeNode））;
//动态分配空间
if（!
s->
base）
栈创建失败！
"
top=s->
base;
stackszie=STACKINITSIZE;
//栈中的剩余内存
//压栈
voidPush（Sqstack*s,Treeroot）
if（（（*s）.top-（*s）.base）>
=（*s）.stackszie）//判断栈是否满？
如果满
（*s）.base=（Tree*）realloc（（*s）.base,（（*s）.stackszie+STACKINCREASESIZE）*sizeof（Tree））;
//扩容
if（!
（*s）.base）
{
printf（"
内存分配失败！
}
（*s）.top=（*s）.base+（*s）.stackszie;
（*s）.stackszie+=STACKINCREASESIZE;
*（s->
top）=root;
top++;
//进行依次入栈操作
//获得栈顶元素
voidGetTop（Sqstack*s,Tree*root）
*root=*（（*s）.top-1）;
//弹出栈顶元素
voidPop（Sqstack*s,Tree*root）
if（（*s）.top==（*s）.base）//=与==
栈已经空了！
*root=*（--（*s）.top）;
//判断栈是否为空
intStackEmpty（Sqstack*s）
if（s->
top==s->
base）
return1;
return0;
//非递归中序遍历
voidInOrderS（Treeroot）
Treep=root;
Sqstacks;
InStack（&
s）;
while（p||!
StackEmpty（&
s））
if（p）
{
Push（&
s,p）;
p=p->
lchild;
else
Pop（&
s,&
rchild;
voidPrintTree（Treeroot,intnLayer）//树状打印二叉树
inti;
if（root==NULL）
return;
PrintTree（root->
rchild,nLayer+1）;
for（i=0;
i<
nLayer;
i++）
"
%c\n"
lchild,nLayer+1）;
voidmain（）
{intlayer=0;
Treeroot=NULL;
先序遍历输入二叉树,#代表空子树:
CreateTree（&
root）;
//参数不懂
递归中序遍历输出:
InOrder（root）;
非递归中序遍历输出:
InOrderS（root）;
层序遍历二叉树：
Traverse（root）;
打印二叉树：
PrintTree（root,layer）;
七．测试分析
测试内容
测试结果
输入二叉树
正确
递归中序遍历
非递归中序遍历
层序遍历
打印二叉树
八．课程设计总结
此次课程设计中，题目为二叉树的中序遍历、层序遍历，在完成这次设计过程中，遇到了好多问题，例如：
不知道如何循环完成二叉树的非递归遍历，如何利用栈和队列的特性，怎么将它们合理的进栈和出栈。
通过这次课程设计的设计，使我明白了自己在学习过程中的一些漏洞，比如，栈和队列中出入的一些细节的处理、结构体指针的应用、运行过程中内存的分配等。
#include<
stdio.h>
stdlib.h>
#defineSTACKINITSIZE100
#defineSTACKINCREASESIZE20
//层序遍历部分
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
//******************************8
typedefcharElemType;
//重命名
//层序遍历
#defineMAXQSIZEZ100//宏定义最大长度
typedefTreeQElemType;
typedefstructstack//利用结构体定义栈
//借助结构体对栈进行重命名
voidCreateTree（Tree*root）//创建一棵树
chars;
//定义树的根节点
s=getchar（）;
//getchar和scanf的区别是什么手动从键盘输入字符
//描述树中表示空树时的情况
if（s=='
#'
）
*root=NULL;
*root=（Tree）malloc（sizeof（TreeNode））;
//申请空间，用malloc函数动态分配空间
root）//判断根节点是否为空，即，该树是否为空
分配内存失败！
（*root）->
data=s;
//将getcher得到的数据分配到树中//？
CreateTree（&
（*root）->
//？
//返回值
//层序遍历队列定义
voidInitQueue（Sqstack1*Q）//初始化前尾指针
front=Q->
rear=0;
//队头等于队尾
StatusErQueue（Sqstack1*Q,QElemTypee）//入队
if（（Q->
rear+1）%MAXQSIZEZ==Q->
front）//判断对是否满?
rear]=e;
rear=（Q->
rear+1）%MAXQSIZEZ;
voidGetTop（Sqstack*s,Tree*root）//?
?
base）//==写为=
//参数
升级会员 