AOJ プログラミング入門 (ALDS1) - #7 木構造

# AOJ プログラミング入門 (ALDS1) - #7 木構造

[AIZU ONLINE JUDGE](https://onlinejudge.u-aizu.ac.jp/courses/list) > [アルゴリズムとデータ構造入門](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1) > [#7 木構造](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7)

節点を表す `Node` クラスを宣言し、二分木を `tree = defaultdict(Node)` とした。
`defaultdict` を用いれば、どのような節点番号にも対応できる。
そのままでは順番が保証されないが、`set(tree)` で `tree.keys()` の昇順を取得可能。

1. 入力に基づいて二分木として最低限の構築を行う
2. 二分木を一巡して、根の場所を探す（＋追加情報を得る）
3. 根の場所を引数として再帰関数を適用し、追加情報を得る
4. 結果を出力する

## [ALDS1_7_A: Rooted Trees](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_7_A)

「らせん本」に習って左子右兄弟表現（left-child, right-sibling representation）を用いる。多分木を二分木として扱うことができるのが強みらしい。

書籍の内容のままで再帰関数を Python のコードに置き換えると、再帰の回数が多すぎるためにエラーが発生することに注意。`sys.setrecursionlimit()` で再帰の回数の上限を増やしてもいいけど、`root` を探すついでに `node.children` を作成しておくことで、`set_depth()` の再帰の回数を減らすことができる。

```{python: 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](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_7_B)

`root` を探すついでに `node.sibling` と `node.degree` を作成しておく（別々にループを回した方が正統派な気もするけど）。

```{python: 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](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_7_C)

先行順巡回（preorder tree walk）：「根節点 -> 左部分木 -> 右部分木」の順
中間順巡回（inorder tree walk）：「左部分木 -> 根節点 -> 右部分木」の順
後行順巡回（postorder tree walk）：「左部分木 -> 右部分木 -> 根節点」の順
の定義通りに再帰関数を定義する。

```{python: 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](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_7_D)

以下、二分木（の特定の範囲）を先行順巡回（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:]`

```{python: 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)

```

わざわざ二分木を作成しなくても、「左部分木 -> 右部分木 -> 根節点」の順で巡ったら後行順巡回になる。

```{python: 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())), []))

```