バイナリ検索ツリー表示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と呼ばれます。

この関数は、最初にチェックして次に移動するのに十分であるため、単一のチェックを使用します。 breadth-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

、最初のツリーのすべてのレベルが反復されるアルゴリズムは、上記と同様のツリーデータと、このコードを使用することができます。

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