[자료구조] 트리 (Tree) - 이진 트리 순회 (Binary Tree Traversal) | 트라이 (Trie, Prefix Trees)

이전글

[자료구조] 트리 (Tree) - 트리의 정의와 종류 (이진트리 등)

---

이진 트리 순회방법에는 세가지가 있다. in-order, pre-oder, post-order 이다.

In-Order Traversal (중위순회)

in-order traversal은 left -> current -> right 노드 순서로 순회하는 방법이다.

def inOrderTraversal(node):
    if node != None:
    	inOrderTraversal(node.left)
        visit(node)
        inOrderTraversal(node.right)

이진 탐색 트리 (binary search tree)에서 in-order 순회를 사용하게 되면 오름차순으로 노드를 방문한다.

 

Pre-Order Traversal (전위순회)

current 노드 -> child 노드 (left, right) 순서로 순회하는 방법이다.

def preOrderTraversal(node):
    if node != None:
        visit(node)
    	inOrderTraversal(node.left)
        inOrderTraversal(node.right)

pre-order 순회에서는 root 노드를 처음으로 방문한다.

 

Post-Order Traversal (후위순회)

child 노드 (left, right) -> current 노드 순서로 순회한다.

def postOrderTraversal(node):
    if node != None:
    	inOrderTraversal(node.left)
        inOrderTraversal(node.right)
        visit(node)

post-order 순회에서는 root 노드를 마지막으로 방문한다.

---

Tries (Prefix Trees)

트라이는 n-ary 트리의 변형으로 각 노드에 character가 저장되어있다. 주로 영단어를 표시할 때 사용된다.

마지막 null node는 단어가 끝났음을 알리는 노드이다.

 

트라이는 O(K) 안에 빠르게 접두사를 검색할 수 있다. (K는 문자열의 길이)

---

출처

- Cracking the Coding Interview - Chapter 4. Trees and Graphs