Я пытаюсь понять, как создавать объекты в js, используя прототипное наследование, то есть используя Object.create()
вместо ключевого слова new
. Я создал класс узла для создания древовидной структуры данных, используя приведенную ниже реализацию:
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;
}
}
Функция 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)
}
Я инициализирую свое дерево с помощью метода create
в моем объекте node
.
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, но моя функция возвращает true
, почему?
Кроме того, мне любопытно, какой вклад вносит Object.extend
. Похоже, что node.create
может быть просто create: function (value, left=null, right=null) { return Object.assign(Object.create(node), { value, left, right }) }
Автор сообщения в блоге использовал его как вспомогательную функцию для присвоения значений свойствам скопированных объектов. Однако я согласен, что использование Object.assign
- гораздо более простая конструкция.
@MarkMeyer, что было бы лучше с точки зрения производительности? Функция extend
или предложенный вами метод Object.assign
.
Это связано с тем, что функция validateBST предполагает, что корневой параметр будет иметь свойство val, но вы передаете объект узла, который имеет свойство value. Теперь, почему он возвращает true, потому что root.val будет неопределенным и никогда не войдет в единственный оператор if, который возвращает false. И выполнение будет продолжаться до тех пор, пока не достигнет листьев дерева, где root равен нулю и, следовательно, не вернет true. Единственное изменение, которое вам нужно, - это заменить root.val на root.value в функции validateBST ().
Спасибо! Я должен внимательно следить за этими маленькими ошибками.
Это опечатка. У ваших узлов есть свойство
value
, которое вы тестируете наval
:(root.val <= min