叉树的生成和遍历.doc

《数据结构》 课程设计报告 ———二叉树的生成和遍历 专 业 信息管理与信息系统 班 级 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.二叉树的层次遍历 访问元素所指结点，若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。 函数实现 # includestdio.h # includestdlib.h # 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 BTree