JS二叉樹非遞歸遍歷

guyan0319 發(fā)布于2019-08-21 16:20 / 2737人閱讀

摘要：一個二叉樹的例子先實(shí)現(xiàn)三種遍歷的遞歸算法以作比較。先序遍歷遞歸算法中序遍歷遞歸算法先遍歷到最左邊的節(jié)點(diǎn)，然后輸出后序遍歷看完上面的遞歸遍歷，下面對比一下非遞歸的二叉樹遍歷。終止條件最后樹遍歷完了自然就結(jié)束后序遍歷

二叉樹的遞歸遍歷很簡單就可以實(shí)現(xiàn)，二叉樹非遞歸遍歷卻想不出來？那你可以看看下面的例子。

一個二叉樹的例子

var root = {
val: 1,
left: {

val: 2,
left: {
  val: 4,
},
right:{
  val:5
}

},
right: {

val: 3,
left: {
  val: 6
},
right: {
  val: 7
}

}
}
先實(shí)現(xiàn)三種遍歷的遞歸算法以作比較。

先序遍歷遞歸算法

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);//先遍歷到最左邊的節(jié)點(diǎn)，然后輸出
    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

看完上面的遞歸遍歷，下面對比一下非遞歸的二叉樹遍歷。你會發(fā)現(xiàn)遞歸真心簡單。

非遞歸前序遍歷

function DLR(root){

var arr=[],res=[];
if(root!=null){
    arr.push(root);
}
while(arr.length!=0){
    var temp=arr.pop();
    res.push(temp.val);
    //這里先放右邊再放左邊是因?yàn)槿〕鰜淼捻樞蛳喾?    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

非遞歸中序遍歷

//先把左邊的，全部放進(jìn)arr再輸出，處理右邊的。
function LDR(root){

var arr=[],res=[];
while(true){
    while(root!=null){
        arr.push(root);
        root=root.left;
    }
    //終止條件：最后樹遍歷完了自然就結(jié)束
    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