[Coding Test][Python]Tree 개념 및 Tree 순회(Inorder, Preorder Postorder) 구현

※ Tree 란?

데이터를 계층적으로 구성하고 관리하는 자료구조이다.

서로 연결된 Node들로 구성되며 Cycle이 없는 Graph이다.

 

Tree 용어 정리

• Node : Tree는 보통 node로 구현
• Edge : Node 간에 연결된 선
• Root Node : Tree는 항상 Root Node에서 시작
• Leef Node : 더이상 뻗어나갈 수 없는 마지막 노드
• Parent Node : 다른 노드와 연결되어 Child Node를 가진 Node
• Child Node : Parent Node에서 파생된 Node
• Sibling Node : 같은 Level에 있는 Node
• Degree : 각 노드가 갖는 Child Node의 수, 모든 Node의 Degree가 n개 이하인 Tree를 n진 Tree라고 한다
• Ancestor(조상) : 위쪽으로 Edge를 따라가면 만나는 모든 Node
• Descendant(자손) : 아래쪽으로 Edge를 따라가면 만나는 모든 Node
• Level : Root Node로부터 떨어진 거리(Root Node는 Level 0)
• Height : Root Node에서 가장 멀리 있는 Leef Node 까지의 거리, 즉, Leef Node중에 최대 Level 값
• Subtree : Tree의 어떤 Node를 Root로 하고, 그 자손으로 구성된 Tree

Tree 종류

• Binary Tree(이진트리) : 모든 Node의 Degree가 2 이하인 Tree
  • Complete Binary Tree(완전 이진 트리) : 모든 Node의 Degree가 2(또는 0)인 Tree (왼쪽에서부터 채워져야한다)
  • Full Binary Tree(포화 이진 트리) : 모든 Node가 Degree가 2인 Tree
  • Balanced Binary Tree(균형 이진 트리) : 모든 Leaf Node의 height 차이가 일정한 범위 내에 있는 Tree
• Binary Search Tree : 왼쪽 SubTree에는 현재 Node 보다 작은 값, 오른쪽 SubTree에는 현재 Node 보다 더 큰 값이 저장된 트리
  • 검색, 삭제, 삭제가 효율적이다( O(logn) )
• Heap Tree : 
  • Max Heap : Parent Node의 값이 항상 자식 노드의 값보다 크거나 같은 Tree
  • Min Heap: Parent Node의 값이 항상 자식 노드의 값보다 작거나 같은 Tree
• AVL Tree, Red - Black Tree, B-Tree 등이 있다.

1. Tree 순회 구현 

Tree 순회 방법으로는 Level order, Pre order(전위 순회), In order(중위 순회), Post order(후위 순회) Traversal이 있다.

1) Node 정의 

class Node(object):
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

2) Tree 생성하기

from collections import deque

def make_tree(data):
    if not data:
        return None
    
    root = Node(data[0])
    queue = deque()
    queue.append(root)

    i = 1
    while queue and i < len(data):
        curr = queue.popleft()

        if data[i] is not None:
            curr.left = Node(data[i])
            queue.append(curr.left)
            i += 1

        if data[i] is not None:
            curr.right = Node(data[i])
            queue.append(curr.right)
            i += 1

    return root

 

data의 순서대로 Tree의 왼쪽부터 채우는 코드입니다.

 

위의 Tree를 생성하기 위한 코드는 아래와 같습니다.

순회를 위한 코드는 아래에서 차례차례 설명드리겠습니다.

root = make_tree([100,20, 200, 10, 30, 150, 300])

3) Level Order

Root Node에서부터 시작해 같은 Level에 있는 Node들을 BFS를 통해 방문합니다.

from collections import deque
def level_order(root):
    visited = []
    if root is None:
        return 0
    
    q = deque()
    q.append(root)
    
    while q:
        curr_node = q.popleft()
        visited.append(curr_node.value)
 		
        if curr_node.left:
            q.append(curr_node.left)
        if curr_node.right:
            q.append(curr_node.right)
    return visited

 

위에서 본 Tree를 Level Order로 방문하면 아래와 같은 결과를 얻을 수 있습니다.

print(level_order(root))

 

[100, 20, 200, 10, 30, 150, 300]

4) Pre Order(전위 순회)

V -> L -> R 순으로 방문합니다.

# 전위 순회
def preorder(curr_node):
    # Base Case
    if curr_node is None:
        return
    # 접근
    print(curr_node.value)
    # 방문
    preorder(curr_node.left)
    preorder(curr_node.right)

 

아래는 Pre order로 순회한 결과입니다.

preorder(root)

 

100 20 10 30 200 150 300

5) In Order(중위 순회)

L-> V -> R 순으로 방문합니다.

# 중위 순회
def inorder(curr_node):
    # Base Case
    if curr_node is None:
        return
    
    inorder(curr_node.left)
    print(curr_node.value)
    inorder(curr_node.right)

아래는 In order로 순회한 결과입니다.

inorder(root)

10 20 30 100 150 200 300

6) Post Order(후위 순회)

L -> R -> L 순으로 방문합니다.

# 후위 순회
def postorder(curr_node):
    # Base Case
    if curr_node is None:
        return
    
    postorder(curr_node.left)
    postorder(curr_node.right)
    print(curr_node.value)

postorder(root)

10 30 20 150 300 200 100

 

2. Tree를 이용한 예제

Binary Tree 하나와 해당 Tree에 속한 두 개의 Node가 주어진다. 이 때, 두 Node의 공통 조상 중 가장 낮은 Node, 즉 The lowest comment ancestor(LCA)를 찾아라.

제약조건         
$2 <= Node 개수 <= 10^5$
$-10^9 <= Node.value <= 10^9$        
$p \neq q$

모든 Node의 value는 Unique 하다     
p, q는 모두 주어진 Tree에 속해있다

Input, Output        
Input : 3 5 1 6 2 0 8 None None 7 4, p=5, q=4       
Output : 5

 

1) Node 정의 

class Node(object):
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

2) Tree 생성하기

from collections import deque

def make_tree(data):
    if not data:
        return None
    
    root = Node(data[0])
    queue = deque()
    queue.append(root)

    i = 1
    while queue and i < len(data):
        curr = queue.popleft()

        if data[i] is not None:
            curr.left = Node(data[i])
            queue.append(curr.left)
            i += 1

        if data[i] is not None:
            curr.right = Node(data[i])
            queue.append(curr.right)
            i += 1

    return root

3) LCA 풀이

from collections import deque
def LCA(curr, p, q):
    if curr == None:
        return None
    
    # Postorder 방식
    
    # Left, Right child Node에서 오는 값을 봐야한다
    left = LCA(curr.left, p, q)
    right = LCA(curr.right, p, q)

    # 현재 Node가 p, q일 때 값을 반환해준다
    if curr.value == p or curr.value == q:
        return curr.value
    # Left, Right에서 오는 값이 모두 존재한다면
    # 현재 Node가 LCA
    elif left and right:
        return curr.value
    # Left 또는 Right에서 return 값이 존재한다면
    # 이를 그대로 위로 올려보내야한다
    elif left or right:
        return left or right

left = LCA(curr.left, p, q)
right = LCA(curr.right, p, q)

Lowest Common Ancestor를 찾기 위해 Post Order Traversal을 통해 Left와 Right에서 return 되는 값을 확인합니다.

if curr.value == p or curr.value == q:
    return curr.value

현재 Node의 값이 찾는 Node중 하나 라면 현재 Node를 return합니다.

즉, 이 값을 위로 올려보내주게 됩니다.

elif left and right:
    return curr.value

목표 값을 올려주다보면 Left, Right 값이 모두 존재하는 Node가 존재하게 되는데 바로 이 Node가 p, q의 LCA입니다.

elif left or right:
    return left or right

Left 또는 Right에서 값이 왔다면 현재 p, q의 LCA는 아니지만 탐색 중 p, q 중 하나가 발견되었다는 의미이므로 그대로 return 해주어서 올려주게 됩니다.

data = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]
tree = make_tree(data)
p, q = 6, 4

LCA(tree, p, q)

6