javascript - 如何在无序二叉树中搜索节点？

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]);