https://www.acmicpc.net/problem/1991
트리의 전위순회, 중위순회, 후위순회 코드를 그대로 적용하면 풀리는 문제
트리 개념/코드 정리
예제 1의 트리 모습
class Node:
def __init__(self, root, left, right):
self.root=root
self.left=left
self.right=right
def _preorder(node):
print(node.root,end='')
if node.left:
_preorder(tree[node.left])
if node.right:
_preorder(tree[node.right])
def _inorder(node):
if node.left:
_inorder(tree[node.left])
print(node.root,end='')
if node.right:
_inorder(tree[node.right])
def _postorder(node):
if node.left:
_postorder(tree[node.left])
if node.right:
_postorder(tree[node.right])
print(node.root,end='')
n=int(input())#노드의 개수
tree={}
for _ in range(n):
root, left, right=input().split()
if left=='.':
left=None
if right=='.':
right=None
tree[root]=Node(root, left, right)
_preorder(tree['A'])
print()
_inorder(tree['A'])
print()
_postorder(tree['A'])
class Node:
def __init__(self, root, left, right):
self.root=root
self.left=left
self.right=right
노드의 역할을 정의해주는 Node 클래스 작성.
root는 부모노드,left, right는 부모노드 왼쪽과 오른쪽에 달린 자식노드를 의미한다.
def _preorder(node):
print(node.root,end='')
if node.left:
_preorder(tree[node.left])
if node.right:
_preorder(tree[node.right])
왼쪽으로 깊이 들어갔다가 오른쪽으로 깊이 들어간다고 생각하기
def _inorder(node):
if node.left:
_inorder(tree[node.left])
print(node.root,end='')
if node.right:
_inorder(tree[node.right])
자손2->자손1(왼쪽)->자손2(오른쪽)->왼쪽자식->루트->자손2->자손1(왼쪽)->자손2(오른쪽)->자식(오른쪽)
def _postorder(node):
if node.left:
_postorder(tree[node.left])
if node.right:
_postorder(tree[node.right])
print(node.root,end='')
자손노드 확인 후 자식노드 확인 맨 밑에서 올라오는 형태
n=int(input())#노드의 개수
tree={}
for _ in range(n):
root, left, right=input().split()
if left=='.':
left=None
if right=='.':
right=None
tree[root]=Node(root, left, right)
노드의 개수n 입력받은 후 n만큼의 연결된 노드 입력받기.
.인 경우, 연결 노드가 없다는 것.->None으로 그래프 만들어주기
_preorder(tree['A'])
print()
_inorder(tree['A'])
print()
_postorder(tree['A'])
항상 A가 루트 노드가 된다고 문제에서 제시하였으므로 A를 기준으로 시작