На этой второй неделе я продолжаю изучать некоторые деревья и решать с их помощью некоторые задачи. Вот некоторые из задач, над решением которых я работал.
Итак, первое, что мы собираемся сделать, это создать базовую форму бинарного дерева поиска:
var Node = function(label) { this.label = label; this.leftNode = null; this.rightNode = null; }; Node.prototype.insert = function(node) { if(node.label < this.label) { this.leftNode? this.leftNode.insert(node) : this.leftNode = node; } else if (node.label >= this.label) { this.rightNode? this.rightNode.insert(node) : this.rightNode = node; } };
Испытания
- Дерево: Обход предварительного заказа
Выведите предварительный обход дерева в виде одной строки значений, разделенных пробелами.
Пример ввода:
1 \ 2 \ 5 / \ 3 6 \ 4
Пример вывода:
1 2 5 3 4 6
решение:
Node.prototype.print = function(output) { output = output || [this.label]; if(this.leftNode) { output.push(this.leftNode.label) this.leftNode.show(output); }; if(this.rightNode) { output.push(this.rightNode.label) this.rightNode.show(output); }; return output.join(' '); };
Первое, что мы собираемся сделать, это создать новую переменную, которая будет массивом, в который мы помещаем узлы. В этом случае мы собираемся начать сверху (корень), затем двигаться по левой ветви, а затем по правой. Мы должны проверить, есть ли левый узел; если это так, мы собираемся поместить узел в массив и выполнить некоторую рекурсию, чтобы проверить, есть ли у него leftNode
; мы делаем то же самое с rightNode
2. Дерево: Обход постзаказа
Выведите обход дерева в обратном порядке в виде одной строки значений, разделенных пробелами.
Пример ввода
1
\
2
\
5
/ \
3 6
\
4
Пример вывода
4 3 6 5 2 1
Решение:
Node.prototype.print = function(output) { output = output || []; if(this.leftNode) this.leftNode.print(output); if(this.rightNode) this.rightNode.print(output); output.push(this.label) return output.join(' '); }
В этом случае почтовый порядок работает как левый-правый-корень. Мы собираемся проверить, есть ли у узла leftNode
, если он есть, мы будем использовать некоторую рекурсию, пока не будет leftNode
, если нет leftNode
, мы собираемся проверить, есть ли у него rightNode
, и сделаем некоторую рекурсию, где мы проверяем если у него есть leftNode
или rightNode
, если нет leftNode
или rightNode
, он переместит значение узла в array
.
3. Дерево: обход по порядку
Формат вывода
Выведите неупорядоченный обход дерева в виде одной строки значений, разделенных пробелами.
Пример ввода
1
\
2
\
5
/ \
3 6
\
4
Пример вывода
1 2 3 4 5 6
Решение:
Node.prototype.print = function(output) { output = output || []; if(this.leftNode) this.leftNode.print(output) output.push(this.label) if(this.rightNode) this.rightNode.print(output) return output.join(' '); };
В поперечном порядке путь решения — левый-корень-правый, где мы начинаем с левой ветви, проходим через корень и продолжаем с правой ветвью. Поскольку это двоичное дерево поиска (BST), ответом будет последовательность, поскольку она начинается слева (в этом случае левая сторона всегда будет меньше корня), затем она переходит к корню и, наконец, переходит к право (это всегда будет больше, чем корень), поэтому это последовательность. Итак, первое, что нужно сделать, это проверить, есть ли у узла leftNode
, если он есть, то мы используем рекурсию, чтобы снова проверить, начиная с leftNode
, если его нет, мы проталкиваем значение массива или метку фактический узел, а затем мы проверяем, есть ли у него rightNode
, и используем рекурсию, начинающуюся с него (в случае, если это правда)