[PYTHON] Introduction to AOJ Programming (ALDS1)-# 7 Tree Structure

Introduction to AOJ Programming (ALDS1)-# 7 Tree Structure

AIZU ONLINE JUDGE> Introduction to Algorithms and Data Structures> # 7 Tree Structure

Declared a Node class that represents a node, and set the binary tree totree = defaultdict (Node). You can use defaultdict to handle any node number. The order is not guaranteed as it is, but you can get the ascending order of tree.keys () with set (tree).

1. Minimal construction as a binary tree based on input
2. Go around the binary tree and find the root location (+ get additional information)
3. Apply a recursive function with the root location as an argument to get additional information
4. Output the result

ALDS1_7_A: Rooted Trees

Learn from the "spiral book" and use the left-child, right-sibling representation. Perhaps it is a strength to be able to treat a tree as a binary tree.

Note that if you replace the recursion function with Python code as it is in the book, you will get an error due to too many recursion. You can increase the number of recursion with sys.setrecursionlimit (), but reduce the number of recursion of set_depth () by creating node.children while searching for root. be able to.

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

While looking for root, create node.sibling and node.degree (although it seems more orthodox to loop separately).

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: "Root node-> Left subtree-> Right subtree" In order tree walk: "Left subtree-> Root node-> Right subtree" Postorder tree walk: "Left subtree-> Right subtree-> Root node" Define a recursive function as defined in.

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

Hereinafter, the binary tree (a specific range) described by the preorder tree walk and the inorder tree walk will be referred to as pre_list and in_list.

In the preceding forward patrol, the order is "root node-> left subtree-> right subtree". In the intermediate order patrol, the order is "left subtree-> root node-> right subtree".

The root node value can be obtained with root = pre_list [0].

Using the position of the root node in the intermediate forward cycle mid = in_list.index (root), The left subtree in the intermediate order patrol is in_list [: mid] The right subtree in the intermediate order patrol is in_list [mid + 1:]

Note that the number of elements in the left subtree is equal to mid, The left subtree in the leading order patrol is pre_list [1: mid + 1] The right subtree in the leading order patrol is 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)

Even if you don't bother to create a binary tree, if you go around in the order of "left subtree-> right subtree-> root node", it will be a trailing cycle.

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())), []))