JS二叉树非递归遍历

guyan0319 发布于2019-08-21 16:20 / 2801人阅读

摘要：一个二叉树的例子先实现三种遍历的递归算法以作比较。先序遍历递归算法中序遍历递归算法先遍历到最左边的节点，然后输出后序遍历看完上面的递归遍历，下面对比一下非递归的二叉树遍历。终止条件最后树遍历完了自然就结束后序遍历

二叉树的递归遍历很简单就可以实现，二叉树非递归遍历却想不出来？那你可以看看下面的例子。

一个二叉树的例子

var root = {
val: 1,
left: {

</>复制代码 
val: 2,
left: {
  val: 4,
},
right:{
  val:5
}

},
right: {

</>复制代码 
val: 3,
left: {
  val: 6
},
right: {
  val: 7
}

}
}
先实现三种遍历的递归算法以作比较。

先序遍历递归算法

function DLR(root){

</>复制代码 
if(root!=null){
    console.log(root.val);
    DLR(root.left);
    DLR(root.right);
}

}
DLR(root)//1,2,4,5,3,6,7

中序遍历递归算法

function LDR(root){

</>复制代码 
if(root!=null){
    LDR(root.left);//先遍历到最左边的节点，然后输出
    console.log(root.val);
    LDR(root.right);
}

}
LDR(root)//4,2,5,1,6,3,7

后序遍历

function LRD(root){

</>复制代码 
if(node!=null){
    LRD(root.left);
    LRD(root.right);
    console.log(root.val);
}

}
LRD(root)//4,5,2,6,7,3,1

看完上面的递归遍历，下面对比一下非递归的二叉树遍历。你会发现递归真心简单。

非递归前序遍历

function DLR(root){

</>复制代码 
var arr=[],res=[];
if(root!=null){
    arr.push(root);
}
while(arr.length!=0){
    var temp=arr.pop();
    res.push(temp.val);
    //这里先放右边再放左边是因为取出来的顺序相反
    if(temp.right!=null){
        arr.push(temp.right);
    }
    if(temp.left!=null){
        arr.push(temp.left);
    }
}
return res;

}

DLR(root)//1,2,4,5,3,6,7

非递归中序遍历

//先把左边的，全部放进arr再输出，处理右边的。
function LDR(root){

</>复制代码 
var arr=[],res=[];
while(true){
    while(root!=null){
        arr.push(root);
        root=root.left;
    }
    //终止条件：最后树遍历完了自然就结束
    if(arr.length==0){
        break;
    }
    var temp=arr.pop();
    res.push(temp.val);
    root=temp.right;
}
return res;

}
LDR(root)//4,2,5,1,6,3,7

后序遍历

function LRD(root){

</>复制代码 
var arr=[],res=[];
arr.push(root);
while(arr.length!=0){
    var p=arr.pop();
    res.push(p.val);
    if(p.left!=null){
        arr.push(p.left);
    }
    if(p.right!=null){
        arr.push(p.right);
    }
}
return res.reverse();

}
LRD(root)//4,5,2,6,7,3,1

GPU云服务器云服务器非递归二叉树遍历 JS二叉树遍历二叉树遍历二叉树的遍历

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/88416.html

二叉树遍历小结

摘要：对于任一重合元素，保证所在两个局部遍历有序，保证实现整体遍历有序重合元素所在局部局部全部有序，遍历该元素并出栈局部未全部有序，将未有序局部元素全部入栈。二叉树遍历小结声明文章均为本人技术笔记，转载请注明出处： [1] https://segmentfault.com/u/yzwall [2] blog.csdn.net/j_dark/ 0 二叉树遍历概述二叉树遍历：按照既定序，...

vvpale 2019-08-16 10:37 评论0 收藏0
《学习JavaScript数据结构与算法》（第8章）（平衡二叉树代码实现）

摘要：平衡二叉树代码实现根节点插入节点树为空树不为空比较小于往左走大于往右走空树树非空自平衡树插入新节点向左走向左子树拆入新节点，且节点的值小于其左子节点时，应该进行旋转。平衡二叉树JS代码实现 var Tree = function() { var Node = function(value) { this.value = value; this....

isLishude 2019-08-26 10:37 评论0 收藏0
js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)

摘要：树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历，深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树，在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。树的简介栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结...

Yuanf 2019-08-23 11:38 评论0 收藏0
JS递归与二叉树的遍历

摘要：貌似大部分语言中的递归都差不多，之所以在标题加是因为搜了下后感觉网上用来描述这概念的不多，简单地说递归就是函数调用自己的过程。貌似大部分语言中的递归都差不多，之所以在标题加JS是因为搜了下后感觉网上用js来描述这概念的不多，简单地说递归就是函数调用自己的过程。下面的栗子可以很直观地展示递归的执行过程： function rec(x){ if(x!==1){ console....

church 2019-08-21 10:48 评论0 收藏0
二叉树的递归遍历（JS实现）

摘要：本文讨论二叉树的遍历，对节点的访问通过打印节点的值体现出来。从二叉树的根节点出发，遍历可分为三个环节访问节点打印节点的值遍历节点的左子树遍历节点的右子树不同环节执行的先后顺序产生了不同的遍历方式。至于二叉树的非递归遍历，且听下回分解。相关概念「树的遍历」指按照一定规则不重复地访问树中所有节点的过程。「访问」指针对节点的操作，如打印节点的值，更新节点的值等。本文讨论二叉树的遍历，...

ethernet 2019-08-21 17:07 评论0 收藏0