65646


ネットでは、行きがけ順・通りがけ順、通りがけ順・帰りがけ順からBSTを生成する方法はよく見かけますが、帰りがけ順のみ与えられた場合、そこから探索二分木を生成することは可能なのでしょうか？また、その場合どういったアルゴリズムになりますか？


CC BY-SA 4.0
2020-04-15T09:22:13.563
65643
2020-04-15T09:58:11.383
38330
question
アルゴリズム データ構造
帰りがけ順から二分探索木の生成


一意に特定できないため不可能です。たとえば `3, 2, 1` という帰りがけ順に対応する二分木は次のふたつが考えられます。

[code]

      1
      |
      2
      |
      3
    
[/code]

[code]

      1
     / \
    3   2
    
[/code]

一般に、n 個の要素からなる帰りがけ順の配列と n
個ノードがある（ノードに名前がついていない）二分木が与えられると、その帰りがけ順に対応するようにノードに名前をつけていくことができます。普通に深さ優先探索をしつつ、帰るときに名前をつけていけば良いです。つまりあるひとつの帰りがけ順に対応する二分木は少なくとも木の形の数だけ存在します。


CC BY-SA 4.0
2020-04-15T09:58:11.383
65646
2020-04-15T09:58:11.383
19110
65643
answer