2016新编二叉树前序遍历的递归算法演示程序

《2016新编二叉树前序遍历的递归算法演示程序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、班级姓名========实习报告二“二叉树前序遍历的非递归算法”演示程序============（一）、程序的功能和特点程序通过键盘输入数据建立一个二叉树，通过递归算法与非递归算法两种方式用前序遍历法输出二叉树。功能包括：1.前序遍历方式建立二叉树2.前序遍历的递归算法输出二叉树3.前序遍历的非递归算法（以栈完成）输出二叉树（二）、程序的算法设计“二叉树前序遍历的非递归”算法：1.【逻辑结构与存储结构设计】程序中的二叉树的逻辑结构为树状结构；存储结构为链式存储2.【基本操作设计】程序的主要操作有：判断栈是否为空元素进栈（插入到栈顶，即将新节点插入到头部）元素出栈（删除头结点）

2、以root为根建立二叉树（输入按前序遍历方式输入字符串）等3.【算法设计】（1）前序遍历方式建立二叉树publicBinTreeNodepreOrderCreate(BinTreeNodep,Strings){得到输入字符串第i位的字符item；如果item不是参照值（此程序为”∧”）{1、生成根结点；2、把根结点的左指针作为新的根结点指针，递归调用自身生成左子树；3、把根结点的右指针作为新的根结点指针，递归调用自身生成右子树；}否则，封闭叶子节点。}（2）前序遍历的递归算法输出二叉树publicvoidpreOrderTraverse(BinTreeNodep){如果根节点

3、不为空{1、输出根节点的数据域2、把根结点的左指针作为新的根结点指针，递归调用自身输出左子树3、把根结点的右指针作为新的根结点指针，递归调用自身输出右子树}}（1）前序遍历的非递归算法输出二叉树voidPreOrder(BinTreeNodep){若根节点的不为空（循环访问）{输出根节点的值如果右子树不为空{右子树的地址进栈}如果左子树不为空{当前指针指向左子树}否则若栈空则打断循环（右子树地址出栈即当前指针指向右子树）}}4.【高级语言代码】（1）前序遍历方式建立二叉树intis=0;//串s的下标，成员变量,避免回溯。publicBinTreeNodepreOrderCr

4、eate(BinTreeNodep,Strings){charitem=s.charAt(is++);//得到串s的第is个字符if(item!=RefValue){//读入的不是参照值p=newBinTreeNode(item);//递归生成左子树p.leftChild=preOrderCreate(p.leftChild,s);//递归生成右子树p.rightChild=preOrderCreate(p.rightChild,s);//实参是空二叉树,得到返回的子二叉树}else//读入的是参照数p=null;//封闭叶子结点returnp;//返回二叉树p}（2）前序遍

5、历的递归算法输出二叉树publicvoidpreOrderTraverse(BinTreeNodep){if(p!=null){//输出根结点数据域System.out.print(""+p.GetData());//递归输出p的左子树preOrderTraverse(p.leftChild);//递归输出p的右子树preOrderTraverse(p.rightChild);}}（1）前序遍历的非递归算法输出二叉树voidPreOrder(BinTreeNodep){//定义栈（栈的数据类型是二叉树结点指针）cLinkStackS=newcLinkStack();//空栈/

6、/从当前结点开始遍历访问while(p!=null){//访问根结点System.out.print(""+p.GetData());//预留右孩子地址在栈中if(p.rightChild!=null)S.Push(p.rightChild);//若有左孩子，当前指针指向左孩子if(p.leftChild!=null)p=p.leftChild;elseif((p=S.Pop())==null)break;//出栈,意味p指向右孩子结点，//如果栈空，则遍历结束。}//循环，访问当前结点}（四）、程序的输入输出和运行结果截屏输入：abc^^fr^h^^q^^^--------

7、-------------------------------------------------------范文最新推荐------------------------------------------------------电力安全月工作总结[电力安全月工作总结]电力安全月工作总结2011年3月1日至3月31日为我公司的安全生产月，**变电站围绕;夯实基储提高素质、树立标杆、争创一流;的主题，开展了丰富多彩、形式多样的具体行动：通过看板形式宣传安全第一、预防为主的方针；通过48+4的学习机会，进行