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

《数据结构课程设计之-树与二叉树的转换.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、此文档收集于网络，如有侵权，请联系网站删除衡阳师范学院《数据结构》课程设计题目：树与二叉树的转换系别：计算机科学系专业：计算机科学与设计班级：1302学生姓名：戴志豪学号：13190217指导老师：赵磊完成日期：2015年1月3号此文档仅供学习与交流此文档收集于网络，如有侵权，请联系网站删除目录一．需求分析.…………………………………………………………………3二．概要设析………………………………………………………………….3三．详细设计………………………………………………………………….51.树的建立………………………………………………………………..52.一般树转化

2、成二叉树…………………………………………………..63.先序遍历树的递归算法………………………………………………..74.后序遍历树的递归算法………………………………………………..75.先序遍历树的非递归算法……………………………………………..76.后序遍历树的非递归算法……………………………………………..87.层次序非递归的算法…………………………………………………..9四．设计与调试分析………………………………………………………….10五．用户手册………………………………………………………………….10六．测试结果…………………………………………………………

3、……….11七．附录（源程序）………………………………………………………….14八．总结……………………………………………………………………….20此文档仅供学习与交流此文档收集于网络，如有侵权，请联系网站删除一.需求分析本程序的功能是对任意树进行递归前序遍历和后序遍历，以及实现树的非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。二．概要设计对于本次设计，需要用到树的建立,树与二叉树的转换算法先序后序二叉树的递归算法;先序后序非递归算法;层次序遍历算法1树的建立用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1的值存入左孩

4、子，为2*i+2的存入右孩子。BiNodecreat()，BiNodestree_creat(char*a,intk)。开始参数数组是否空或越界把数组的值赋给结点的数据域返回根指针结束返回空指针YN递归的给左子树赋值参数变为a[2i+1]递归的给右子树赋值参数变为a[2i+2]2一般树转化成二叉树转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的右孩子。voidexchange()，classTree3先序遍历树的递归算法若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。voidPreOrder(BiNoderoot)。此文

5、档仅供学习与交流此文档收集于网络，如有侵权，请联系网站删除开始判断结点是否空访问根结点结束按前根遍历方式遍历左子树按前根遍历方式遍历左子树YN4后序遍历树的递归算法若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；voidPostOrder(BiNoderoot)。此文档仅供学习与交流此文档收集于网络，如有侵权，请联系网站删除开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN5先序遍历树的非递归算法若二叉树为空，则空操作；否则（1）先将根节点进栈，在栈不为空时循环；(2)出栈p，访问*p若其右孩

6、子节点不空将右孩子节点进栈若其左孩子节点不空时再将其左孩子节点进栈。6后序遍历树的非递归算法采用一个栈保存需要返回的指针，先扫描根节点所有的左孩子节点并一一进栈，出栈一个节点*b作为当前节点，然后扫描该节点的右子树。当一个节点的左右孩子节点均访问后再访问该节点，如此重复操作，直到栈空为止。7层次序的非递归遍历按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。voidLevelOrder(BiNoderoot)。此文档仅供学习与交流此文档收集于网络，如有侵权，请联系网站删除三．详细设计1树的建立：PTreeCreatTree(PTreeT){inti=

7、1;intfa,ch;PTNodep;for(i=1;ch!=-1;i++){printf("输入第%d结点:",i);scanf("%d,%d",&fa,&ch);printf("");p.data=ch;p.parent=fa;T.count++;T.node[T.count].data=p.data;T.node[T.count].parent=p.parent;}printf("");printf("创建的树具体情况如下:");print_ptree(T);returnT;2一般树转换成二叉树BTNode*change(PTr