JS二叉樹非遞歸遍歷

guyan0319 發布于2019-08-21 16:20 / 2742人閱讀

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

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

一個二叉樹的例子

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二叉樹遍歷二叉樹遍歷二叉樹的遍歷

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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實現）

摘要：本文討論二叉樹的遍歷，對節點的訪問通過打印節點的值體現出來。從二叉樹的根節點出發，遍歷可分為三個環節訪問節點打印節點的值遍歷節點的左子樹遍歷節點的右子樹不同環節執行的先后順序產生了不同的遍歷方式。至于二叉樹的非遞歸遍歷，且聽下回分解。相關概念「樹的遍歷」指按照一定規則不重復地訪問樹中所有節點的過程?！冈L問」指針對節點的操作，如打印節點的值，更新節點的值等。本文討論二叉樹的遍歷，...

ethernet 2019-08-21 17:07 評論0 收藏0