Как создать общий постоянный экземпляр самоопределяемого объекта в javascript?

Question

Я создаю программу для представления двоичного дерева поиска в javascript. Я хочу, чтобы создать общий узел дерева с как ptrs (слева, справа) как null. Это код, который я написал:

var BST = function(data) { 
    if (data === null || data === undefined){ 
     this.data = null; 
     this.left = null; 
     this.right = null; 
    } 

    else{ 
     this.data = data; 
     this.left = new BST(null); 
     this.right = new BST(null); 
    } 
}; 

BST.prototype.insert = function(data) { 
    if (this.data === null){ 
     this.data = data; 
     this.left = new BST(null); 
     this.right = new BST(null); 
    } 
    else if (data < this.data) 
     this.left.insert(data); 
    else if (data > this.data) 
     this.right.insert(data); 
}; 

BST.prototype.inOrder = function(func) { 
    if (this.data !== null) { 
     this.left.inOrder(func); 
     func(this.data); 
     this.right.inOrder(func); 
    } 
}; 

Здесь я хочу, чтобы присвоить все нулевые указатели с нулевым узлом (как определен в состоянии if(data === null || data === undefined)). Но для каждого нулевого узла мне нужно создать новый узел, представляющий одни и те же данные. Есть ли способ назначить общий экземпляр нулевого узла?
Причины я использовать узел нуля, а не только с помощью

else{ 
    this.data = data; 
    this.left = null; 
    this.right = null; 
} 

является то, что при вызове метода inOrder по достижению узла с left or right = null, это дает TypeError, потому что он пытается запустить null.inOrder(func); так, this.left сдвигов до null.
Способом изменения функции inOrder, что приведет к множеству условий вокруг каждого оператора, т. Е. Не очень элегантной реализации.
Я мог бы также определить inOrder вне прототипа объекта и заставить его взять дерево в качестве аргумента, то есть inOder(tree,func), но я не хочу этого делать.

Кроме того, в качестве второго улучшения кода рассмотрите метод insert; в null случае:

if (this.data === null){ 
    this.data = data; 
    this.left = new BST(null); 
    this.right = new BST(null); 
} 

, так как я должен переопределить каждую запись в любом случае, я хочу передать этот узел к новому дереву вообще делать что-то вдоль линий:

if (this.data === null) 
    this = new BST(data); 

Я что это будет менее эффективная реализация первой, но она все еще намного более кратка. Так есть ли способ сделать это?

Answer 1

Но для каждого нулевого узла у меня создать новый узел, представляющий одни и те же данные. Есть ли способ назначить общий экземпляр нулевого узла?

Да, но это нарушит ваш код. Подумайте об этом: что происходит, когда вы вызываете метод insert на этом экземпляре узла? ...

Что касается второй проблемы, вы не можете оптимизировать ее с помощью текущей модели. Нет такой вещи, как замена места на месте (there is in C#).

Я думаю, что ваш текущий код нормально, хотя я лично придерживаться более простой модели, что-то вроде

var BST = function(data) { 
    this.insert(data); 
}; 

BST.prototype.insert = function(data) { 
    if (typeof this.data == 'undefined') { 
     this.data = data; 
    } else if (data < this.data) { 
     if (!this.left) { 
      this.left = new BST(); 
     } 
     this.left.insert(data); 
    } else if (data > this.data) { 
     if (!this.right) { 
      this.right = new BST(); 
     } 
     this.right.insert(data); 
    } 
}; 

BST.prototype.inOrder = function(func) { 
    if (typeof this.data != 'undefined') { 
     this.left && this.left.inOrder(func); 
     func(this.data); 
     this.right && this.right.inOrder(func); 
    } 
}; 

Обратите внимание, что это полностью исключает необходимость в nullNode, так как - эй! - это JavaScript, поэтому почему бы не использовать такие замечательные вещи, как undefined и динамическое расширение объекта.

Answer 2

Да, в этом случае вы можете использовать постоянный экземпляр, потому что все нулевые узлы одинаковы и не имеют разных ссылок (например, свойство «parent»). Чтобы создать такую ​​константу, вам понадобится место для ее хранения; которые могут быть либо (частным) переменными или что-то вроде

BST.emptyleaf = new BST(null); 

И вы можете также использовать одноплодный шаблон:

function BST(data) { 
    if (data === null || data === undefined) { 
     if (BST.emptyleaf) 
      return BST.emptyleaf; // singleton instance if available 
     this.data = null; 
     this.left = null; 
     this.right = null; 
     BST.emptyleaf = this; // else create it for re-use 
    } else { 
     this.data = data; 
     this.left = new BST(null); 
     this.right = new BST(null); 
    } 
}