《数据结构》
课程设计报告———二叉树的生成和遍历
专业信息管理与信息系统
班级110514
小组成员110514128 汤文莹
110514129 王玉珏
110514130 张蓓蕾
110514131 张慕琦
课程设计：二叉树的生成和遍历
一、任务描述
1.将二叉树以广义表形式存储在一个 TXT 文件上，通过读取 TXT 文件，建立
二叉树；
2.求树的高度
3.实现二叉树的前序、中序和后序遍历；
4.将输出结果存储在文件内。
二、问题分析
1.设计思想
以广义表格式输入一个二叉树，将其接收至一维数组中，利用栈结构建立二叉链表树；通过先、中、后访问根结点递归算法遍历二叉树；利用队列的入队、出队操作实现二叉树的层次遍历。
例如：a(c(,d)，f(g,))建立如下图所示二叉树。
2.数据结构
定义队列数组长度
# define QueueMaxSize 20
定义栈数组长度
# define StackMaxSize 10
定义二叉树数据类型
typedef char ElemType;
struct BTreeNode{
ElemType data;
struct BTreeNode * left;
struct BTreeNode * right;
}BTreeNode;
3.主要模块设计
初始化二叉树
void InitBTree(struct BTreeNode** BT)
根据a所定义的二叉树广义表字符串建立对应的存储结构
void CreateBTree(struct BTreeNode ** BT,char * a)
前序遍历二叉树
void Preorder(struct BTreeNode * BT)
{
if(BT!=NULL) {
printf("%c",BT->data); /*访问根结点*/
Preorder(BT->left); /*前序遍历左子树*/
Preorder(BT->right); /*前序遍历右子树*/ }
}
中序遍历二叉树
void Inorder(struct BTreeNode * BT)
{
if(BT!=NULL) {
Inorder(BT->left); /*中序遍历左子树*/
printf("%c",BT->data); /*访问根结点*/
Inorder(BT->right); /*中序遍历右子树*/ }
}
后序遍历二叉树
void Postorder(struct BTreeNode * BT)
{
if(BT!=NULL) {
Postorder(BT->left); /*后序遍历左子树*/
Postorder(BT->right); /*后序遍历右子树*/
printf("%c",BT->data); /*访问根结点*/ }
}
由指针指向的一颗二叉树的深度
int BTreeDepth(struct BTreeNode * BT)
按层遍历由BT指针所指向的二叉树
void Levelorder(struct BTreeNode * BT
4.详细设计
1）二叉树的建立
其中mark的值1、2、3、4分别指str[i]为字母、‘(’、‘，’、‘)’；tag为左、右孩子的标志；
2.二叉树的层次遍历
访问元素所指结点，若该元素所指结点的左右孩子结点非空，则该元素所指
结点的左孩子指针和右孩子指针顺序入队。
函数实现
# include
# include
# define QueueMaxSize 20 /*定义队列数组长度*/
# define StackMaxSize 10 /*定义栈数组长度*/
typedef char ElemType;
struct BTreeNode{
ElemType data;
struct BTreeNode * left;
struct BTreeNode * right;
}BTreeNode;
void InitBTree(struct BTreeNode** BT)
/*初始化二叉树，即把树根指针置空*/
{
*BT=NULL;
}
void CreateBTree(struct BTreeNode ** BT,char * a) /*根据a所定义的二叉树广义表字符串建立对应的存储结构*/
{
struct BTreeNode * p;
/*定义s数组作为存储根结点指针的栈使用*/
struct BTreeNode * s[StackMaxSize];
/*定义top作为s栈的栈顶指针，初值为-1，表示空栈*/
int top=-1;
/*用k作为处理结点的左子树和右子树的标记，k=1处理左子树，k=2处理右子树*/
int k;
/*用i扫描数组a中存储的二叉树广义表字符串，初值为0*/
int i=0;
/*把树根指针置为空，即从空树开始建立二叉树*/
*BT=NULL;
/*每循环一次处理一个字符，直到扫描到字符串结束\0为止*/
while (a[i])
{
switch(a[i])
{
case ' ': /*对空格不做任何处理*/
break;
case '(':
if(top==StackMaxSize-1)
{
printf("栈空间太小，需增加StackMaxSize!\n");
exit(1);
}
top++;
s[top]=p;
k=1;
break;
case ')':
if(top==-1)
{
printf("二叉树广义表字符串错!\n");
exit(1);
}
top--;
break;
case ',':
k=2;
break;
default:
p=(struct BTreeNode * )malloc(sizeof(struct BTreeNode));
p->data=a[i];
p->left=p->right=NULL;
if(*BT==NULL)
