二叉树的遍历以及树与二叉树的转换课程设计.doc

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

1、课程设计（数据结构）院、系专业姓名学号指导教师2010年月日树的应用摘要：关键词：树；二叉树；转换；遍历；递归和非递归1．实验题目实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。2．实验分析2．1总体分析2.1.1本程序的功能是对任意二叉树进行递归前序遍历和后序遍历，用栈实现非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。2.1.2本程序要求用户以字符输入，若要实现终端结点，最后以回车键建入数据。2.1.3本程序的结果将依次打印出递归前序遍历和后序遍历，用栈实现非递归的前序和中序遍历和后序遍历，和线

2、索化层序遍历，输入树及树传换成二叉树。2.2具体分析2.2.1二叉树创建用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1的值存入左孩子，为2*i+2的存入右孩子。BiNodecreat()，BiNodestree_creat(char*a,intk)。2.2.2先序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。voidPreOrder(BiNoderoot)。2.2.3中序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。vo

3、idInOrder(BiNoderoot)。2.2.4后序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；voidPostOrder(BiNoderoot)。2.2.5先序非递归算法BiNode根指针，若BiNode!=NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取BiNode的右子树的根指针？voidF_PreOrder(BiNoderoot)2.2.6中序非递归算法BiNode是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问

4、根，再遍历右子树。问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取BiNode指针？voidF_inOrder(BiNoderoot)。2.2.7后序非递归算法BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。voidF_PostOrder(BiNoderoot)。2.2.8层次序遍历算法按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。voidLevelOrder(BiNoderoot)。2.2.9树与二叉树的转换算法转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的有孩

5、子。voidexchange()，classTree.3.实验步骤3.1流程图开始参数数组是否空或越界把数组的值赋给结点的数据域返回根指针结束返回空指针YN递归的给左子树赋值参数变为a[2i+1]递归的给右子树赋值参数变为a[2i+2]图1、二叉树的创建开始判断结点是否空访问根结点结束按前根遍历方式遍历左子树按前根遍历方式遍历左子树YN图2、前序递归遍历开始判断结点是否空按中根遍历方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN图3、中序递归遍历开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN图4、后序递归遍历开始申请一个BiNode

6、数组inttop=0判断结点是否空输出结点值s[++top]=root结点的值变为它的左孩子判数组是否空root=s[top--]root=root->rchild结束判数组或结点是否空NYNYN图5、前序非递归遍历开始申请一个BiNode数组]inttop=0判断结点是否空s[++top]=root结点的值变为它的左孩子判数组是否空输出结点值root=s[top--]root=root->rchild结束判数组或结点是否空NYYNNY图6、中序非递归遍历开始申请一个StackElemType数组用一个临时变量存根的信息数组标志致零s[top].ptr=pp=p->lchild

7、top++判数组标志致是否为一数组标位致一p=s[top-1].ptrp=p->rchild结束NYYNYYN判数组是否空判树是否空输出结点的数据N判数组是否空图7、后序非递归遍历开始申请一个BiNode数组s[]申请两个整形变量数组首元赋为根结点s[2*i+1]=root->lchild；s[2*i+2]=root->rchildi++root=s[i]max=i输出数组结束N判断树是否空Y图8、层序遍历3.2代码：#includeusingnamespacestd;#