为什么此 javascript 树实现的 BST 验证函数会失败？

Question

我试图了解如何使用原型继承在 js 中创建对象，即使用 Object.create() 而不是 new 关键字。我创建了一个节点 class 用于使用以下实现制作树数据结构：

Object.prototype.extend = function(extension) {
    var hasOwnProperty = Object.hasOwnProperty;
    var object = Object.create(this);

    for(var property in extension) {
      if (hasOwnProperty.call(extension, property) ||
              typeof object[property] === "undefined")
                    object[property] = extension[property];
    }

    return object

}

const node =  {
    create: function (value, left=null, right=null) {
      return this.extend({
        value: value,
        left: left,
        right: right,
      })
    },
    insertLeft: function(value){
        this.left = this.create(value);
        return this.left;
    },
    insertRight: function(value) {
        this.right = this.create(value);
        return this.right;
    }
}

我从博客 post 收到的 extend 函数解释了原型继承。

然后我创建了一个函数来验证这样实现的 BST：

validateBST = function (root) {
    if (root === null) return true
    return (function validate(root, min=-Infinity, max=Infinity) {
      if (root === null) return true
      if (root.val <= min || root.val >= max) return false
      return validate(root.left, min, root.val) && validate(root.right, root.val, max)
    })(root)
}

我在我的 node 对象中使用 create 方法初始化我的树。

let tree = node.create(5, node.create(1), node.create(4, node.create(3), node.create(6)));

树变量的输出；

{ value: 5,
  left: { value: 1, left: null, right: null },
  right:
   { value: 4,
     left: { value: 3, left: null, right: null },
     right: { value: 6, left: null, right: null } } }

所以这是一个无效的 BST 但我的函数 returns true，为什么？

Answer 1

这是因为 validateBST 函数假设根参数将具有属性 'val'，但您传递的节点对象具有属性 'value' .现在为什么它 returns 为真，因为 root.val 将是未定义的，并且永远不会输入唯一的 'if' 语句 returns 为假。并且，执行将一直持续到它到达树叶，其中根为空，因此 returns 为真。您需要做的唯一更改是在 validateBST() 函数中将 'root.val' 替换为 'root.value'。

为什么此 javascript 树实现的 BST 验证函数会失败？

Why does this BST validation function fail with this javascript tree implementation?

javascript

prototypal-inheritance

binary-search-tree