如何查找值是否存在于二叉树中

how to find value is present in binary tree or not

本文关键字：存在 是否 二叉树 何查找 查找      更新时间：2023-09-26

请告诉我如何查找二进制树中是否存在值？我想找到值是存在于二叉树的左节点还是右节点？

BinarySearchTree.prototype = {
  //more code
  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 found;
  }
}

我建议使用递归方法，而不是使用while循环。

function searchBST(rootNode, val) {
    if (rootNode.key === null)
        return null;
    var nodeKey = parseInt(rootNode.val);
    if (val < nodeKey) {
        return searchBST(rootNode.left, val);
    } else if (val > nodeKey) {
        return searchBST(rootNode.right, val);
    } else {
        return rootNode.value;
    }
}

此函数将返回具有搜索值的节点，如果您只想检查是否存在具有某个值的节点时，只需使用false和true 编辑返回值即可

如果在树中找到值，则可以离开函数。

function Node(value) {
    this.value = value;
    // this.left = null;
    // this.right = null;
}
function BinarySearchTree() {
    this._root = null;
}
BinarySearchTree.prototype = {
    insert: function (value) {
        var node = this,
            side = '_root';
        while (node[side]) {
            node = node[side];
            if (value === node.value) {
                return;
            }
            side = value < node.value ? 'left' : 'right';
        }
        node[side] = new Node(value);
    },
    contains: function (value) {
        var current = this._root
        while (current) {
            document.write('value: ' + current.value + '<br>');
            if (value === current.value) {
                return true; // leave the function
            }
            current = value < current.value ? current.left : current.right;
        }
        return false;
    },
};
var tree = new BinarySearchTree(),
    i;
for (i = 0; i < 10; i++) {
    tree.insert(Math.floor(Math.random() * 1000));
}
document.write(tree.contains(42) + '<br>');
tree.insert(42);
document.write(tree.contains(42) + '<br>');
document.write('<pre>' + JSON.stringify(tree, 0, 4) + '</pre>');

相关文章：