트리 순회

yongju·2022년 12월 11일
0

BAEKJOON

목록 보기
23/40
post-thumbnail

❓문제

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])
  • 전위순회(preorder) 방문한 노드(루트) 출력하고 왼쪽 자식노드로 가서 다시 전위순회, 다 끝나면 오른쪽 자식노드로 가서 다시 전위순회.
  • 왼쪽으로 깊이 들어갔다가 오른쪽으로 깊이 들어간다고 생각하기
def _inorder(node):
    if node.left:
        _inorder(tree[node.left])
    print(node.root,end='')
    if node.right:
        _inorder(tree[node.right])
  • 중위순회(inorder) : 기준 노드의 왼쪽 자식 노드로가서 중위순회 후 다시 루트 출력. 오른쪽 자식 노드로 가서 중위순회
  • 자손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='')
  • 후위순회(postorder) : 기준 노드의 왼쪽 자식 노드로 가서 후위순회 후 오른쪽 자식 노드로 가서 후위순회 후 노드 값 출력.
  • 자손노드 확인 후 자식노드 확인 맨 밑에서 올라오는 형태
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를 기준으로 시작

🎖제출 결과

💡insight

https://koosco.tistory.com/109

profile
AI dev

0개의 댓글