幅広い最初の検索バイナリ検索ツリーjavascriptの実装

Question

JavaScriptでBSTツリーを実装する次のコードがあります。

function Node(value) { 
    this.left = null; 
    this.right = null; 
    this.value = value; 
} 

function BinarySearchTree() { 
    this.root = null; 
    return; 
} 

BinarySearchTree.prototype.push = function(value) { 

    if (!this.root) { 
    this.root = new Node(value); 
    return; 
    } 

    var currentRoot = this.root; 
    var newNode = new Node(value); 
    while (currentRoot) { 
    if (value < currentRoot.value) { 
     if (!currentRoot.left) { 
     currentRoot.left = newNode; 
     break; 
     } else { 
     currentRoot = currentRoot.left; 
     } 
    } else { 

     if (!currentRoot.right) { 
     currentRoot.right = newNode; 
     break; 
     } else { 
     currentRoot = currentRoot.right; 
     } 

    } 

    } 

} 

var a = new BinarySearchTree(); 
a.push(27); 
a.push(14); 
a.push(35); 
a.push(10); 
a.push(19); 
a.push(31); 
a.push(42); 

私は、木の最初の横断を行うことができる関数を実装しようとしています。これはこれまで私が試したことです。

console.log(a.root.value); 
traverse(a.root); 

//function to traverse 
function traverse(node) { 

    currentNode = node; 
    while (currentNode.left) { 
    displayNodes(currentNode); 
    parent = currentNode; 
    currentNode = currentNode.left; 
    displayNodes(currentNode); 
    if(parent.right!=null){ 
    displayNodes(parent.right); 
    } 
    } 
} 

//function that displays the left and right node of a node 
function displayNodes(node) { 


    if (node.left != null) { 
    console.log(node.left.value); 
    } 
    if (node.right != null) { 
    console.log(node.right.value); 
    } 
} 

大量のデータで拡大縮小できる機能を実装できません。私は、トラバースする再帰的メソッドが良いか、whileループを使用するかどうかはわかりません。どのように機能を実装できますか？この関数が予期しない動作をすることはわかっていますか？私はどんな訂正をするべきですか？

Answer 1

現在、ルートノードから一番左の葉にパスをトラバースしています。

それぞれのコールバックを呼び出す簡単な非再帰的幅優先トラバーサル機能は、次のようにノードが見ることができる横断

：

// Breadth-first traversal: 
function traverse(node, cb) { 
    var current = [node]; 
    while (current.length > 0) { 
    var next = []; 
    for (var node of current) { 
     cb(node); 
     if (node.left) next.push(node.left); 
     if (node.right) next.push(node.right); 
    } 
    current = next; 
    } 
} 

// Example: 
traverse(root, function(node) { 
    console.log(node.value); 
}); 

それが最初にだけ含まれ、すでに発見やトラバースノードcurrentの配列を維持することによって動作しますルートノード。今度は、そのリスト内の各ノードを子ノードと繰り返し置き換えます。上記の関数では、子はnext配列に格納されます。各反復の最後に、currentの現在のレベルのすべてのノードがnextの次の深いレベルのすべての子に置き換えられます。 @DavidKnipe's answerの最初の提案も参照してください。

非再帰的アプローチは、コールスタックサイズの制限を受けないという利点があります。これにより、理論的には、call stack size is limitedが大きいデータ構造を扱うことができます。

Answer 2

O（1）メモリを使用してBFSへの道を探しているなら、それを行うには良い方法はないと思います。 （DFSは別の問題ですが、BFSでなければなりませんか？）

これを行うには2通りの方法があります。 [this.root]という配列から始め、ノードの配列を繰り返し処理し、それらのノードの子の配列を返す関数を書くことができます。その後、その関数を子の配列で呼び出し、空の配列が得られるまでツリーを下って行きます。

メモリが問題であれば、別の方法があります。与えられたレベルでノードの配列を覚えておくのではなく、深さを覚えておき、その都度反復をやり直すことができます。したがって、自然数がnで、ツリー全体を反復処理する関数がありますが、nより深くすることなく、nレベルでのみ実行しようとしています。それ以上のノードがなくなるまで、nのすべての値に対してこの関数を呼び出します。

最後の1つは非常に無駄に思えるかもしれませんが、ツリーの最後のいくつかのレベルにノードのほとんどが含まれていればそれほど悪くないかもしれません。データセットと計算能力によって異なります。