Kombinasi sekuensialisasi pra, pasca, dan berurutan manakah yang unik?

Kami tahu post-order,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

dan pre-order

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

dan resp traversal berurutan. sekuensialisasi.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

Orang dapat dengan mudah melihat bahwa keduanya tidak menggambarkan pohon yang diberikan secara unik, bahkan jika kita mengasumsikan kunci / label berbeda berpasangan.

Kombinasi mana dari ketiganya yang bisa digunakan untuk tujuan itu dan mana yang tidak bisa?

Jawaban positif harus mencakup algoritma (efisien) untuk merekonstruksi pohon dan bukti (ide) mengapa itu benar. Jawaban negatif harus memberikan contoh tandingan, yaitu pohon yang berbeda yang memiliki representasi yang sama.

Pertama, saya akan berasumsi bahwa semua elemen berbeda. Tidak ada jumlah sekuensialisasi yang akan memberi tahu Anda bentuk pohon dengan elemen [3,3,3,3,3]. Dimungkinkan untuk merekonstruksi beberapa pohon dengan elemen duplikat, tentu saja; Saya tidak tahu kondisi apa yang cukup bagus.

Melanjutkan hasil negatif, Anda tidak dapat sepenuhnya membangun kembali pohon biner dari sekuensialisasi pra-pesanan dan pasca-pesanan saja. [1,2]preorder, [2,1]post-order harus ada 1di root, tetapi 2bisa berupa anak kiri atau anak kanan. Jika Anda tidak peduli dengan ambiguitas ini, Anda dapat merekonstruksi pohon dengan algoritma berikut:

• Biarkan menjadi traversal pre-order dan menjadi traversal post-order. Kita harus memiliki , dan ini adalah akar dari pohon.[ y n , ... , y 1 ] x 1 = y $[x_1,\dots,x_n]$$[y_n,\ldots,y_1]$$x_1=y_1$
• y 2 x 2 = y 2 [ x 2 , ... , x n ] [ y n , ... , y 2$x_2$ adalah anak paling kiri dari root, dan adalah anak paling kanan. Jika , simpul root tidak waspada; ulangi dan untuk membuat subtree tunggal.$y_2$$x_2 = y_2$$[x_2,\ldots,x_n]$$[y_n,\ldots,y_2]$
• Kalau tidak, biarkan dan menjadi indeks sedemikian rupa sehingga dan . adalah traversal pre-order dari subtree kiri, dengan subtree kanan, dan juga untuk post-order. Subtree kiri memiliki elemen , dan subtree kanan memiliki elemen . Perulangan satu kali untuk setiap subtree. Omong-omong, metode ini digeneralisasikan ke pohon dengan percabangan yang sewenang-wenang. Dengan percabangan sewenang-wenang, cari tahu sejauh mana subtree kiri dan potong elemen dari kedua daftar, lalu ulangi untuk memotong subtree kedua dari kiri, dan seterusnya.j x 2 = y i y 2 = x j [ x 2 , ... , x j - 1 ] [ x j , ... , x n ] j - 2 = n - i + 1 i - 2 = n - j + 1 j - $i$$j$$x_2 = y_i$$y_2 = x_j$$[x_2,\ldots,x_{j-1}]$$[x_j,\ldots,x_n]$$j-2=n-i+1$$i-2=n-j+1$
  $j-2$

Seperti yang dinyatakan, waktu berjalan adalah dengan kasus terburuk (dalam kasus dengan dua anak, kami mencari setiap daftar lineraly). Anda dapat mengubahnya menjadi jika Anda memproses ulang daftar untuk membangun sebuah struktur peta hingga dari nilai elemen ke posisi dalam daftar input . Juga gunakan array atau peta terbatas untuk beralih dari indeks ke nilai; tetap berpegang pada indeks global, sehingga panggilan rekursif akan menerima seluruh peta dan mengambil rentang sebagai argumen untuk mengetahui apa yang harus ditindaklanjuti.Θ ( n 2 ) O ( $O(n^2)$$\Theta(n^2)$$O(n\,\mathrm{lg}(n))$$n\,\mathrm{lg}(n)$

Dengan traversal pre-order dan traversal in-order , Anda dapat membangun kembali pohon sebagai berikut:$[x_1,\ldots,x_n]$$[z_1,\ldots,z_n]$

• Root adalah kepala traversal pre-order .$x_1$
• Biarkan menjadi indeks sedemikian rupa sehingga . Kemudian adalah traversal berurutan dari anak kiri dan adalah traversal berurutan dari anak kanan. Dengan jumlah elemen, adalah traversal pre-order dari anak kiri dan dari anak kanan. Berulang untuk membangun sub pohon kiri dan kanan.z k = x 1 [ z 1 , ... , z k - 1 ] [ z k + 1 , ... , z n ] [ x 2 , ... , x k ] [ x k + 1 , ... , x n$k$$z_k = x_1$$[z_1,\ldots,z_{k-1}]$$[z_{k+1},\ldots,z_n]$$[x_2,\ldots,x_k]$$[x_{k+1},\ldots,x_n]$

Sekali lagi, algoritma ini adalah seperti yang dinyatakan, dan dapat dilakukan dalam jika daftar diolah menjadi peta terbatas dari nilai ke posisi.O ( $O(n^2)$$O(n\,\mathrm{lg}(n))$

Post-order plus in-order tentu saja simetris.