11

Эта вопрос в значительной степени объясняет, что они могут, но не показывает никаких примеров наличия двух разных деревьев с одним и тем же обходом предварительного заказа.

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

trees binary-trees graph-traversal search-trees Шаран Дуггирала
источник

2

Это упражнение начального уровня. Что вы пробовали и где застряли?

Рафаэль

1

Даже если у вас есть почтовый заказ, в дополнение к предварительному заказу, обходу, вы все равно можете получить разные деревья. Почему дерево не является уникально возможным при заданном обходе предварительного и последующего порядка? Вы можете найти пример по порядку в разделе От представления по порядку к бинарному дереву . Также связанный / дубликат: Какие комбинации секвенизации до, после и по порядку уникальны?

Dukeling

28

Примеры дерева (изображение) :

     A:                 B:
     ‾‾                 ‾‾
     1                  1
    /                  / \
   2                  2   3
  /  
 3

Это пример, который соответствует вашему сценарию. Значение корня дерева A равно 1, у него есть левый потомок со значением 2, а у его левого потомка также есть левый потомок со значением 3.

Значение корня дерева B равно 1, левый дочерний элемент со значением 2 и правый дочерний элемент со значением 3.

В обоих случаях обход Предзаказа составляет 1-> 2-> 3.

royashcenazi
источник

11

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

Данкрамб

5

@Dancrumb, который, в свою очередь, является частным случаем общего правила, согласно которому для любого дерева с N узлами и для любой формы дерева (= немеченого дерева) с N узлами существует способ пометить последний так, чтобы он разделял обход с бывший. Это относится к любому обходу (посещение до / после / по порядку).

чи

8

Предположим, вы рассматриваете деревья из $n$ узлов. Теперь возьмите любое двоичное дерево с $n$ узлами и назовите узлы в соответствии с их нумерацией предварительного заказа. Тогда ясно, что последовательность предварительного заказа дерева будет $1,2,\dots,n$

Это означает, что мы можем назвать узлы любой двоичной древовидной структуры так, чтобы она генерировала ту же последовательность предварительного заказа, что и последовательность другого заданного дерева.

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

Хендрик Ян
источник

8

Подсчет аргументов

Число немеченых двоичных деревьев в $n$ узлах равно $n^\text{th}$ $C_n=(2n)!/(n!(n+1)!).$ Например, есть 5 бинарных деревьев из 3 узлов,

    o         o         o         o         o
   /         /         / \         \         \
  o         o         o   o         o         o      .
 /           \                     /           \
o             o                   o             o

$n!$

\frac{(2 N)!}{(N + 1)!} знак равно 2 N \cdot (2 N - 1) \cdot ... (N + 2),

$\frac{(2n)!}{(n+1)!} = 2n\cdot(2n-1)\cdot \dots (n+2).$

В отличие от них только $n!$ обходы дерева из $n$ узлов. Поскольку мы просто умножили первое на $n!$ $C_n>1$ $n>1.$ $n$

ЧР Дрост
источник

1

Что касается вашего второго вопроса, да, два структурно разных дерева могут иметь одинаковый обход по порядку. Один из таких примеров:

     A:                 B:

     1                  2
    / \                  \
   2   3                  1
                           \
                            3

Обход обоих деревьев одинаков. 2 -> 1 -> 3

Навьот Сингх
источник

Может ли предварительный заказ двух разных деревьев быть одинаковыми, даже если они разные?

Ответы:

Подсчет аргументов