木構造に関する問題です． アルゴリズムについて詳しく知りたい方は参考文献などをご覧ください．
# ALDS1_7_A
n = int(input())
info_dict = {}
children_set = set([i for i in range(n)])
for _ in range(n):
info = list(map(int,input().split(" ")))
idx,k,children = info[0],info[1],info[2:]
info_dict[idx] = [idx,children] # node:idxの情報を持っておく
children_set = children_set - set(children) # 根を探しておく
tree_dict = {}
children_list = [[list(children_set)[0],-1,0]] # 根からスタート (idx, parent, depth)
# children_list が空になるまでループ
while children_list:
idx, parent, depth = children_list.pop() #
if parent == -1:
tree_dict[idx] = [idx,parent,depth,"root",info_dict[idx][1]]
elif info_dict[idx][1]:
tree_dict[idx] = [idx,parent,depth,"internal node",info_dict[idx][1]]
else:
tree_dict[idx] = [idx,parent,depth,"leaf",info_dict[idx][1]]
# 子の (idx, parent, depth) をchildren_listに追加する
for child in info_dict[idx][1]:
children_list.append([child,idx,depth+1])
for i in range(n):
# node 0: parent = -1, depth = 0, root, [1, 4, 10]の形式で出力
print(f"node {i}: parent = {tree_dict[i][1]}, depth = {tree_dict[i][2]}, {tree_dict[i][3]}, {tree_dict[i][4]}")
# ALDS1_7_B
n = int(input())
binary_tree = {}
info_dict = {}
children_set = set([i for i in range(n)])
for _ in range(n):
idx, left, right = map(int,input().split(" "))
info_dict[idx] = [left,right]
children_set = children_set - {left,right} # 根を探しておく
children_list = [[list(children_set)[0],-1,-1,0]]
leaf_set = set()
# children_listが空になるまでループ
while children_list:
idx, sibling, parent,depth = children_list.pop()
# node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
degree = 0
for x in info_dict[idx]:
if x != -1:
degree += 1
# nodeのtype別に処理
if parent == -1:
binary_tree[idx] = [idx,parent,sibling,degree,depth,0,"root"]
elif info_dict[idx] == [-1,-1]:
binary_tree[idx] = [idx,parent,sibling,degree,depth,0,"leaf"]
leaf_set.add(idx)
else:
binary_tree[idx] = [idx,parent,sibling,degree,depth,0,"internal node"]
# left, rightが-1でなければchildren_listに追加
if info_dict[idx][0] != -1:
children_list.append([info_dict[idx][0],info_dict[idx][1],idx,depth+1])
if info_dict[idx][1] != -1:
children_list.append([info_dict[idx][1],info_dict[idx][0],idx,depth+1])
# 高さを調べる
for idx in leaf_set:
height = 0
while True:
parent = binary_tree[idx][1]
if parent == -1:
break
height += 1
binary_tree[parent][5] = max(height,binary_tree[parent][5])
idx = parent
for i in range(n):
# node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root の形式で出力
idx,parent,sibling,degree,depth,height,node_type = binary_tree[i]
print(f"node {idx}: parent = {parent}, sibling = {sibling}, degree = {degree}, depth = {depth}, height = {height}, {node_type}")
# ALDS1_7_C
n = int(input())
binary_tree = {}
info_dict = {}
children_set = set([i for i in range(n)])
for _ in range(n):
idx, left, right = map(int,input().split(" "))
info_dict[idx] = [left,right]
children_set = children_set - {left,right} # 根を探しておく
root = list(children_set)[0]
children_list = [[list(children_set)[0],-1,-1,0]]
leaf_set = set()
# children_listが空になるまでループ
while children_list:
idx, sibling, parent,depth = children_list.pop()
# node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
degree = 0
for x in info_dict[idx]:
if x != -1:
degree += 1
# nodeのtype別に処理
if parent == -1:
binary_tree[idx] = [idx,parent,sibling,degree,depth,0,"root",info_dict[idx]]
elif info_dict[idx] == [-1,-1]:
binary_tree[idx] = [idx,parent,sibling,degree,depth,0,"leaf",info_dict[idx]]
leaf_set.add(idx)
else:
binary_tree[idx] = [idx,parent,sibling,degree,depth,0,"internal node",info_dict[idx]]
# left, rightが-1でなければchildren_listに追加
if info_dict[idx][0] != -1:
children_list.append([info_dict[idx][0],info_dict[idx][1],idx,depth+1])
if info_dict[idx][1] != -1:
children_list.append([info_dict[idx][1],info_dict[idx][0],idx,depth+1])
def pre_oder(root):
node_list = [root]
idx = root
while True:
# left_forward
if idx == -1:
break
left = binary_tree[idx][-1][0]
if left != -1 and left not in set(node_list):
node_list.append(left)
idx = left
elif left == -1:
while True:
# right_forward
if idx == -1:
break
right = binary_tree[idx][-1][1]
if right == -1 or right in set(node_list):
idx = binary_tree[idx][1] # 親に戻る
else:
if right == root:
break
elif right in set(node_list):
pass
else:
node_list.append(right)
idx = right
break
if right == root:
break
print("Preorder")
print(" ",end="")
print(*node_list)
def in_oder(root):
node_list = []
idx = root
while True:
# left_forward
if idx == -1:
break
left = binary_tree[idx][-1][0]
if left != -1 and left not in set(node_list):
idx = left
else:
node_list.append(idx)
while True:
# right_forward
if idx == -1:
break
right = binary_tree[idx][-1][1]
if right == -1 or right in set(node_list):
idx = binary_tree[idx][1] # 親に戻る
if idx not in node_list:
if idx != -1:
node_list.append(idx)
else:
if right == root:
break
elif right in set(node_list):
pass
else:
idx = right
break
if right == root:
break
print("Inorder")
print(" ",end="")
print(*node_list)
# 節点は右の要素から戻ってきたときに追加する
def post_oder(root):
node_list = []
idx = root
while True:
# left_forward
if idx == -1:
break
left = binary_tree[idx][-1][0]
if left != -1 and left not in set(node_list):
idx = left
else:
if binary_tree[idx][-1][1] == -1:
node_list.append(idx)
while True:
# right_forward
if idx == -1:
break
right = binary_tree[idx][-1][1]
if right == -1 or right in set(node_list):
child = idx
idx = binary_tree[idx][1] # 親に戻る
if child in node_list and idx not in node_list:
# 右側から戻ってきているなら追加
if idx != -1:
if binary_tree[idx][-1][1] == child:
node_list.append(idx)
# 左からだが右がないなら追加
elif binary_tree[idx][-1][1] == -1:
node_list.append(idx)
else:
if right == root:
break
elif right in set(node_list):
pass
else:
idx = right
break
if right == root:
break
print("Postorder")
print(" ",end="")
print(*node_list)
pre_oder(root)
in_oder(root)
post_oder(root)
# ALDS1_7_D
# 左 根 右 葉まで下る 左側の要素がなければ(根節点なので)追加 それ以外の点は下から戻ってきたときに追加する
def inOrder(root):
x = tree[root]
node_list = []
node_set = set()
while x!=None:
flag = True
# 左側の要素があるかを調べる
if x.left != None:
if x.left.key not in node_set:
x = x.left
flag = False
else:
# 左側の要素がない場合は追加してよい
if x.key not in node_set:
node_list.append(x.key)
node_set.add(x.key)
# 無ければ右側を調べる
if flag:
flag = True
# 葉までたどり着いたら追加
if x.right == None:
x = x.parent
if x.key not in node_set:
node_list.append(x.key)
node_set.add(x.key)
flag = False
if flag:
# まだ調べていない場合は下る
if x.right.key not in node_set:
x = x.right
# 既に調べてある場合は上る
else:
x = x.parent
if x != None:
if x.key not in node_set:
node_list.append(x.key)
node_set.add(x.key)
# print(" ",end="") # 問題に合わせて空白を入れただけ
# print(*node_list)
# 下るときに追加していけばいい 葉までたどり着いたら右側の要素が追加されていないところまで戻る
def preOrder(root):
x = tree[root]
node_list = [root]
node_set = set([root])
while x!=None:
# # print(node_list)
flag = True
# 左側の要素があるかを調べる
if x.left != None:
if x.left.key not in node_set:
x = x.left
node_list.append(x.key)
node_set.add(x.key)
flag = False
# 無ければ右側を調べる
if flag:
flag = True
# 葉までたどり着いたら戻る
if x.right == None:
x = x.parent
flag = False
if flag:
# まだ調べていない場合は下る
if x.right.key not in node_set:
x = x.right
node_list.append(x.key)
node_set.add(x.key)
# 既に調べてある場合は上る
else:
if x != None:
x = x.parent
# print(" ",end="") # 問題に合わせて空白を入れただけ
# print(*node_list)
def postOrder(root):
x = tree[root]
node_list = []
node_set = set()
while x!=None:
# print(x.key)
flag = True
# 左側の要素があるかを調べる
if x.left != None:
if x.left.key not in node_set:
x = x.left
flag = False
# 無ければ右側を調べる
if flag:
flag = True
# 葉までたどり着いたら追加
if x.right == None:
node_list.append(x.key)
node_set.add(x.key)
x = x.parent
flag = False
if flag:
# まだ調べていない場合は下る
if x.right.key not in node_set:
x = x.right
# 既に調べてある場合は上る
else:
if x != None:
# 右側から戻ってきていれば追加
# print(x.key,x.right.key)
if x.key not in node_set and x.right.key in node_set:
node_list.append(x.key)
node_set.add(x.key)
x = x.parent
# print(" ",end="") # 問題に合わせて空白を入れただけ
print(*node_list)
# Nodeクラスを自作して木を表現する
class Node:
def __init__(self,key):
self.key = key
self.right = None # 右の子
self.left = None #左の子
self.parent = None # 親
n = int(input())
preorder_tree = list(map(int,input().split()))
inorder_tree = list(map(int,input().split()))
# preorderで根を見つける
root = preorder_tree.pop(0)
root0 = root # 一番最初の根
# inorder_treeを使って根の左と右で分ける
left_tree = [] # 中間順巡回 の根の左側は左部分木
right_tree = [] # 中間順巡回 の根の右側は右部分木
left = True
for x in inorder_tree:
if x == root:
left = False
continue
if left:
left_tree.append(x)
else:
right_tree.append(x)
# root, parent, left_tree, right_treeのリストを作る
parent = None
tree_list = [[root,parent,left_tree,right_tree]]
node_list = []
tree = {root0:Node(root0)}
while tree_list:
root,parent,left_tree,right_tree = tree_list.pop(0)
node = tree[root]
left_root = None
right_root = None
# 部分木の根を見つける(先行順巡回で最初にぶつかったものが根)
for x in preorder_tree:
if x in left_tree and left_root==None:
left_root = x
# inorder_treeを使って根の左と右で分ける
left_tree2 = []
right_tree2 = []
left = True
for y in left_tree:
if y == left_root:
left = False
continue
if left:
left_tree2.append(y)
else:
right_tree2.append(y)
tree_list.append([left_root,node,left_tree2,right_tree2])
elif x in right_tree and right_root==None:
right_root = x
# inorder_treeを使って根の左と右で分ける
left_tree2 = []
right_tree2 = []
left = True
for y in right_tree:
if y == right_root:
left = False
continue
if left:
left_tree2.append(y)
else:
right_tree2.append(y)
tree_list.append([right_root,node,left_tree2,right_tree2])
break
# 調べ終わった要素を先行順巡回のリストから取り除き，Nodeを更新
if left_root!=None:
preorder_tree.remove(left_root)
left_node = Node(left_root)
node.left = left_node
tree[left_root] = left_node
if right_root!=None:
preorder_tree.remove(right_root)
right_node = Node(right_root)
node.right = right_node
tree[right_root] = right_node
# 親を設定する
node.parent = parent
node_list.append(node)
tree[node.key] = node
# 出来上がった木を表示
postOrder(root0)