5-3강 - Binary Tree Traversals (이진 트리 순회)

이 부분은 예시 동영상과 함께 보며 문제를 푸는 것이 좋다.

 

0) 이진 트리 순회에 대한 소개

1> 전제 

: tree의 모든 node를 한 번씩만 방문한다.

 

2> linear order의 필요성

1> 완전한 순회를 위해서 linear order가 필요하다.

2> 그리고 이 순서가 subtree(child들)에도 동일하게 적용되어야 한다.

 

3> 기호

L : left child로 pointer로 이동

R : right child로 pointer로 이동 

V : node 방문

 

4> order의 종료

LVR : inorder traversal (중위 순회)

VLR : preorder traversal (전위 순회)

LRV : postorder traversal (후위 순회)

VRL, RVL, RLV

 

1) Inorder Traversal

1> inorder 함수 (LVR)

parameter로 node pointer를 받는다.

[0] 해당 node pointer가 존재하면

- [1] 왼쪽 child에 대한 pointer를 가지고 inorder 한다. (재귀적으로 구현)

- [2] 현재 pointer가 가리키는 node의 data를 탐색(출력)

- [3] 오른쪽 child에 대한 pointer를 가지고 inorder 한다. (재귀적으로 구현)

 

2> 함수에 대한 설명

재귀적으로 구현이 되며 왼쪽 child를 먼저 가리킨다.

=> [0] & [1] 처음에 왼쪽으로 내려갈 수 있는 node까지 계속 내려간다.

=> [0] 맨 끝의 node는 왼쪽 node가 없으므로

=> [2] 그리고 해당 node를 출력하고

=> [3] 오른쪽 node에 대해 inorder

 

3> 구현

void inorder (node_pointer ptr)
{
	if (ptr) {
		inorder(ptr->left_child);
		printf("%c", ptr->data);
        	inorder(ptr->right_child);
	}
}

4> 예시

=> A / B * C * D + E

 

2) Preorder Traversal

1> preorder 함수 (VLR)

parameter로 node pointer를 받는다.

[0] 해당 node pointer가 존재하면

- [1] 현재 pointer가 가리키는 node의 data를 탐색(출력)

- [2] 왼쪽 child에 대한 pointer를 가지고 preorder 한다. (재귀적으로 구현)

- [3] 오른쪽 child에 대한 pointer를 가지고 preorder 한다. (재귀적으로 구현)

 

2> 함수에 대한 설명

parameter로 node pointer를 받는다.

[0] 해당 node pointer가 존재하면

[1] root node의 data를 출력

=> [2] 왼쪽 child node를 가리키고 preorder 함수 진행

=> [1] 이 node(아까 가리킨 child node)의 data를 출력한다. (재귀적으로 진행=> [1]과 [2]를 반복)

=> [3] 더 이상 왼쪽 child node가 존재하지 않으면 sibling(parent의 오른쪽 child node)를 가리키고

=> [1] 이 node(아까 가리킨 sibling)의 data를 출력한다. (재귀적으로 진행 => [1]과 [2]를 반복)

 

3> 구현

void preorder(nodePointer ptr)
{
	if (ptr) {
		printf(“%d”, ptr->data);
		preorder(ptr->leftChild);
		preorder(ptr->rightChild);
	}
}

 

4> 예시

=> +**/ABCDE

 

3) Postorder Traversal

1> postorder 함수 (LRV)

parameter로 node pointer를 받는다.

[0] 해당 node pointer가 존재하면

- [1] 왼쪽 child에 대한 pointer를 가지고 postorder 한다. (재귀적으로 구현)

- [2] 오른쪽 child에 대한 pointer를 가지고 postorder 한다. (재귀적으로 구현)

- [3] 현재 pointer가 가리키는 node의 data를 탐색(출력)

 

2> 함수에 대한 설명

parameter로 node pointer를 받는다.

재귀적으로 구현이 되며 왼쪽 child를 먼저 가리킨다.

=> [0] & [1] 처음에 왼쪽으로 내려갈 수 있는 node까지 계속 내려간다.

=> [0] 맨 끝의 node는 왼쪽 node가 없으므로 

=> [2] 대안으로 오른쪽 child node를 가리키고 postorder 함수 진행

=> [0] & [1] & [2] 왼쪽으로 내려갈 수 있는 node까지 계속 내려간다. 왼쪽이 막히면 오른쪽으로 간다.

=> [0] & [1] & [2] & [0] 양쪽 child 모두 없는 경우 

=> [3] 현재 pointer가 가리키고 있는 이 node를 출력

=>

[2] 왼쪽에서 올라온 경우 parent node의 오른쪽 child node에 대해 postorder하고

[3] 오른쪽에서 올라온 경우 parent node를 즉시 출력

 

3> 구현

void postorder(nodePointer ptr)
/* Postorder Traversal */
{
	if (ptr) {
		postorder(ptr->leftChild);
		postorder(ptr->rightChild);
		printf(“%d”, ptr->data);
	}
}

4> 예시

=> AB/C*D*E+

 

4) Iterative Inorder Traversal

위의 3가지 방법 모두 재귀적으로도 만들 수 있지만 반복문을 사용해서도 만들 수 있다.

1> 원리 (3가지 방법 모두 적용)

- action (탐색 후 출력)이 없을 때까지 stack에 쌓고

- action이 있으면 stack에 저장된 원소를 pop

 

2> iterative inorder traversal 적용

- left child node를 stack (NULL node가 올 때까지)

- NULL node를 만나면 (출력을 해야하면) stack에서 pop => data printf

- 그리고 출력한 node의 right child를 stack

 

3> 구현

void iter_inorder (node_pointer node)
{
	int top = 1; /* initialize stack */
	node_pointer stack[MAX_STACK_SIZE];
	for ( ; ; ) {
		for ( ; node; node = node->left_child) push(node); // [1] 왼쪽의 child node를 가리키고 계속 stakc
		// [0] 더 이상 왼쪽에 stack이 존재하지 않으면 반복문 종료하고
        node = pop(); // [2] stack에서 pop
		if (!node) break; // 출력할 node가 없다면 함수 종료
		printf("%c", node->data); // [2] pop한 data를 출력
		node = node->right_child; // 오른쪽 node로 pointer를 이동
	}
}

4> 특징

- 시간 복잡도 : O(n)

- 공간 복잡도 : O(n)

 

 

5) Level Order Traversal

queue를 이용해서 순회하는 방법

(먼저 들어온 것이 먼저 나가는 구조)

특정 level에 존재하는 node들을 모두 탐색하고 그 다음 level에 존재하는 node들을 탐색

코드 작성

 

 

4. Additional Binary Tree Operation (이진 트리의 추가 연산)

 

binary tree의 정의와 recursive traversal을 이용하면 binary tree에 대한 다양한 operation을 구현할 수 있다.

 

1) Copying Binary Trees

(위에서 만든 postoreder 방식으로 copy)

1> copy 함수

parameter로 node_pointer(original)를 받는다.

[0] 해당 node_pointer가 존재하면 메모리(temp)를 동적 할당으로 확보

[0]' 동적 할당한 메모리(temp) 안에 node가 들어있는지 확인=> node가 들어있으면 함수 종료

- [1] node_pointer(original)의 왼쪽 child에 대한 pointer를 가지고 copy 한다. (재귀적으로 구현)

여기서 return한 node pointer를 동적 할당한 메모리(temp)의 왼쪽 child 에게 할당

- [2] node_pointer(original)의 오른쪽 child에 대한 pointer를 가지고 copy 한다. (재귀적으로 구현)

여기서 return한 node pointer를 동적 할당한 메모리(temp)의 오른쪽 child 에게 할당

- [3] 현재 node_pointer(original)가 가리키는 node의 data를 동적 할당한 메모리(temp)의 data에 복사 탐색(출력)

코드 작성

 

2) Testing For Equality

동일성 검사는 [1] 같은 구조를 가지며 [2] 대응 되는 node에 있는 정보들이 일치하면 된다.

(위에서 만든 preorder 방식으로 test)

1> equal 함수

parameter로 node_pointer 2개(first, second)를 받는다.

두 node_pointer가 NULL이면 return

혹은 ||

[0] first와 second 모두 존재하는지 확인 &&

[1] 두 node_pointer의 data가 같은지 확인 &&

[2] 두 node_pointer의 왼쪽 child node_pointer를 equal 함수를 적용해서 true를 return하는지 && (재귀적으로 구현)

[3] 두 node_pointer의 오른쪽 child node_pointer를 equal 함수를 적용해서 true를 return하는지 && (재귀적으로 구현)

코드 작성

 

3) The Satisfiability Problem

0> satisfiability problem에 대한 소개

ex> '( x_1 A - x_2 ) V ( - x_1 A x_3 ) V -x_3 '이 True가 되도록 변수에 값을 지정할 수 있는지?

- The Satisfiability Problem : 주어진 식의 값이 True가 되도록 변수에 값을 지정할 수 있는 방법이 있는가?

- 변수(x_1, x_2, ... x_n)와 연산자(A, V, - ; 각각 and, or, not을 의미)로 이루어진 식

- 규칙

• 변수는 하나의 식이다.
• x, y가 각각 식이면, x와 y에 연산자를 가한 것(-x, xAy, xVy)도 식이다.
• 연산 순서는 -, A, V 순서이다. (괄호를 사용해서 연산 순서를 바꿀 수 있다.)

- 이러한 식을 계산하는데 시간 복잡도 = O(g*2^n)

(n개의 변수에 true of false 대입 = 2^n) (g : 변수에 값을 대입하고 식을 계산하는데 필요 시간)

- 식을 계산하는 방법 : 전체 식이 하나의 값이 될 때까지 subtree를 계산하면서 tree를 postorder traversal 한다.

- 주의 : '-'은 단항 연산자여서 오른쪽 node만 가진다.

 

1> node 구조 

- 연산자 우선순위 선언

- node struct는 [1] data (logical), [2] value (int), [3] left_child (node_pointer), [4] right_child (node_pointer)

- data : 시각화했을 때 node안에 들어간 연산자 혹은 변수의 값(True/False)

- value : node간 연산을 한 뒤에 얻어진 값 (True/False)  (True와 False만 있어서 int형으로 저장한다.)

 

코드 작성