이진 트리의 순회

대표적인 자료구조인 트리에서 이진트리를 순회하는 방법 및 간단한 코드를 소개하겠다.

 

이진 트리(Binart Tree)

트리란 각 노드가 부모-자녀 관계를 갖는 계층 구조를 나타낸 데이터 구조이며, 루트 노드에서 시작하여 하위 노드로 분기되는 비선형 데이터 구조이다. 리프 노드를 제외한 각 노드에는 하나 이상의 하위 노드가 있다.

이진트리는 이러한 트리 구조중 각 노드들이 자식을 2개 이하로 가지는 트리를 칭한다.

 

이진 트리의 순회

이진 트리를 순회하는 방법은 대표적으로 3가지가 있다.(백준 1991)

이진트리 예시

preorder(전위 순회)

-(루트)(왼쪽 자식)(오른쪽 자식) 순서로 순회

def preorder(curr):
    if curr != '.':		#현재 노드가 null이 아니면 (여기서는 .을 null이라 가정)
        print(curr, end= '')
        preorder(tree[curr][0])	#왼쪽 자식
        preorder(tree[curr][1])	#오른쪽 자식

-위 예시에서 탐색 결과는 3->6->5->4->8->7->1->2

 

inorder(중위 순회)

-(왼쪽 자식)(루트)(오른쪽 자식) 순서로 순회

def inorder(curr):
    if curr != '.':
        inorder(tree[curr][0])
        print(curr, end='')
        inorder(tree[curr][1])

-위 예시에서 탐색 결과는 5->6->8->4->3->1->2->7

 

postorder(후위 순회)

-(왼쪽 자식)(오른쪽 자식)(루트) 순서로 순회

def postorder(curr):
    if curr != '.':
        postorder(tree[curr][0])
        postorder(tree[curr][1])
        print(curr, end='')

-위 예시에서 탐색 결과는 5->8->4->6->2->1->7->3

 

두 순회 결과로 트리 구조 얻기 (백준 2263, 4256)

inorder와 preorder 또는 inorder와 postorder의 순회 결과를 알면 트리의 구조를 알 수 있다.

• inorder + preorder
  • preorder는 루트노드 부터 탐색을 시작한다는 성질(첫번째 값이 루트)과 inorder의 탐색 순서인 (왼쪽 자식)(루트)(오른쪽 자식)을 이용하여 분할 정복한다.
    1. preorder에서 루트 노드를 구한 뒤, inorder에서 루트를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나눈다.
    2. 각 서브트리의 시작 index와 끝 index를 이용하여 해당 범위에 대해 1번을 시행한다. (서브트리에서 각각 루트 노드를 구한 뒤, 루트를 기준으로 다시 왼쪽 서브트리와 오른쪽 서브트리로 나눈다.) 이 때, preorder에서는 시작노드가 루트가 되므로 다음 탐색에서 시작노드가 제외되고 inorder에서는 끝 노드가 루트이므로 끝 노드가 제외되므로 index를 구할 때 주의해야한다.
    3. 이 과정을 반복하여 분할 정복하면 트리의 구조를 알 수 있다.

def makePost(preStart, preEnd, inStart, inEnd):
    if (preStart > preEnd) or (inStart > inEnd):
        return
    root = preorder[preStart]    #preorder의 시작 노드가 루트
    rootIndex = nodeIndex[root]  #inorder에서 root의 index
    leftCount = rootIndex - inStart #왼쪽 서브트리 노드의 개수
    rightCount = inEnd - rootIndex  #오른쪽 서브트리 노드의 개수
    
    makePost(preStart + 1, preStart + leftCount, inStart, inStart + leftCount - 1)  #왼쪽 서브트리에 대해 탐색
    makePost(preEnd - rightCount + 1, preEnd, inEnd - rightCount + 1, inEnd)    #오른쪽 서브트리에 대해 탐색
    print(root)

•  inorder + postorder
  • postorder의 맨 끝 노드가 루트노드임을 이용하여 위 방식과 마찬가지로 구현하면 된다.

def makePre(inStart,inEnd,postStart,postEnd):
    if (inStart > inEnd) or (postStart > postEnd):
        return
        
    root = postorder[postEnd]	#postorder의 끝 노드가 루트
    print(root)
    
    rootIndex = nodeIndex[root]	#inorder에서 root의 index
    leftCount = rootIndex - inStart	#왼쪽 서브트리 노드의 개수
    rightCount = inEnd - rootIndex	#오른쪽 서브트리 노드의 개수

    makePre(inStart, inStart + leftCount - 1, postStart, postStart + leftCount - 1)
    makePre(inEnd - rightCount + 1, inEnd, postEnd - rightCount, postEnd - 1)