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

Question

请有人告诉我如何查找二叉树中是否存在值？ 我想查找二叉树的左节点或右节点中存在值吗？

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;
  }
}

Answer 1

我建议使用递归方法，而不是使用 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 和 编辑返回值正确