Супутник

Вказівки

Уявімо, що нам потрібно передати бінарне дерево на супутник, який наближається до Альфи Центавра, а пропускна здатність у нас обмежена. Оскільки в дереві немає повторюваних елементів, його однозначно задають обходи pre-order та in-order.

Напишімо програмне забезпечення для супутника, яке відновить дерево з цих обходів.

Обхід pre-order читає значення поточного вузла перед (звідси «pre») читанням лівого піддерева в порядку pre-order. Після цього в порядку pre-order читається праве піддерево.

Обхід in-order читає ліве піддерево в порядку in-order, потім поточний вузол і, нарешті, праве піддерево в порядку in-order. Тобто по порядку зліва направо.

Наприклад, обхід pre-order цього дерева такий: [a, i, x, f, r]. Обхід in-order цього дерева такий: [i, a, f, x, r].

  a
 / \
i   x
   / \
  f   r

Зауваження: перший елемент обходу pre-order - це завжди корінь.