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)
.
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}')
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}')
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())), []))
Recommended Posts