二叉树的生成与遍历.docx

《数据结构》课程设计报告———二叉树的生成和遍历 专 业 信息管理与信息系统 班 级 110514 小组成员 110514128 汤文莹110514129 王玉珏110514130 张蓓蕾110514131 张慕琦课程设计：二叉树的生成和遍历任务描述将二叉树以广义表形式存储在一个 TXT 文件上，通过读取 TXT 文件，建立二叉树； 求树的高度 实现二叉树的前序、中序和后序遍历； 将输出结果存储在文件内。二、问题分析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 * BT4.详细设计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 BTreeNode ** BT,char * a) /*根据a所定义的二叉树广义表字符串建立对应的存储结构*/{struct BTreeNode * p; /*定义s数组作为存储根结点指针的栈使用*/struct BTreeNode * s[StackMaxSize]; /*定义top作为s栈的栈顶指针，初值为-1，表示空栈*/int top=-1; /*用k作为处理结点的左子树和右子树的标记，k=1处理左子树，k=2处理右子树*/i