君，已阅读到文档的结尾了呢~~
二叉树的中序、前序、后序的递归及非递归遍历算法,层次 #IFNDEF TREE_H#DEFINE TREE_H#INCLUDE &STDIO.H&#INCLUDE &MALLOC.H&#INCLUDE &STACK&#INCLUDE &QUEUE&#INCLU...
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
二叉树的中序、前序、后序的递归及非递归遍历算法,层次
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口（Binary tree）是每个节点最多有两个子树的。二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有个结点；深度为k的二叉树至多共有个结点；对任何一棵二叉树T，如果其终端结点数为，度为2的节点数为，则。与树不同，树的节点个数至少为1，而二叉树的节点个数可以为0；树中节点的最大度数没有限制，而二叉树节点的最大度数为2；树的节点无左、右之分，而二叉树的结点有左、右之分。1.1前(先)序、中序、后序遍历遍历二叉树：L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则先(根)序遍历二叉树的顺序是DLR，中(根)序遍历二叉树的顺序是LDR，后(根)序遍历二叉树的顺序是。还有按层遍历二叉树。这些方法的时间复杂度都是O(n)，n为结点个数。用二叉树表示上述表达式：a+b*(c-d)-e/f先序遍历的序列是：-+a*b-cd/ef中序遍历的序列是：a+b*c-d-e/f后序遍历的序列是：abcd-*+ef/-1.２二叉树的存储1.２.1顺序存储二叉树可以用数组或线性表来存储，而且如果这是满二叉树，这种方法不会浪费空间。用这种紧凑排列，如果一个结点的索引为i，它的子结点能在索引2i+1和2i+2找到，并且它的父节点（如果有）能在索引floor((i-1)/2)找到（假设根节点的索引为0）。1.２.２二叉链表存储二叉树通常用树结点结构来存储。有时也包含指向唯一的父节点的指针。如果一个结点的子结点个数小于2，一些子结点指针可能为空值，或者为特殊的哨兵结点。 使用链表能避免顺序储存浪费空间的问题，算法和结构相对简单，但使用二叉链表，由于缺乏父链的指引，在找回父节点时需要重新扫描树得知父节点的节点地址。1.２.３三叉链表存储改进于二叉链表，增加父节点的指引，能更好地实现节点间的访问，不过算法相对复杂。 当二叉树用三叉链表表示时，有N个结点，就会有N+2个空指针。1.３将n叉树转换为二叉树一般有序树和二叉树之间有一一映射关系，能进行相互转换。n叉树转换为二叉树的方法：二叉树中结点x的左子结点为n叉树中结点x的左子结点；二叉树中结点x的右子结点为n叉树中结点x的第一个右边的同级结点y。例如，在左边的树中，A有6个子结点{B,C,D,E,F,G}。它能被转换成右边的二叉树。将一棵树转换为二叉树的方法：1、在兄弟之间加一连接；2、对每个结点，除了其左孩子外，去除其与其余孩子之间的联系；3、以树的根结点为轴心，将整树顺时针转45度。1.4二叉树遍历（）节点描述：privateclassNode{// 左节点privateNode leftC// 右节点privateNode rightC// 节点对应的值privateintpublicNode(intdata){this.leftChild =null;this.rightChild =null;this.data = } }1.4.1前中后续遍历（递归）递归遍历：/* *前序遍历二叉树 * */publicvoidpreOrder(){if(node !=null){ System.out.print(node.data); preOrder(node.leftChild); preOrder(node.rightChild); } }/* *中序遍历二叉树 * */publicvoidinOrder(Node node){if(node !=null){ inOrder(node.leftChild); System.out.print(node.data); inOrder(node.rightChild); } }/* *后序遍历二叉树 * */publicvoidpostOrder(){if(node !=null){ postOrder(node.leftChild); postOrder(node.rightChild); System.out.print(node.data); }1.4.2前中后续遍历（非递归）/** * * 【前序】 * 利用栈实现循环先序遍历二叉树 * 这种实现类似于图的深度优先遍历（DFS） * 维护一个栈，将根节点入栈，然后只要栈不为空，出栈并访问，接着依次将访问节点的右节点、左节点入栈。 * 这种方式应该是对先序遍历的一种特殊实现（看上去简单明了），但是不具备很好的扩展性，在中序和后序方式中不适用 */publicvoidpreOrder(){if(root==null)return; Stack&Node& s=Stack&Node&; s.push(root);while(!s.isEmpty){ Node =s. System.out.println(temp.value);if(temp.right!=null) s.push(temp.right);if(temp.left!=null) s.push(temp.left); } }/** * * 【中序】 * 利用栈模拟递归过程实现循环中序遍历二叉树 * 思想和上面的preOrderStack_2相同，只是访问的时间是在左子树都处理完直到null的时候出栈并访问。 */publicstaticvoidinOrderStack(Node root){if(root==null)return; Stack&Node& s=newStack&Node&;while(root!=null||!s.isEmpty){while(root!=null){ s.push(root);//先访问再入栈root=root. } root=s. System.out.println(root.value); root=root.//如果是null，出栈并处理右子树} }/** * * 【后续】 * 后序遍历不同于先序和中序，它是要先处理完左右子树，然后再处理根(回溯)，所以需要一个记录哪些节点已经被访问的结构(可以在里面加一个标记)，这里可以用map实现 */publicstaticvoidpostOrderStack(Node root){if(root==null)return; Stack&Node& s=new&Node&; Map&Node,Boolean& map=new&Node,Boolean&; s.push(root);while(!s.isEmpty){ Node temp=s.if(temp.left!=null&&!map.containsKey(temp.left)){ temp=temp.while(temp!=null){if(map.containsKey(temp))break;elses.push(temp); temp=temp. }continue; }if(temp.right!=null&&!map.containsKey(temp.right)){ s.push(temp.right);continue; } Node t=s. map.put(t,true); System.out.println(t.value); } }1.4.3广度优先遍历（层次遍历）/** *@root 树根节点 * 层序遍历，用队列实现，先将根节点入队列，只要队列不为空，然后出队列，并访问，接着讲访问节点的左右子树依次入队列 */publicvoidlevelTravel(){if(root==null)return; Queue&Node& q=LinkedList&Node&; q.add(root);while(!q.isEmpty){ Node temp = q. System.out.println(temp.value);if(temp.left!=null)q.add(temp.left);if(temp.right!=null)q.add(.right); } }将为您减少类似内容我要收藏222个赞不感兴趣分享到分享到：相关文章还可以输入140字热门频道10.9万人订阅174.2万人订阅1296万人订阅16.7万人订阅20.3万人订阅你还可用第三方账号来登录请输入你注册的电子邮件地址绑定密保手机*您可用使用此密保手机找回密码及登录*请勿随意泄露手机号，以防被不法分子利用，骗取帐号信息手机号码发送验证码确定电子邮件请输入您的意见和建议请您输入正确的邮箱地址，以便我们和您联系，帮您解决问题。扫描下载手机客户端热门搜词20:14 提问
二叉树后序遍历非递归算法 运行有问题！ 求解答~ 谢啦
二叉树后序遍历非递归算法(有问题)
a(flag=1)，只遍历完左子树，右子树尚未遍历，则该结点不出栈，利用栈顶结点找到它的右子树，准备遍历
b(flag=2)，遍历完右子树，将该结点出栈，并访问它
struct BiNode{
BiNode *lchild,*
struct Element{
void postOrder2(BiNode *bn){
int top=-1;
Element s[20];///假定不会发生上溢
while(bn!=NULL||top!=-1){///两个条件都不成立才退出循环
while(bn!=NULL){
s[top].bt=
s[top].flag=1;///结点连同标志位一起入栈
while(top!=-1&&s[top].flag==2){
bn=s[top--].
if(top!=-1){
s[top].flag=2;
bn=s[top].bt-&
按赞数排序
运行后神秘问题
你把错误贴出来啊
142关注|484收录
1082关注|145收录
412关注|937收录
其他相似问题
相关参考资料1816人阅读
数据结构/算法（33）
递归和非递归俩种方法实现二叉树的前序遍历。
对二叉树的递归遍历我相信大家只要学了数据结构后应当都很容易就能写出，这里主要是讨论二叉树的非递归写法。按照二叉树前序遍历的定义，无论是访问整棵树还是其子树，均应该遵循先访问根结点，然后访问根结点的左子树，最后访问根结点的右子树的。在整个二叉树前序遍历的过程中，程序始终要做的工作分成俩个部分：（借用辅助栈来实现）
1. 当前正在处理的树（子树）
2. 保存在栈中等待处理的部分。
当栈中元素位于栈顶即将出栈时，意味着其根结点和左子树已访问完成，出栈后，进入其右子树进行访问。
代码如下：
/*-------------------------------
Copyright by yuucyf.
--------------------------------*/
#include &stdafx.h&
#include &assert.h&
#include &iostream&
#include &stack&
typedef struct tagBSTreeNode
tagBSTreeNode *psL
tagBSTreeNode *psR
tagBSTreeNode()
psLeft = psRight = 0;
nValue = 0;
}S_BSTreeN
void AddBSTreeNode(S_BSTreeNode *&psRoot, int nValue)
if (NULL == psRoot)
psRoot = new S_BSTreeN
assert(psRoot);
psRoot-&nValue = nV
if (psRoot-&nValue & nValue)
AddBSTreeNode(psRoot-&psRight, nValue);
AddBSTreeNode(psRoot-&psLeft, nValue);
void PreOrder_Recursion(const S_BSTreeNode *psRoot)
if (NULL == psRoot)
cout && psRoot-&nValue && & &;
PreOrder_Recursion(psRoot-&psLeft);
PreOrder_Recursion(psRoot-&psRight);
void PreOrder_Not_Recursion(S_BSTreeNode *psRoot)
stack&S_BSTreeNode *& stackN
S_BSTreeNode *psCurNode = psR
while ((!stackNode.empty()) || (psCurNode != NULL))
if (psCurNode != NULL)
while (psCurNode)
cout && psCurNode-&nValue && & &;
stackNode.push(psCurNode);
psCurNode = psCurNode-&psL
psCurNode = stackNode.top();
stackNode.pop();
psCurNode = psCurNode-&psR
int _tmain(int argc, _TCHAR* argv[])
S_BSTreeNode *psRoot = NULL;
AddBSTreeNode(psRoot, 8);
AddBSTreeNode(psRoot, 6);
AddBSTreeNode(psRoot, 4);
AddBSTreeNode(psRoot, 5);
AddBSTreeNode(psRoot, 12);
AddBSTreeNode(psRoot, 10);
AddBSTreeNode(psRoot, 15);
AddBSTreeNode(psRoot, 13);
AddBSTreeNode(psRoot, 14);
cout && &递归遍历的结果为:& &&
PreOrder_Recursion(psRoot);
cout && &非递归遍历的结果为:& &&
PreOrder_Not_Recursion(psRoot);
//Don't forget to free memory.
如果要求是非递归后序遍历呢？非递归后序稍微有点复杂。按照二叉树后序遍历的定义，无论是访问整棵树还是起子树，均应该遵循先访问根结点左子树，然后访问根结点的右子树，最后访问根结点。值得注意的是，当一个元素位于栈顶即将处理的是，其左子树的访问一定完成，如果其右子树不为空，接下来应该进入其右子树访问，但此时该栈顶元素时不能出栈的，因为它作为根结点，其本身的值还未被访问。只有等到其右子树也访问完成后，该栈顶元素才能出栈，并输出它的值。&因此，在二叉树后序遍历的算法中，必须每个节点维护一个类型为int的整数nTag，
其每个元素(节点)的nTag取值为0 或1，用于标识栈中每个元素的状态。
1. 当一个元素刚进栈时，其对应的nTag 值置为0；
2. 当它位于栈顶即将被处理时，其nTag 值为0.意味着应该访问其右子树，于是将右子树作为当前处理的对象，此时该栈顶元素仍应该保留在栈中，并将其对应的nTag 值改为1.
3. 当其右子树访问完成后，该元素又一次位于栈顶，而此时其nTag 值为1，意味着其右子树已访问完成，接下来，应该直接访问的就是它，将其出栈。
代码如下：
void PostOrder_Not_Recursion(S_BSTreeNode *psRoot)
stack&S_BSTreeNode *& stackN
S_BSTreeNode *psCurNode = psR
while ((!stackNode.empty()) || (psCurNode != NULL))
if (psCurNode != NULL)
while (psCurNode /*&& psCurNode-&nTag != 1*/)
stackNode.push(psCurNode);
psCurNode = psCurNode-&psL
psCurNode = stackNode.top();
while ((!stackNode.empty()) && (psCurNode-&nTag == 1))
cout && psCurNode-&nValue && & &;
stackNode.pop();
if (stackNode.empty())
psCurNode = NULL;
psCurNode = stackNode.top();
if (!stackNode.empty())
psCurNode-&nTag = 1;
psCurNode = psCurNode-&psR
psCurNode = NULL;
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：202841次
积分：2560
积分：2560
排名：第9841名
原创：50篇
转载：24篇
评论：80条
(2)(1)(2)(1)(1)(12)(2)(5)(14)(6)(8)(10)(1)(2)(2)(4)(1)给出一个二叉树的前序序列和中序序列，写出其生成二叉树的递归和非递归算法
[问题点数：40分]
给出一个二叉树的前序序列和中序序列，写出其生成二叉树的递归和非递归算法
[问题点数：40分]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2013年 总版技术专家分年内排行榜第三
2012年 总版技术专家分年内排行榜第七
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。}