11

To pytanie w zasadzie wyjaśnia, że mogą, ale nie pokazuje żadnych przykładów istnienia dwóch różnych drzew z tym samym przejściem w przedsprzedaży.

Wspomniano również, że przechodzenie w kolejności dwóch różnych drzew może być takie samo, chociaż są one strukturalnie różne. Czy jest na to przykład?

trees binary-trees graph-traversal search-trees Sharan Duggirala
źródło

2

Jest to ćwiczenie na poziomie podstawowym. Co próbowałeś i gdzie utknąłeś?

Raphael

1

Nawet jeśli masz zamówienie w przedsprzedaży, oprócz zamówienia w przedsprzedaży, nadal możesz uzyskać różne drzewa. Dlaczego drzewo nie jest wyjątkowo możliwe przy danym przejściu przed i po zamówieniu? Przykład zamówienia można znaleźć w sekcji Od reprezentacji zamówienia do drzewa binarnego . Również powiązane / duplikaty: Które kombinacje sekwencjonowania przed, po i w kolejności są unikalne?

Dukeling

28

Przykłady drzew (obraz) :

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

Jest to przykład, który pasuje do twojego scenariusza: Drzewo Korzeń ma wartość 1, mając lewe dziecko o wartości 2, a jego lewe dziecko ma również lewe dziecko o wartości 3.

Wartość korzenia drzewa B wynosi 1, mając lewe dziecko o wartości 2 i prawe dziecko o wartości 3.

W obu przypadkach przejście w przedsprzedaży wynosi 1-> 2-> 3.

royashcenazi
źródło

11

Jest to właściwie szczególny przypadek ogólnej zasady, że dla dowolnego drzewa jakiegoś rzędu istnieje drzewo liniowe tylko lewych (lub tylko prawych) dzieci, które mają tę samą kolejność.

Dancrumb

5

@Dancrumb Który z kolei jest szczególnym przypadkiem ogólnej zasady, że dla każdego drzewa z N węzłami i dla dowolnego kształtu drzewa (= drzewo bez etykiety) z N węzłami istnieje sposób na oznaczenie tego drugiego, tak aby dzielił przejście z były. Dotyczy to każdego przejścia (wizyta przed / po / w kolejności).

chi

8

$n$ $n$ $1,2,\dots,n$

Oznacza to, że możemy nazwać węzły dowolnej struktury drzewa binarnego, aby wygenerowała taką samą sekwencję zamówienia wstępnego, jak w innym danym drzewie.

To nie zadziała, jeśli będziemy musieli założyć inne właściwości drzewa. Na przykład, jeśli drzewo ma być drzewem wyszukiwania binarnego, a wszystkie klucze są różne, jego kolejność w kolejności jednoznacznie określa drzewo.

Hendrik Jan
źródło

8

Liczenie argumentu

$n$ $n^\text{th}$ $C_n=(2n)!/(n!(n+1)!).$

    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 \dots (n + 2)) .

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

$n!$ $n$ $n!$ $C_n>1$ $n>1.$ $n$

CR Drost
źródło

1

Jeśli chodzi o twoje drugie pytanie, tak, dwa strukturalnie różne drzewa mogą mieć tę samą przemianę. Jednym z takich przykładów jest:

     A:                 B:

     1                  2
    / \                  \
   2   3                  1
                           \
                            3

Wędrówka obu drzew jest taka sama. 2 -> 1 -> 3

Navjot Singh
źródło

Czy przejście przez dwa różne drzewa w przedsprzedaży może być takie samo, mimo że są różne?

Odpowiedzi:

Liczenie argumentu