基本的に、二分木ではないツリーは、preorder（そこからぶら下がっているサブツリーの前に内部ノードを列挙する）とpostorder（そこからぶら下がっているサブツリーの後に内部ノードを列挙する）の2つの順序でトラバースできます。あなたの問題では、「ボトムアップ」はポストオーダーであり、「トップダウン」はプレオーダーであると思います。
さらに、すべてのオブジェクトを互いに分離できる、つまり、それらが異なる値またはポインターを持っていると仮定しましょう。すべてのオブジェクトが同一である場合、つまりすべてが同一の状態である場合、それらは同一に見えるため、トラバーサルリストからツリーの形状を推測することはできません。
ここで、ツリーTがあり、プレオーダーおよびポストオーダートラバーサルによって生成されたノードリストがある場合、そのツリーのROOTは、プレオーダーリストの最初のノードとポストオーダーリストの最後のノードになります。これにより、次の再構築方法が得られます。
プレオーダーとポストオーダーのトラバースノードリストの2つのリストがあります。これらをR（pRe）およびO（pOst）と呼びます。
- Rの最初の要素はルートノードです。Rから削除します
- Oから最後の要素を削除し、それが同じルートノードであることを確認します（そうである必要があります）
- 次に、Rの最初の要素を確認します。これは、左端のサブツリーのルートです。
- Oから同じノードを見つけます。Oのk番目のノードだとしましょう
- これで、左端のサブツリーにk個のノードがあります。リストRとOの両方から最初のkノードを取得し、このアルゴリズムを再帰的に実行して、左端のサブツリーを再構築します。
- RとOの残りの部分を続行し、これを繰り返して、ルートノードの残りのサブツリーを再構築します。
擬似コード-ツリーを返す再帰的プロシージャ。入力：2つのトラバーサルリストr =プレオーダー、o=ポストオーダー
def mktree(r, o):
l = len(r)
assert l == len(o)
root = r[0]
assert root == o[l - 1]
if l == 1:
return mknode(root)
else:
myroot = mknode(root)
r = r[1:l] # sublist that excludes first element
o = o[0:l-1] # sublist that excludes last element
while len(r) > 0: # iterate and construct subtrees
first = r[0]
lim = -1
for i in 0..l - 1:
if o[i] == first:
lim = i + 1
break
assert lim != -1
myroot.add_rightmost_child(mktree(r[0:lim], o[0:lim])
r = r[lim:len(r)] # sublist from lim until end of list
o = o[lim:len(o)] # sublist from lim until end of list
return myroot
仕組みの例を次に示します。
元の木：
1
/ | \
2 3 4
/ / \
5 6 7
プレオーダートラバーサル（「トップダウン深さ優先」）：1 2 5 3 4 6 7
注文後のトラバーサル（「ボトムアップ」）：5 2 3 6 7 4 1
アルゴリズムの実行：
mktree(1253467, 5236741)
myroot = 1
r = 253467, o = 523674
loc = 1 (location of '2' in o)
mktree(25, 52)
myroot = 2
mktree(5, 5) -> returns singleton tree 5
list exhausted -> returns tree 2[5] (5 only child of 2)
add 2[5] to myroot as right child, tree at myroot 1[2[5]]
r = 3467, o = 3674 (stripped away "25" that was processed)
loc = 0 (location of '3' in o)
mktree(3, 3) returns singleton tree 3
add 3 to myroot as right child, tree at myroot 1[2[5], 3]
r = 467, o = 674 (stripped away "3" that was processed)
loc = 2 (location of '4' in o)
mktree(467, 674)
myroot = 4
r = 67, o = 67
(recursive calls return first singleton 6, then 7)
returns tree 4[6,7]
add 4[6,7] to myroot as right child, tree at myroot 1[2[5],3,4[6,7]]
list exhausted, return tree
その結果、元の木が再建されました。
参考までに、擬似コードでのプレオーダーおよびポストオーダートラバーサルの定義は次のとおりです。
def preorder(t):
l = [root_node(t)] # BEFORE recursion = PREorder
for c in t.children(): # in left to right order
l.append(preorder(c))
return l
def postorder(t):
l = []
for c in t.children(): # in left to right order
l.append(postorder(c))
l.append(root_node(t)) # AFTER recursion = POSTorder
return l