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