[Algorithm] 트리(tree)

✨트리(tree)

트리 구조란 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다.
최상위노드: 루트노드
자식없는 노드: 잎 노드
잎노드가 아닌 노드: 내부 노드

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

 

 

 

 

✨트리순회

전위 순회(preorder traversal),중위 순회(inorder traversal),후위 순회(postorder traversal)로 나뉘어진다.

 

 

 

ex) 백준 1991번 트리순회

https://www.acmicpc.net/problem/1991

import sys

class Node():
    def __init__(self,v,l,r):
        self.value=v
        if(l=='.'):self.left=None
        else:self.left=l
        if(r=='.'):self.right=None
        else:self.right=r

def preorder(nod: Node):
    print(nod.value,end="")
    if(nod.left!=None):preorder(tree[nod.left])
    if(nod.right!=None):preorder(tree[nod.right])


def inorder(nod: Node):
    if(nod.left!=None):inorder(tree[nod.left])
    print(nod.value,end="")
    if(nod.right!=None):inorder(tree[nod.right])

def postorder(nod: Node):
    
    if(nod.left!=None):postorder(tree[nod.left])
    if(nod.right!=None):postorder(tree[nod.right])
    print(nod.value,end="")




tree={}
for _ in range(int(sys.stdin.readline().rstrip())):
    a,b,c=sys.stdin.readline().rstrip().split(" ")
    tree[a]=Node(a,b,c)


preorder(tree['A'])
print("")
inorder(tree["A"])
print("")
postorder(tree["A"])

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🎈참고자료

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0