Javascript顯示二叉搜索樹遍歷（遞歸方式）

Question

我試圖控制二叉樹中的每個數據。我的主要問題是我想要以遞歸的方式實現。基本上，我有這樣的代碼至今：

this.levelOrder = function (root) { 
    if (root.data != null) { 
     console.log(root.data); 

     if (root.left != null) { 
      this.levelOrder(root.left); 
     } 

     if (root.right != null) { 
      this.levelOrder(root.right) 
     } 
    } else { 
     return; 
    } 
}; 

輸出爲3 2 1 5 4 7

但應3 2 5 1 4 7。所以基本上我訪問節點的第一個孩子，而不是先打印所有的孩子。任何想法？

Answer 1

假設這樣一棵樹，

 4 
    2  6 
1 3 5 7 

和對象文本

tree = { 
    data: 4, 
    left: { 
     data: 2, 
     left: { 
      data: 1, 
      left: null, 
      right: null 
     }, 
     right: { 
      data: 3, 
      left: null, 
      right: null 
     } 
    }, 
    right: { 
     data: 6, 
     left: { 
      data: 5, 
      left: null, 
      right: null 
     }, 
     right: { 
      data: 7, 
      left: null, 
      right: null 
     } 
    } 
}; 

你可以遞歸調用函數並獲得第一左部分，然後樹的右邊部分。該算法被稱爲depth-first search。

該函數使用單個檢查，因爲這足以先檢查然後繼續前進。

var depthFirth = function (node) { 
 
     if (node) { 
 
      console.log(node.data); 
 
      depthFirth(node.left); 
 
      depthFirth(node.right) 
 
     } 
 
    }, 
 
    tree = { data: 4, left: { data: 2, left: { data: 1, left: null, right: null }, right: { data: 3, left: null, right: null } }, right: { data: 6, left: { data: 5, left: null, right: null }, right: { data: 7, left: null, right: null } } }; 
 

 
depthFirth(tree); // 4 2 1 3 6 5 7

對於breadth-first search，一種算法，該算法首先遍歷樹的每一個級別，你可以如上使用此代碼與同一棵樹上的數據。

var breadthFirst = function (node) { 
 

 
     function bf(queue) { 
 
      var newQueue = []; 
 
      queue.forEach(function (node) { 
 
       console.log(node.data); 
 
       node.left && newQueue.push(node.left); 
 
       node.right && newQueue.push(node.right); 
 
      }); 
 
      newQueue.length && bf(newQueue); 
 
     } 
 

 
     bf([node]); 
 
    }, 
 
    tree = { data: 4, left: { data: 2, left: { data: 1, left: null, right: null }, right: { data: 3, left: null, right: null } }, right: { data: 6, left: { data: 5, left: null, right: null }, right: { data: 7, left: null, right: null } } }; 
 

 
breadthFirst(tree); // 4 2 6 1 3 5 7