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?

— 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?

Liczenie argumentu