[자료구조] 트리 - 이진트리, 순회

정의

트리 중에서 가장 많이 쓰이는 트리로, 모든 노드가 2개의 서브 트리를 가진다.

서브트리는 공집합 일 수 있다. (공집합 또한 이진트리이다.)

이진트리의 노드에는 최대 2개까지의 자식노드가 존재할 수 있고, 모든 노드의 차수가 2 이하이다.

 

이진트리에는 서브트리간의 순서가 존재한다. (즉 왼쪽과, 오른쪽이 구별된다)

 

1. 공집합이거나

2. 루트와 왼쪽 서브트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합.

 

성질

n개의 노드를 가진 이진트리는 정확히 n-1 개의 간선(edge) 를 가진다. 왜냐하면 이진트리에서 노드는 루트를 제외하면 정확히 하나의 부모노드를 가지기 때문이다. (부모와 자식간에는 1개의 edge 만이 존재한다)

 

높이가 h 인 이진트리의 경우, 최소 h 개의 노드를 가지며 최대 2^h -1 개의 노드를 가진다.

즉 n 개의 노드를 가지는 이진트리의 높이는 최대 n 이거나 log_2(n+1) 이 된다.

 

분류

• full binary tree (포화 이진 트리)
• complete binary tree (완전 이진 트리)
• 기타 이진 트리

full binary tree

각 레벨에 노드가 꽉 차있는 이진트리이다. 위 와 같이 노드에 번호를 붙일 수 있다. (왼쪽 부터 오른쪽) 이 번호는 항상 일정하다. 즉, 루트의 오른쪽 자식 노드는 항상 3번이다.

 

Complete binary tree

완전 이진트리는 높이가 k일 때 레벨벨 k-1 까지는 포화이진트리이고, 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리이다.

즉 위 그림에서 L 노드가 F 의 오른쪽 자식 노드에 위치한다면, 완전 이진트리가 아니다.

 

이진트리의 표현

배열을 이용

https://www.youtube.com/watch?v=0iHD18D072c

노드 i 의 부모 노드 인덱스 = i/2

노드 i의 왼쪽 자식 노드 인덱스 = 2i

노드 i의 오른쪽 자식 노드 인덱스 = 2i+1

 

링크를 이용

https://math.hws.edu/eck/cs124/javanotes5/c9/s4.html

typedef struct TreeNode {
	int data;
    struct TreeNode *left, *right;
} TreeNode;

int main(){
	TreeNode *n1, *n2, *n3;
    n1 = (TreeNode*)malloc(sizeof(TreeNode));
    n2 = (TreeNode*)malloc(sizeof(TreeNode));
    n3 = (TreeNode*)malloc(sizeof(TreeNode));
    
    n1->data = 10;
    n1->left = n2;
    n1->right = n3;
    
    n2->data = 20;
    n2->left = NULL;
    n2->right = NULL;
    
    ...

이진트리의 순회(traversal)

스택이나 큐등은 데이터를 선형으로 가지고 있기 때문에 자료를 순차적으로 순회하는 방법은 하나뿐이었지만, 트리느 ㄴ그렇지 않다.

 

전위순회(preorder traversal) : VLR

VLR 은 순회환경을 나타내는 용어로, V는 루트노드 L은 왼쪽 서브트리, R은 오른쪽 서브트리를 의미한다.

즉 전위 순회는 루트 부터 시작해서 왼쪽 서브트리를 다 탐색한 다음 오른쪽 서브트리로 넘어간다는 뜻이다.

preorder(x):
	if x != NULL then
    	print DATA(x);
        preorder(LEFT(x));
        preorder(RIGHT(x));

 

중위순회 (inorder traversal) : LVR

inorder(x):
	if x != NULL then
    	inorder(LEFT(x));
        printf(DATA(x));
      	inorder(RIGHT(x));

후위순회 (postorder traversal) : LRV

postorder(x):
	if x != NULL then
    	postorder(LEFT(x));
        postorder(RIGHT(x));
        print(DATA(x));

 

반복적 순회

위 방식들은 시스템 스택을 사용하지만, 별도의 스택을 구현해서 순환호출을 흉내낼 수도 있다.

아래 코드는 중위순회 (LVR) 을 흉내내는 예시이다.

void inorder_iter(TreeNode *root){
	while(1) {
		for (; root; root=root->left)
        	push(root)
        root = pop();
        if (!root) break;
        printf("[%d] ", root->data);
        root = root->right;
    }
}

 

레벨순회 (level order traversal)

표준적인 순회방법은 아니지만, 각 노드를 레벨 순으로 검사하는 순회 방법이다.'

지금까지의 순회방식이 스택을 사용함에 반해, 레벨 순회는 큐를 사용한다.

https://java2blog.com/binary-tree-level-order-traversal-java/

 

순회 방법 선택

순서는 중요치 않고 노드를 전부 방문하기만 하면 된다면, 전위 중우 후위 중 아무것이나 택해도 된다.

자식노드를 처리한 다음에 부모 노드를 처리해야한다면 후위순위를 사용해야 한다.

부모노드를 처리한 다음에 자식 노드를 처리해야 한다면 전위순회를 사용해야 한다.