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

Итак, первое, что мы собираемся сделать, это создать базовую форму бинарного дерева поиска:

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. Дерево: Обход предварительного заказа

Выведите предварительный обход дерева в виде одной строки значений, разделенных пробелами.

Пример ввода:

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, и используем рекурсию, начинающуюся с него (в случае, если это правда)