Tree Traversal(트리의 순회)

Tree

트리는 노드와 링크를 이용한 자료구조이다.

트리는 일반적으로 컴퓨터나 일상에서도 많이 사용되는 구조이다.

회사의 조직도나 컴퓨터의 폴더 같은 경우가 이를 사용하는 대표적인 예시이다.

트리 구조는 다른 알고리즘들보다 자료의 저장과 검색에 대해서는

메모리를 월등하게 사용할 수가 있어서 개발에 있어서 많이 사용이 된다.

 

용어

트리에 대해 얘기하기 전에 트리에 관련된 용어들에 대해서 먼저 알고 있어야 한다.

 

 

일반적으로 트리는 위와 같은 형태를 말한다.

A노드를 기준으로 여러 가지 노드들이 연결이 되어있다.

링크드 리스트와 동일하게 링크로 연결이 되어있지만,

앞과 뒤를 이어주는 링크드 리스트와는 약간은 다른 점을 갖는다.

 

위의 노드들에서 볼 수 있다시피 몇몇 용어들이 적혀있다.

 

Root Node

연결된 노드들이 한 군데로 모이는 노드를 root node라고 한다.

 

Degree

노드 하나에 연결되어 있는 노드의 수를 나타낸다.

차수가 2개 이하로 이루어진 트리를 이진트리라고 한다.

 

Parent Node

현재의 노드의 바로 상위 노드를

부모 노드라고 한다.

한 노드의 부모 노드가 2개 이상인 경우는 없으며

2개 이상인 경우 트리가 될 수가 없다.

 

Child Node

현재의 노드의 하위에 있는 노드들을

자식 노드라고 한다.

 

Sibling Node

같은 부모 노드를 갖는 노드를 형제 노드라고 한다.

 

Leaf Node

트리 구조의 끝단에 있는 노드를 리프 노드라고 한다.

 

Level

레벨은 루트 노드로부터 해당 노드까지의 경로를 나타내는 수가 된다.

위의 노드에서 H의 레벨은 4가 된다.

 

Depth

트리의 최대 깊이를 Depth라고 한다.

 

 

 

이진트리

 

이진트리는 자식 노드를 2개 이하만 갖는 트리이다.

2개 이하의 노드만 가지므로 구현이 쉽고,

이중 링크드 리스트와 비슷하게 두 개의 링크를 한다.

링크드 리스트와 다르게 좌우로 노드가 있어서

아래와 같이 left, right로 링크의 이름을 변경한다.

typdef struct _Node{
    char Data;
    struct _Node *left;
    struct _Node *right;
} Node;

 

추가로 이진 트리에 나오는 몇 가지 종류를 설명하겠다.

 

왼쪽으로 기울어진 이진트리로

리프 노드를 제외한 모든 노드가 왼쪽의 자식 노드만 갖는다.

 

오른쪽으로 기울어진 이진트리로

왼쪽으로 기울어진 이진트리와 개념이 반대라고 생각하면 된다.

 

 

완전 이진트리는

모든 노드가 2개의 자식 노드를 갖거나

자식 노드를 갖지 않는 트리를 뜻한다.

 

 

 

정 이진트리는

리프 노드들의 레벨이 같아야 한다.

 

 

 

 

 

 

.

.

.

.

 

트리에서는 노드를 순회하는 방법이 여러 가지가 있다.

많은 방법들이 존재하지만 크게는 네 가지가 있다.

 

전위 순회-(깊이 우선 순회)

중위 순회-(대칭 순회)

후위 순회

단계 순회-(너비 우선 순회)

 

 

 

전위 순회

 

루트 노드에서부터 리프 노드가 나올 때까지 왼쪽 하단으로 이동한다.

리프 노드가 나오게 되면 리프 노드의 형제 노드가 있는지 확인을 한다.

있을 경우 방문을 하게 된다.

이후 부모 노드와 같은 레벨의 노드를 방문을 한다.

그다음부터는 전과 동일하다.

 

주요 코드는 아래와 같이 진행된다.

void preorder_traverse(NODE *ptrNode){ //arg ptrNode->left
	
    Push(ptrNode);
    
    while(!isStackEmpty()){
    	ptrNode = Pop();
        Visit(ptrNode); //printf("%c ->", ptrnode->Data);
        
       	if(ptrNode->right != endNode){
        	Push(ptrNode->right);
        }
        
        if(ptrNode->left != endNode){
        	Push(ptrNode->left);
        }
        
    }
}

출력 순서

A -> B -> D -> E -> C -> F -> G

 

 

 

중위 순회

맨 왼쪽 하단에 있는 리프 노드부터 시작이 된다.

그 이후 리프 노드의 부모 노드를 방문한 뒤 형제 노드가 있을 시 방문한다.

다음으로 2번의 부모 노드로 이동을 한다.

동일하게 4번 노드의 오른쪽 자식 노드들 중 가장 왼쪽 하단에 있는 리프 노드에 방문한다.

이후 과정은 동일하다.

 

재귀 호출을 이용한 중위 순회

void Recursive_Traverse(Node *ptrNode){ //arg ptrNode->left
	if(ptrNode != endNode){
    	Recursive_Traverse(ptrNode->left);
        Visit(ptrNode); //printf("%c ->", ptrnode->Data);
        Recursive_Traverse(ptrNode->right);
    }
}

스택을 이용한 중위 순회

void Stack_Traverse(NODE *ptrNode){ //arg ptrNode->left
	int finish = 0;
    do{
    	while(ptrNode != endNode){
        	Push(ptrNode);
            ptrNode = ptrNode->left;
        }
        
        if(!isStackEmpty()){
        	ptrNode = Pop();
            Visit(ptrNode); //printf("%c ->", ptrnode->Data);
            ptrNode = ptrNode->right;
        }else
        	finish = 1;
    }while(!finish);
    
}

출력 순서

D -> B -> E -> A -> F -> C -> G

 

 

후위 순회

맨 왼쪽 하단의 리프 노드에 방문한다.

그다음 형제 노드가 있을 시에 방문을 한다. 방문을 한 뒤 부모 노드로 이동을 해서 방문을 한다.

이후 B와 같은 레벨의 노드로 이동을 한 후 자식 노드 중 왼쪽에 있는 리프 노드를 방문한다.

그 이후 과정은 동일하다.

 

후위 순회도 동일하게 두 가지로 구현이 가능하다.

 

재귀 호출을 이용한 후위 순회

void Recursive_Traverse(Node *ptrNode){ //arg ptrNode->left
	if(ptrNode != endNode){
    	Recursive_Traverse(ptrNode->left);
        Recursive_Traverse(ptrNode->right);
        Visit(ptrNode); //printf("%c ->", ptrnode->Data);
    }
}

 

스택을 이용한 후위 순회

void Stack_Traverse(NODE *ptrNode){ //arg ptrNode->left
	int finish = 0;
    NODE *ptrVisited = endNode;
    Node *ptrPushed = endNode;
    
    do{
    	while(ptrNode != endNode && ptrNode != ptrVisted){
        	if(ptrNode != ptrPushed){
            	Push(ptrNode);
            }
            if(ptrNode->right != endNode){
            	Push(ptrNode->right)
            }
            if(ptrNode->left != endNode){
            	Push(ptrNode->left)
            }
            
            ptrNode   = ptrNode->left;
            ptrVisted = ptrNode->left;
        }
        
        if(!IsStackEmpty()){
        	ptrNode = Pop();
            
            if(ptrNode->left!=endNode && ptrNode->right==endNode && ptrNode->left!=ptrVisited){
            	# When Tree unbalanced
                Push(ptrNode);
                ptrNode = ptrNode->left;
            }
            if(ptrNode->right==endNode || ptrNode->right==preVisited){
            	Visit(ptrNode); //printf("%c ->", ptrnode->Data);
                preVisited = ptrNode;
            }     
        }else{
        	finish = 1;
        }
    }while(!finish);
}

 

출력 순서

D -> E -> B -> F -> G -> C -> A

 

 

 

단계 순회

 

레벨 순서대로 왼쪽에서부터 오른쪽으로 차례대로 방문을 하는 것을 단계 순회라고 한다.

단계 순회는 스택이나 재귀 호출을 이용하기보다는 큐를 이용해서 구현하는 것이 쉽다.

큐 중에서도 원형 큐를 이용을 하는 것이 활용성면에서 좋으므로 원형 큐를 이용해서 작성한다.

 

void Level_Treverse(NODE *ptrNode){ //arg ptrNode->left
	Put(ptrNode);
    while(!IsQueueEmpty()){
    	ptrNode = Get();
        Visit(ptrNode); //printf("%c ->", ptrnode->Data);
		
        if(ptrNode->left!=endNode){
        	Put(ptrNode->left);
        }
        if(ptrNode->right!=endNode){
        	Put(ptrNode->right);
        }
    }
}

# Circular Queue
/*
void Put(Node *ptrNode){
	Queue[rear] = ptrNode;
    rear = (rear++) % MAX;
}

NODE *Get(void){
	NODE *ptrNode;
    
    if(!IsQueueEmpty()){
    	ptrNode = Queue[front];
        front   = (front++) % MAX;
        
        return ptrNode;
    }else{
    	print("Empty");
    }
    
    return NULL;
}
*/

 

출력 순서

A -> B -> C -> D -> E -> F -> G

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

해당 글은 알고리즘 문제 풀이 전략을 기반으로 작성되었음을 알려드립니다.