AOJ プログラミング入門 (ALDS1) - #7 木構造
AIZU ONLINE JUDGE > アルゴリズムとデータ構造入門 > #7 木構造
節点を表す Node クラスを宣言し、二分木を tree = defaultdict(Node) とした。
defaultdict を用いれば、どのような節点番号にも対応できる。
そのままでは順番が保証されないが、set(tree) で tree.keys() の昇順を取得可能。
- 入力に基づいて二分木として最低限の構築を行う
- 二分木を一巡して、根の場所を探す（＋追加情報を得る）
- 根の場所を引数として再帰関数を適用し、追加情報を得る
- 結果を出力する
ALDS1_7_A: Rooted Trees
「らせん本」に習って左子右兄弟表現（left-child, right-sibling representation）を用いる。多分木を二分木として扱うことができるのが強みらしい。
書籍の内容のままで再帰関数を Python のコードに置き換えると、再帰の回数が多すぎるためにエラーが発生することに注意。sys.setrecursionlimit() で再帰の回数の上限を増やしてもいいけど、root を探すついでに node.children を作成しておくことで、set_depth() の再帰の回数を減らすことができる。
Rooted Trees}
from collections import defaultdict
NIL = -1
class Node():
def __init__(self, parent=NIL, left=NIL, right=NIL):
self.parent = parent
self.left = left
self.right = right
def set_depth(u, d):
tree[u].depth = d
for ch in tree[u].children:
set_depth(ch, d + 1)
tree = defaultdict(Node)
for _ in range(int(input())):
id, k, *C = map(int, input().split())
if tree[id].parent == NIL: tree[id].parent = NIL
for j in range(k):
tree[C[j]].parent = id
if j == 0:
tree[id].left = C[j]
else:
tree[C[j - 1]].right = C[j]
for u, node in tree.items():
if node.parent == NIL: root = u
children = []
ch = node.left
while ch != NIL:
children.append(ch)
ch = tree[ch].right
node.children = children
set_depth(root, 0)
for u in set(tree):
node = tree[u]
kind = "root" if node.parent == NIL else "leaf" if node.left == NIL else "internal node"
print(f'node {u}: parent = {node.parent}, depth = {node.depth}, {kind}, {node.children}')
ALDS1_7_B: Binary Trees
root を探すついでに node.sibling と node.degree を作成しておく（別々にループを回した方が正統派な気もするけど）。
Binary Trees}
from collections import defaultdict
NIL = -1
class Node():
def __init__(self, parent=NIL, left=NIL, right=NIL):
self.parent = parent
self.left = left
self.right = right
def set_depth(u, d):
tree[u].depth = d
tree[u].left == NIL or set_depth(tree[u].left, d + 1)
tree[u].right == NIL or set_depth(tree[u].right, d + 1)
def set_height(u):
h1 = 0 if tree[u].left == NIL else set_height(tree[u].left) + 1
h2 = 0 if tree[u].right == NIL else set_height(tree[u].right) + 1
tree[u].height = max(h1, h2)
return tree[u].height
tree = defaultdict(Node)
for _ in range(int(input())):
id, left, right = map(int, input().split())
tree[id].left = left
tree[id].right = right
if left != NIL: tree[left].parent = id
if right != NIL: tree[right].parent = id
for u, node in tree.items():
node.sibling = NIL
if node.parent == NIL: root = u
elif tree[node.parent].left != NIL and tree[node.parent].right != NIL:
node.sibling = tree[node.parent].right if u == tree[node.parent].left else tree[node.parent].left
node.degree = (node.left != NIL) + (node.right != NIL)
set_depth(root, 0)
set_height(root)
for u in set(tree):
node = tree[u]
kind = "root" if node.parent == NIL else "leaf" if node.degree == 0 else "internal node"
print(f'node {u}: parent = {node.parent}, sibling = {node.sibling}, degree = {node.degree}, depth = {node.depth}, height = {node.height}, {kind}')
ALDS1_7_C: Tree Walk
先行順巡回（preorder tree walk）：「根節点 -> 左部分木 -> 右部分木」の順
中間順巡回（inorder tree walk）：「左部分木 -> 根節点 -> 右部分木」の順
後行順巡回（postorder tree walk）：「左部分木 -> 右部分木 -> 根節点」の順
の定義通りに再帰関数を定義する。
Tree Walk}
from collections import defaultdict
NIL = -1
class Node():
def __init__(self, parent=NIL, left=NIL, right=NIL):
self.parent = parent
self.left = left
self.right = right
def debug(tree):
def dfs(u, preorder, inorder, postorder):
preorder.append(u)
tree[u].left == NIL or dfs(tree[u].left, preorder, inorder, postorder)
inorder.append(u)
tree[u].right == NIL or dfs(tree[u].right, preorder, inorder, postorder)
postorder.append(u)
return preorder, inorder, postorder
for u, node in tree.items():
if node.parent == NIL: root = u
preorder, inorder, postorder = dfs(root, [], [], [])
print('Preorder')
print('', *preorder)
print('Inorder')
print('', *inorder)
print('Postorder')
print('', *postorder)
tree = defaultdict(Node)
for _ in range(int(input())):
id, left, right = map(int, input().split())
tree[id].left = left
tree[id].right = right
if left != NIL: tree[left].parent = id
if right != NIL: tree[right].parent = id
debug(tree)
ALDS1_7_D: Reconstruction of a Tree
以下、二分木（の特定の範囲）を先行順巡回（preorder tree walk）と中間順巡回（inorder tree walk）で記述したものを pre_list, in_list と表記する。
先行順巡回では「根節点 -> 左部分木 -> 右部分木」の順で巡る。
中間順巡回では「左部分木 -> 根節点-> 右部分木」の順で巡る。
根節点の値は root = pre_list[0] で取得できる。
中間順巡回における根節点の位置 mid = in_list.index(root) を用いると、
中間順巡回における左部分木は in_list[:mid]
中間順巡回における右部分木は in_list[mid + 1:]
左部分木の要素数が mid に等しいことに注意すると、
先行順巡回における左部分木は pre_list[1:mid + 1]
先行順巡回における右部分木は pre_list[mid + 1:]
Reconstruction of a Tree}
from collections import defaultdict
NIL = -1
class Node:
def __init__(self, parent=NIL, left=NIL, right=NIL):
self.parent = parent
self.left = left
self.right = right
def func(pre_list, in_list):
if pre_list == []: return
root = pre_list[0]
mid = in_list.index(root)
if tree[root].parent == NIL: tree[root].parent = NIL
if mid > 0:
tree[root].left = pre_list[1:mid + 1][0]
tree[pre_list[1:mid + 1][0]].parent = root
if mid + 1 < len(pre_list):
tree[root].right = pre_list[mid + 1:][0]
tree[pre_list[mid + 1:][0]].parent = root
func(pre_list[1:mid + 1], in_list[:mid])
func(pre_list[mid + 1:], in_list[mid + 1:])
def debug(tree):
def dfs(u, preorder, inorder, postorder):
preorder.append(u)
tree[u].left == NIL or dfs(tree[u].left, preorder, inorder, postorder)
inorder.append(u)
tree[u].right == NIL or dfs(tree[u].right, preorder, inorder, postorder)
postorder.append(u)
return preorder, inorder, postorder
for u, node in tree.items():
if node.parent == NIL: root = u
_, _, postorder = dfs(root, [], [], [])
print(*postorder)
tree = defaultdict(Node)
_ = int(input())
func(list(map(int, input().split())), list(map(int, input().split())))
debug(tree)
わざわざ二分木を作成しなくても、「左部分木 -> 右部分木 -> 根節点」の順で巡ったら後行順巡回になる。
Reconstruction of a Tree (Concise ver.)}
def func(pre_list, in_list, ans):
if pre_list == []: return
root = pre_list[0]
mid = in_list.index(root)
func(pre_list[1:mid + 1], in_list[:mid], ans)
func(pre_list[mid + 1:], in_list[mid + 1:], ans)
ans.append(root)
return ans
_ = int(input())
print(*func(list(map(int, input().split())), list(map(int, input().split())), []))