数据结构课程设计二叉树的创建和遍历.doc

安徽工程大学
数据结构
课程设计说明书
 
 
 
学生姓名:
 刘超
学号:
3120702109 
学院:
计算机与信息学院
专业:
信息与计算科学
题目:
二叉树的创建和遍历
指导教师
潘海玉
 
 
 
 2014年8月25日
目录
需求分析-----------------------1
概要设计-----------------------1
详细设计-----------------------3
调试分析-----------------------9
课程总结-----------------------10
附录-----------------------12
需求分析
问题描述:根据运行时输入的先序序列,创建一棵二叉树,分别对其进行先序、中序、后序、层序遍历,并显示遍历结果。
void CreateBTree(BTree &T) //按先序次序输入,构造二叉树
void PreOrder(BTree T) //递归先序遍历
void InOrder(BTree T) //递归中序遍历
void PostOrder(BTree T) //递归后序遍历
void LevelOrder(BTree T) //层序遍历
void NRPreOrder(BTree bt) //非递归先序遍历
void NRInOrder(BTree bt) //非递归中序遍历
void NRPostOrder(BTree bt) //非递归后序遍历
void main() //二叉树的建立与遍历实现

此次课程设计遍历算法的框架图
层序遍历
遍历算法
递归遍历
非递归遍历
先序遍历
中序遍历
后序遍历
先序遍历
中序遍历
后序遍历
此次课程设计所用的三组二叉树
A
A
C
B
C
B

D
F
E
E
F
D
G
H
A
B
F
G
C
D
E
H
本设计所使用的存储结构:
typedef char ElemType;//定义二叉树结点值的类型为字符型
typedef struct bnode{//二叉链表结构定义
ElemType data;
struct bnode *lchild,*rchild;
}Bnode,* BTree;
typedef struct {
BTree ptr;
int tag;
}stacknode;

void CreateBTree(BTree &T){//按先序次序输入,构造二叉链表表示的二叉树T,#表示空树
char ch;
ch=getchar();
if(ch=='#') T=NULL;//读入#时,将相应节点指针置空
else{
if(!(T=(Bnode *)malloc(sizeof(Bnode))))
printf("创建失败!");//生成结点空间
T->data=ch;
CreateBTree(T->lchild);//构造二叉树的左子树
CreateBTree(T->rchild);//构造二叉树的右子树
}
}
void PreOrder(BTree T){//递归先序遍历
if(T){
printf("%c ",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BTree T){//递归中序遍历
if(T){
InOrder(T->lchild);
printf("%c ",T->data);
InOrder(T->rchild);
}
}
void PostOrder(BTree T){//递归后序遍历
if(T){
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c ",T->data);
}
}
void LevelOrder(BTree T){//层序遍历
BTree Q[MAX];
int front=0,rear=0;
BTree p;
if(T){ //根结点入队
Q[rear]=T;
rear=(rear+1)%MAX;
}
while(front!=rear){
p=Q[front]; //队头元素出队
front=(front+1)%MAX;
printf("%c ",p->data);
if(p->lchild){ //左孩子不为