Как искать узел в не упорядоченном двоичном дереве?

Question

Я строй Некоммерческого заказали бинарное дерево, которое выглядит следующим образом

        1 
           / \ 
           30  2 
           \ /\ 
           31 4 3 
           /\ 
           34 32 
           .... and so on 

Моей реализация была создана следующим образом

function BinarySearchTree() { 
    this._root = null; 
} 

BinarySearchTree.prototype = { 

    //restore constructor 
    constructor: BinarySearchTree, 

    add: function(value,whereToAdd,nodeToAdd){ 
     //create a new item object, place data in 
     var node = { 
       value: value, 
       left: null, 
       right: null 
      }, 

     //used to traverse the structure 
      current; 

     //special case: no items in the tree yet 
     if (this._root === null || whereToAdd === null || whereToAdd === undefined){ 
      this._root = node; 
     } else { 
      current = nodeToAdd; 

      while(true){ 

       //if the new value is less than this node's value, go left 
       if (whereToAdd === "no"){ 

        //if there's no left, then the new node belongs there 
        if (current.left === null){ 
         current.left = node; 
         break; 
        } else { 
         current = current.left; 
        } 

        //if the new value is greater than this node's value, go right 
       } else if (whereToAdd === "yes"){ 

        //if there's no right, then the new node belongs there 
        if (current.right === null){ 
         current.right = node; 
         break; 
        } else { 
         current = current.right; 
        } 

        //if the new value is equal to the current one, just ignore 
       } else { 
        break; 
       } 
      } 
     } 
    }, 

     traverse: function(process){ 

     //helper function 
     function inOrder(node){ 
      if (node){ 

       //traverse the left subtree 
       if (node.left !== null){ 
        inOrder(node.left); 
       } 

       //call the process method on this node 
       process.call(this, node); 

       //traverse the right subtree 
       if (node.right !== null){ 
        inOrder(node.right); 
       } 
      } 
     } 

     //start with the root 
     inOrder(this._root); 
    }, 


    contains: function(value){ 
     var found  = false, 
      current  = this._root; 

     //make sure there's a node to search 
     while(!found && current){ 

      //if the value is less than the current node's, go left 
      if (value < current.value){ 
       current = current.left; 

       //if the value is greater than the current node's, go right 
      } else if (value > current.value){ 
       current = current.right; 

       //values are equal, found it! 
      } else { 
       found = true; 
      } 
     } 

     //only proceed if the node was found 
     return current; 
    }, 

    size: function(){ 
     var length = 0; 

     this.traverse(function(node){ 
      length++; 
     }); 

     return length; 
    }, 

    toArray: function(){ 
     var result = []; 

     this.traverse(function(node){ 
      result.push(node.value); 
     }); 

     return result; 
    }, 

    toString: function(){ 
     return this.toArray().toString(); 
    }, 

}; 

function ArmTheTree(Tree){ 
    Tree.add(1,null,null); 
    Tree.add(30,"no",Tree.contains(1)); 
    Tree.add(31,"yes",Tree.contains(30)); 
    Tree.add(32,"yes",Tree.contains(31)); 
    Tree.add(33,"no",Tree.contains(32)); 
    Tree.add(34,"no",Tree.contains(31)); 
    Tree.add(35,"yes",Tree.contains(34)); 
    Tree.add(36,"yes",Tree.contains(35)); 

    Tree.add(2,"yes",Tree.contains(1)); 
    Tree.add(4,"no",Tree.contains(2)); 
    Tree.add(23,"no",Tree.contains(4)); 
    Tree.add(24,"yes",Tree.contains(23)); 
    Tree.add(25,"no",Tree.contains(23)); 
    Tree.add(26,"yes",Tree.contains(25)); 
    Tree.add(27,"no",Tree.contains(25)); 
    Tree.add(28,"no",Tree.contains(27)); 
    Tree.add(29,"yes",Tree.contains(27)); 

    Tree.add(3,"yes",Tree.contains(2)); 
    Tree.add(5,"yes",Tree.contains(3)); 

    Tree.add(6,"no",Tree.contains(3)); 
    Tree.add(7,"yes",Tree.contains(6)); 
    Tree.add(8,"no",Tree.contains(6)); 
    Tree.add(9,"yes",Tree.contains(8)); 

    Tree.add(17,"no",Tree.contains(9)); 
    Tree.add(19,"yes",Tree.contains(17)); 
    Tree.add(20,"no",Tree.contains(17)); 
    Tree.add(21,"yes",Tree.contains(20)); 


    Tree.add(10,"yes",Tree.contains(9)); 
    Tree.add(11,"yes",Tree.contains(10)); 

    Tree.add(12,"no",Tree.contains(10)); 
    Tree.add(15,"yes",Tree.contains(12)); 
    Tree.add(13,"no",Tree.contains(12)); 
    Tree.add(14,"yes",Tree.contains(13)); 
    Tree.add(16,"no",Tree.contains(13)); 

}; 
Tree = new BinarySearchTree(); 
ArmTheTree(Tree); 



}); 

Как я могу использовать реализацию поперечной функции для поиска узел внутри двоичного дерева? Мое намерение - использовать это дерево для истинной или ложной игры.

Answer 1

Вы можете использовать рекурсивный подход с вспомогательной функцией _contains, который ищет значения в узле в дереве и его поддеревьев:

..., 

_contains: function(node, value) { 
    if (node === null) return null; 
    if (node.value == value) return node; 

    // search in left subtree 
    var n = this._contains(node.left, value); 
    if (n) return n; 

    // search in right subtree 
    return this._contains(node.right, value); 
}, 

contains: function(value) { 
    return this._contains(this._root, value); 
}, 

... 

Функция возвращает null, если узел не найден.

Если вы заработаете функцию add, верните только что добавленный узел, вы можете сэкономить много деревьев при строительстве дерева, и вы, вероятно, обойдетесь без функции contains. Вместо того, чтобы:

Tree.add(1, null, null); 
Tree.add(30, "no", Tree.contains(1)); 
Tree.add(31, "yes", Tree.contains(30)); 

вы получите:

var n = {}; 

n[1] = Tree.add(1, null, null); 
n[30] = Tree.add(30, "no", n[1]); 
n[31] = Tree.add(31, "yes", n[30]);