数据结构课程设计先中后序遍历Word文件下载.docx
《数据结构课程设计先中后序遍历Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计先中后序遍历Word文件下载.docx（32页珍藏版）》请在冰点文库上搜索。
9
10
12
问题描述：
根据运行时输入的先序序列，创建一棵二叉树，分别对其
进行先序、中序、后序、层序遍历，并显示遍历结果。
voidCreateBTree（BTree&
T）
//
按先序次序输入，构造二叉树
voidPreOrder（BTreeT）
递归先序遍历
voidInOrder（BTreeT）
递归中序遍历
voidPostOrder（BTreeT）
递归后序遍历
voidLevelOrder（BTreeT）
层序遍历
voidNRPreOrder（BTreebt）
非递归先序遍历
voidNRInOrder（BTreebt）
非递归中序遍历
voidNRPostOrder（BTreebt）
非递归后序遍历
voidmain（）
二叉树的建立与遍历实现
此次课程设计遍历算法的框架图
遍历算法
非递归遍
递归遍历历
先序遍历中序遍历后序遍历先序遍历中序遍历后序遍历
此次课程设计所用的三组二叉树
A
BCBC
DEF
GHA
BF
CG
DEH
本设计所使用的存储结构：
typedefcharElemType;
//定义二叉树结点值的类型为字符型
typedefstructbnode{//二叉链表结构定义
ElemTypedata;
structbnode*lchild,*rchild;
}Bnode,*BTree;
typedefstruct{
BTreeptr;
inttag;
}stacknode;
T）{//按先序次序输入，构造二叉链
表表示的二叉树T，#表示空树
charch;
ch=getchar（）;
if（ch=='
#'
）T=NULL;
//读入#时，将相应节点指针置空
else{
if（!
（T=（Bnode*）malloc（sizeof（Bnode））））
printf（"
创建失败!
"
）;
//生成结点空间
T->
data=ch;
CreateBTree（T->
lchild）;
//构造二叉树的左子树
rchild）;
//构造二叉树的右子树
}
voidPreOrder（BTreeT）{//递归先序遍历
if（T）{
%c"
T->
data）;
PreOrder（T->
voidInOrder（BTreeT）{//递归中序遍历
InOrder（T->
voidPostOrder（BTreeT）{//递归后序遍历
PostOrder（T->
voidLevelOrder（BTreeT）{//层序遍历
BTreeQ[MAX];
intfront=0,rear=0;
BTreep;
if（T）{//根结点入队
Q[rear]=T;
rear=（rear+1）%MAX;
while（front!
=rear）{
p=Q[front];
//队头元素出队
front=（front+1）%MAX;
p->
if（p->
lchild）{//左孩子不为空，入队
Q[rear]=p->
lchild;
rchild）{//右孩子不为空，入队
rchild;
voidNRPreOrder（BTreebt）{//非递归先序遍历BTreestack[MAX],p;
inttop;
if（bt!
=NULL）{
top=0;
p=bt;
while（p!
=NULL||top>
0）{
%c"
stack[top]=p;
//预留p指针在数组中
top++;
p=p->
if（top>
top--;
p=stack[top];
///*左子树为空，进右子树*/
voidNRInOrder（BTreebt）{//非递归中序遍历BTreestack[MAX],p;
//预留p指针在数组中
/*左子树为空，进右子树*/
voidNRPostOrder（BTreebt）{//非递归后序遍历stacknodes[MAX],x;
BTreep=bt;
if（bt!
do{
while（p!
=NULL）{//遍历左子树
s[top].ptr=p;
s[top].tag=1;
//标记为左子树
while（top>
0&
&
s[top-1].tag==2）{
x=s[--top];
p=x.ptr;
//tag为R，表示右子树
访问完毕，故访问根结点
s[top-1].tag=2;
//遍历右子树
p=s[top-1].ptr->
}while（top>
0）;
一组测试树
运行时界面
这个程序的代码较为简单，可以实现了二叉树的三种递归遍历算法和三种非递归遍历算法还有层序遍历算法，想要改进的话可以在选择功能上下手，建立的时候提示更人性化，对输入的数据进行有效性验证，也可以改进为对遍历算法进行选择等等。
二叉树这个数据结构几乎在每一本的数据结构的书都作为
重点内容讲述，足见其在算法和程序设计界的重要地位。
但是，
到目前为止，自己还没有真正体验到它的威力，可能是学习的还
不够深刻。
像二叉树遍历的算法，用递归的算法只是简单的几行
代码，然后就可以实现输出遍历次序。
对于非递归的思想，要用
到栈这个数据结构，但是对于二叉树遍历问题来说非递归要较递
归复杂。
程序一开始总是出现语法错误，改了很多次也上网查了相关资料，才最后改为现在可以成功运行的程序。
在这个过程中，我体会到开发工程师的感觉了，就是要用挑剔的眼光想问题并且不断地改进自己的程序。
通过这次课程设计逐渐提高了自己的程序设计和调试能力，
通过上机实习，严整自己设计算法的正确性，学会了有效利用基本调试方法，查找出代码中的错误并且修改。
我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。
6.附录
#include<
stdlib.h>
stdio.h>
#include<
iostream.h>
#defineMAX10//结点个数不超过
10个
T）{//按先序次序输入，构造二叉链表表
示的二叉树T，#表示空树
（T=（Bnode*）malloc（sizeof（Bnode））））printf（"
创建
失败!
voidPostOrder（BTreeT）{//递归后序遍历if（T）{
voidNRPreOrder（BTreebt）{//非递归先序遍历
BTreestack[MAX],p;
voidNRInOrder（BTreebt）{//非递归中序遍历
voidNRPostOrder（BTreebt）{//非递归后序遍历
stacknodes[MAX],x;
//tag为R，表示右子树访
问完毕，故访问根结点
voidmain（）{//主函数
BTreeT;
T=NULL;
intselect;
while
（1）{
\n\n\n请选择要执行的操作:
\n"
1.创建二叉树\n"
2.二叉树的递归遍历算法（前、中、后）\n"
3.二叉树的层次遍历算法\n"
4.二叉树的非递归遍历算法（前、中、后）\n"
0.退出\n"
输入：
"
cin>
>
select;
switch（select）{
case0:
return;
case1:
\n请按先序次序输入各结点的值，以#表示空
树（输入时可连续输入）:
CreateBTree（T）;
break;
case2:
T）printf（"
\n未建立树，请先建树！
\n\n递归先序遍历:
PreOrder（T）;
\n递归中序遍历:
InOrder（T）;
\n递归后序遍历:
PostOrder（T）;
break;
case3:
\n\n层序遍历:
LevelOrder（T）;
case4:
\n\n非递归先序遍历:
NRPreOrder（T）;
\n非递归中序遍历:
NRInOrder（T）;
\n非递归后序遍历:
NRPostOrder（T）;
default:
\n\n请确认选择项:
升级会员 