数据结构课程设计之树与二叉树的转换.doc

衡阳师范学院《数据结构》课程设计题目: 树与二叉树的转换系别: 计算机科学系专业: 计算机科学与设计班级: 1302 学生姓名: 戴志豪学号: 13190217 指导老师: 赵磊完成日期: 2015 年1 月3 号目录一. 需求分析. ………………………………………………………………… 3 二. 概要设析………………………………………………………………….3 三. 详细设计………………………………………………………………….5 ………………………………………………………………..5 2. 一般树转化成二叉树…………………………………………………..6 ………………………………………………..7 ………………………………………………..7 5. 先序遍历树的非递归算法……………………………………………..7 ……………………………………………..8 7. 层次序非递归的算法…………………………………………………..9 四. 设计与调试分析………………………………………………………….10 五. 用户手册………………………………………………………………….10 六. 测试结果………………………………………………………………….11 七. 附录(源程序) ………………………………………………………….14 八. 总结……………………………………………………………………….20 一. 需求分析本程序的功能是对任意树进行递归前序遍历和后序遍历,以及实现树的非递归的前序、和后序遍历,还有对树的层序遍历以及树与二叉树的转换。二. 概要设计对于本次设计,需要用到树的建立,树与二叉树的转换算法先序后序二叉树的递归算法; 先序后序非递归算法; 层次序遍历算法 1 树的建立用链表实现创建一个树结点的结构体, 从键盘输入数据, 存入数组。把下标为 2*i+1 的值存入左孩子, 为 2*i+2 的存入右孩子。 BiNode creat() , BiNode stree_creat(char *a,int k)。开始参数数组是否空或把数组的值赋给结点的数返回根指针结束返回空指针 Y N 递归的给左子树赋值参数变为 a[2i+1] 递归的给右子树赋值参数变为 a[2i+2] 2 一般树转化成二叉树转换时结点的第一个孩子变为它的左孩子,兄弟节点变为他的右孩子。 void exchange() , class Tree 3先序遍历树的递归算法若二叉树为空,则空操作;否则( 1 )访问根结点;( 2 )先序遍历左子树;( 3 )先序遍历右子树。 void PreOrder(BiNode root) 。开始判断结点是否访问根结点结束按前根遍历方式遍历左子树按前根遍历方式遍历左子树 YN 4 后序遍历树的递归算法若二叉树为空,则空操作;否则( 1 )后序遍历左子树;( 2 )后序遍历右子树。( 3) 访问根结点; void PostOrder(BiNode root) 。开始判断结点是否按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点 YN 5 先序遍历树的非递归算法若二叉树为空, 则空操作; 否则(1)先将根节点进栈, 在栈不为空时循环;(2) 出栈 p, 访问*p若其右孩子节点不空将右孩子节点进栈若其左孩子节点不空时再将其左孩子节点进栈。 6 后序遍历树的非递归算法采用一个栈保存需要返回的指针,先扫描根节点所有的左孩子节点并一一进栈,出栈一个节点*b 作为当前节点,然后扫描该节点的右子树。当一个节点的左右孩子节点均访问后再访问该节点,如此重复操作,直到栈空为止。 7 层次序的非递归遍历按照树的层次从左到右访问树的结点,层序遍历用于保存结点的容器是队列。 void LevelOrder(BiNode root) 。三. 详细设计 1树的建立: PTree CreatTree(PTree T) { int i=1; int fa,ch; PTNode p; for(i=1;ch!=-1;i++) { printf(" 输入第%d 结点:\n",i); scanf("%d,%d",&fa,&ch); printf("\n"); =ch; =fa; ++; [].data = ; [].parent = ; } printf("\n"); printf(" 创建的树具体情况如下:\n"); print_ptree(T); return T; 2