[데이터 구조] 18차시 트리(Tree) | 트리 항해(Tree Traversal)와 쓰레드 이진 트리(Threaded Binary Trees)

1. 트리 항해

1) Binary Tree Traversal

(1) 정의

- Tree의 각 node를 한 번씩 방문하는 알고리즘

- 각 node와 그 node의 subtree들을 동등하게 취급하면 6개의 traversal 조합이 있다.

(L: Left로 움직임, V: 노드를 visiting, R: Right로 움직임)

1️⃣LVR 2️⃣LRV 3️⃣VLR 4️⃣VRL 5️⃣RVL 6️⃣RLV

 

- Traverse left before right를 도입하면, 3개의 조합이 남는다.

 

 

(2) In-order Traversals(중위 순회)

- 방법: 왼쪽 branch를 모두 방문한 후, node를 방문하고, 오른쪽 branch를 방문함

 

 

(3) Pre-order Traversals(전위 순회)

- 방법: node를 방문하고, 왼쪽 branch를 모두 방문한 후, 오른쪽 branch를 방문

 

(4) Post-order Traversals(후위 순회)

- 방법: 왼쪽 branch를 모두 방문한 후, 오른쪽 branch를 방문한 후, node를 방문함

 

 

 

 

 

 

 

 

 

2) Additional Binary Tree Operations

(1) Iterative In-order Traversal

- 중위 순회를 위한 비순환 알고리즘

- 순환 호출을 제어하기 위해 스택을 사용

ex) 팩토리얼, 피보나치, 트리 순회, 이진 탐색, 하노이 타워, quick sort 등

 

 

- Recursive version의 system stack을 모방하기 위해 stack에 대한 삽입, 삭제 구현

 

(2) 레벨 순서 순회(Level Order Traversal)

- 이진 트리를 노드의 레벨 순서(수평)로 순회

- 큐를 사용

1️⃣먼저 루트 노드를 큐에 삽입

2️⃣순회는 큐 front에 있는 노드를 가져와 NULL이 아니면, 그 노드를 방문한 후

3️⃣그의 왼쪽 자식과 오른쪽 자식을 찾아 순서대로 큐 rear에 삽입

4️⃣이 과정을 큐가 공백이 될 때까지 반복

 

 

- 아래 그림의 sequential node number에 근거한 항해 방법으로서 queue로 구현한다.

 

 

 

(3) 일반 트리 순회

- 전위(tree preorder) 순회

1️⃣루트를 방문

2️⃣첫 번째 서브트리를 트리 전위로 순회

3️⃣나머지 서브트리들을 트리 전위로 순회

 

- 중위(tree inorder) 순회

1️⃣첫 번째 서브 트리를 트리 중위로 순회

2️⃣루트를 방문

3️⃣나머지 서브트리들을 트리 중위로 순회

 

- 후위(tree postorder) 순회

1️⃣첫 번째 서브트리를 트리 후위로 순회

2️⃣나머지 서브트리를 트리 후위로 순회

3️⃣루트를 방문

 

 

(4) 일반 트리와 이진 트리로 표현된 것의 순회

 

(5) 이진 트리의 기타 연산

1️⃣주어진 이진 트리의 복사(T를 받아서, S에 복사함)

 

 

2️⃣주어진 2개의 이진 트리의 동등성 검사(TFdecision로 결정)

 

 

 

 

2. 쓰레드 이진 트리

1) 정의

- Thread: 불필요한 Null link 대신, tree 내의 다른 노드를 가리키는 용도로 사용

- 왜 Thread를 사용하는가?

• 이진 트리는 Node당 2개의 link가 있으므로, tree의 null link는 n + 1개임.
• Binary tree에서 2n개의 link들 중, leaf의 n+1개 link가 안 쓰는 null link임
  
  

- 문제점

1️⃣ 아무 쓸모 없는 null link가 너무 많다(NULL link 수 = node의 총 수 + 1)

2️⃣ 각 순회 순서상, 임의 단말 노드의 앞 노드(previous node)와 뒷 노드(successor node)를 모른다.

 

- Thread 구성 규칙

1️⃣한 node의 left-child가 null이면, 그 값이 in-order traversal에 의해 현 node 바로 전에 방문되는 node를 가리킨다. (현 node의 in-order predecessor를 가리킴)

 

2️⃣ 한 node의 right-child가 null이면, 그 값이 in-order traversal에 의해 현 node 바로 뒤에 방문되는 node를 가리킨다. (현 node의 in-order successor를 가리킴)

 

 

 

Q. 실제 포인터와 스레드를 어떻게 구분하나?

A. thread와 normal pointer를 구분하기 위해 다음 두 개의 field를 추가함: left_thread, right_thread

 

- dangling reference 방지를 위해 모든 threaded binary tree는 head node(dummy root)를 유지한다.

- 따라서, empty threaded binary tree라도 적어도 하나의 node를 가진다.

 

- left_thread field가 0(false)일 때, left_child는 현 node의 left child를 가리키는 용도임

- left_thread field가 1(true)일 때, left_child는 현 node의 in-order predecessor를 가리키는 용도임

 

 

 

 

 

 

 

2) In-order Traversal of a Threaded Binary Tree

- 일반적으로 이미 방문했던 노드이지만, 다음에 사용해야 하는 node를 keeping하는 방법으로 stack을 이용

- 그러나, stack을 사용하지 않고도 threaded tree의 thread를 이용하여 in-order traversal 수행하여 다음 노드를 알 수 있다.

- ptr 노드의 in-order 순 뒷 노드를 찾아보자.

 

 

 

3) Threaded Binary Trees 삽입

- 오른쪽 subtree가 없는 parent에서 오른쪽에 child를 만들어보자.

1️⃣parent -> right_thread를 False로 만듦

2️⃣child -> left_thread, child->right_thread를 True로 만듦

3️⃣child -> left_child가 parent를 가리키게 한다.

4️⃣child -> right_child가 parent -> right_child값을 가짐

5️⃣parent -> right_child가 child를 가리킴