자료구조 <트리>

트리란?

계층적인 구조인 트리는 가족의가계도, 회사의 조직도, 컴퓨터의 디렉토리 구조, 인공지능 문제에서도 사용됩니다.

대표적인 것이 결정트리

트리의 예: 결정트리

 

---

트리의 용어들

트리의 용어

루트(root) : 계층적인 구조에서 가장 높은 곳에 있는 노드 : (A)

 

서브트리(subtree) : 루트노드를 제외한 나머지 노드들 : { (B,D,E,H,I,J) , (C,F,G) }

 

간선(edge) : 트리에서 루트와 서브트리는 선으로 연결됩니다. : 10개 (공식::노드의 개수-1)

 

부모노드(parent node) : 데이터 구조의 트리에서 모든 노드의 선행 노드인 노드를 부모 노드라고 하거나 자신에서 다른 연속 노드로 분기하는 노드를 부모 노드라고 합니다. : (A),(B),(C),(D),(E),(F),(G)

 

자식노드(children node): 트리에서 루트노드를 제외한 모든 노드들을 자식 노드라 할 수 있습니다. : B와 C는 A의 자식노드, D와 E는 B의 자식노드 , F와 G는 C의 자식노드, H와 I는 D의 자식노드, J는 E의 자식노드

 

형제관계(sibling) : 데이터 구조의 트리에서 동일한 부모에 속하는 노드를 형제라고 합니다. = 같은 계층내의 노드들 :{(B,C) , (D,E,F,G) , (H,I,J)}

 

조상노드(ancestor node) : 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드들 : G는 A와 C를 조상으로 부를 수있다. 하지만 G는 B를 조상으로 부를 수 없다.

자세한내용:https://stackoverflow.com/questions/10094991/basic-tree-concept-defining-ancestors#:~:text=A%20node's%20%22parent%22%20is%20a,is%20called%20an%20%22ancestor%22.

Basic Tree Concept: Defining ancestors

후손노드(descendent node) : 임의의 노드 하위에 연결된 모든 노드들을 의미한다. 어떤 노드의 서브 트리에 속하는 모든 노드들은 후속 노드이다.

 

단말노드(terminal node 또는 leaf node) : 자식 노드가 없는 노드 : (H),(I),(J)

 

비단말노드(nonterminal node) : 자식 노드가 있는 노드 : (H),(I),(J)를 제외한 모든 노드

 

차수(degree) : 어떤 노드가 가지고 있는 자식 노드의 개수 : (A)=2, (B)=2, (C)=2, (D)=2, (E)=1,

(F),(G),(H),(I),(J)=0

 

트리의 차수 : 트리가 가지고 있는 노드의 차수 중에서 가장 큰 값 : 2

 

레벨(level) : 트리 데이터 구조에서 루트 노드는 레벨 0에 있고 루트 노드의 자식은 레벨 1에 있으며 레벨 1에 있는 해당 노드의 자식은 레벨 2가 되는 식입니다.

 

트리의높이(height) : 트리가 가지고 있는 최대 레벨을 말합니다. 루트 노드에서 가장 먼 잎 노드까지 가장 긴 경로를 따라 있는 edge의 수입니다. : 위 사진의 트리높이는 3이다.

깊이(depth) : 트리에서 가장 긴 경로의 루트 노드에서 리프 노드까지의 총 edge 수를 "트리의 깊이"라고 합니다.

트리에서 루트 노드에서 특정 노드까지 많은 edge를 트리의 깊이라고 합니다.

---

트리의 종류

이진 트리(binary tree)

 이진트리의 정의 : 모든 노드의 차수가 2 이하이며, 이진 트리에는 서브트리간의 순서가 존재한다(left,right)

이진트리의 기초

1. 모든 노드의 차수가 2 이하가 된다 (공집합도 포함된다)

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

3. 이진트리의 서브트리들은 모두 이진트리여야 합니다.

 

위 1,2,3의 정의는 순환적인 이진트리알고리즘을 작성하기위해 아주 중요하게 사용됩니다.

---

이진트리의 분류

 

1. Perfect Binary Tree

포화 이진 트리는 모든 잎이 같은 깊이를 갖는 포화 이진 트리입니다.

높이 h의 포화 이진 트리는 n = 2^h+1-1개의 노드와 l = 2^h개의 잎을 가지고 있습니다. 

따라서 높이가 3인 트리는 15개의 노드와 8개의 잎을 가지고 있습니다.

 

2. Complete Binary Tree

완전한 이진 트리에서는 마지막 레벨을 제외한 모든 레벨이 완전히 채워집니다. 마지막 수준이 완전히 채워지지 않은 경우 해당 노드는 가능한 한 왼쪽으로 배열됩니다.

 

3. Full Binary Tree

전체 이진 트리에서 모든 노드에는 자식이 없거나 두 개의 자식이 있습니다.

 

4. AVL Tree (Balanced Binary Tree) 높이 균형 이진 탐색트리

균형 인수 = ( 왼쪽 서브 트리의 높이 - 오른쪽 서브트리의 높이 )

즉, 높이 균형 이진 탐색 트리는 모든 노드의 균형인수의 절댓값이 1 이하여야 함.

예를 들어 2를 인수로 가진 노드는 왼쪽 서브트리의 높이가 1 오른쪽 서브트리의 높이가 0이므로 균형인수는 1 이다.

---

링크 표현법

 

-기본 구조

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

-이진트리의 순회

전위순회

전위순회는 루트를 먼저 방문하고 그 다음에 왼쪽 서브트리를 방문하고 오른쪽 서브트리를 마지막으로 방문하는 것이다. 왼쪽 서브트리를 방문할때 왼쪽서브트리도 하나의 이진트리 이므로 전체트리와 똑같은 방식으로 서브트리를 방문하면됩니다.

void preorder(TreeNode* root)
{
	if(root!=NULL){
    		cout << root->data << " " ;
            preorder(root->left);
            preorder(root->right);
            }
 }

중위순회

중위순회는 먼저 왼쪽 서브트리,루트,오른쪽 서브트리 순으로 방문한다.

void inorder(Tree *node){
	if(root!=NULL){
				inorder(root->left);
				cout << root->data << " ";
				inorder(root->right);
           }
 }

후위순회

후위순회는 왼쪽 서브트리,오른쪽 서브트리, 루트 순으로 방문한다.

void postorder(TreeNode *root)
{
if(root!=NULL){
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
 }
}

지금까지 순회들은 스택을 이용한 방법이다. 순환적인 함수을 한건데 이게 왜 스택을 이용한방법이냐 할 수 있겠지만

순환호출도 사실은 시스템 스택을 사용하고 있는 것이기 때문에 별도의 스택을 사용하면 위와 같이 순환 호출을 흉내낼수 있다. 중위순회를 스택으로 이용한 한번 구현해보자.

#include <iostream>
#define SIZE 100
using namespace std;

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

TreeNode *stack[SIZE];
int top = -1;

void push(TreeNode *root) {
	if (top < SIZE - 1) {
		stack[++top] = root;
	}
}

TreeNode *pop()
{
	TreeNode *p = NULL;
	if (top > -1) {
		p = stack[top--];

	}
	return p;
}

void inorder_tra(TreeNode*root)
{
	while (1) {
		for (; root; root = root->left)
			push(root);
		root = pop();
		if (!root)break;
		cout << root->data << " ";
		root = root->right;

	}
}

TreeNode n1 = { 1,NULL,NULL };
TreeNode n2 = { 4,&n1,NULL };
TreeNode n3 = { 6,NULL,NULL };
TreeNode n4 = { 5,NULL,NULL };
TreeNode n5 = { 17,&n3,&n4 };
TreeNode n6 = { 13,&n2,&n5 };
TreeNode *root = &n6;

//inorder_tra(root) -> 1 4 13 6 17 5 출력됨

 

레벨순회

노드는 루트에서 시작하여 레벨별로 왼쪽에서 오른쪽으로 방문합니다.

노드를 레벨순서로 방문할려면 큐가 필요합니다. 먼저 루트에 방문하고 그 루트를 큐에 집어넣고 그런 다음 반복적으로 큐의 첫 번째 요소를 제거하고 방문하여 큐에 자식을 추가합니다.

void level_order(TreeNode *ptr)
{
if(ptr==NULL)return;
Queue<TreeNode*> queue;
queue.push(ptr);
while(!queue.empty())
{
	TreeNode* node = queue.pop();
    cout << node->data <<" ";
    if(node->left)
    	queue.push(node->left);
    if(node->right)
    	queue.push(node->right);
 }
 
 }

 

---

이진트리의 추가 연산

-노드의 개수

int get_node_count(TreeNode *node)
{
int count =0;
if(node!=NULL)
{
	count = 1+ get_node_count(node->left) + get_node_count(node->right) ;
 }
 return count;
 }

-단말 노드 개수 구하기

int get_leaf_count(TreeNode *node)
{
	int count =0;
    if(node!=NULL){
	if(node->left==NULL&&node->right==NULL)// 왼쪽자식과 오른쪽 자식이 둘다 NULL이면 단말노드이므로 1반환 
    	return 1; 
    else
    	count = get_leaf_count(node->left)+get_leaf_count(node->right);
        //만약 그렇지 않으면 비단말 노드이므로 왼쪽,오른쪽 서브트리에 대하여 순환호출한다음, 반환되는 값을 서로 더하면 된다.
     }
 return count;
 }

-높이 구하기

int get_height(TreeNode *node)
{
int height=0;
if(node!=NULL) height = 1+max(get_height(node->left),get_height(node->right));

return height;
}
//※여기서 결과값은 높이가 1이 더 크다.

---

스레드 이진 트리(c언어로 쉽게풀어쓴 자료구조)

이진 트리 순회는 순환 호출을 사용한다. 순환호출은 함수를 호출해야 되므로 시간복잡도를 생각하면

노드의 개수가 많아지고 트리의 높이가 커지게 되면 상당히 비효율적이다.

하지만 단말노드에 NULL대신 선행노드인 중위 선행자나 후속노드인 중위 후속자를 저장시켜 놓는 스레드 이진트리를

이용하면 된다.

중위후속자가 있는 스레드이진트리

 

typedef struct TreeNode{
	int data;
    struct TreeNode *left,*right;
    int is_thread; // true이면 노드의 right는 중위후속자이고 false이면 오른쪽 자식을 가르키는 포인터가 된다.
};

스레드 이진트리가 구성되었다고 가정하고 is_thread가 true로 되있으면 바로 오른쪽 자식이 중위 후속자가 되므로 오른쪽자식을 반환한다. 만약 오른쪽 자식이 NULL이면 더이상 후속자가 없다는 것이므로 NULL을 반환한다.

만약 is_thread가 false이며 NULL도 아니라면 서브트리의 가장 왼쪽 노드로 가야된다.

TreeNode* find_successor(TreeNode *P)
{
	TreeNode *q = p->right;
    if(q==NULL || p->is_thread ==True) 
    	return q;
    
    while(q->left !=NULL) q=q->left;
    return q;
 }

void thread_inorder(TreeNode *t)
{
	TreeNode *q;
    q=t;
    while(q->left) q=q->left; //가장 왼쪽 노드로 가기
    do{
    	cout << q->data;
        q= find_successor(q);
      }while(q);
  }

하지만 이 방법은 순회를 빠르게 하는 장점이 있으나 문제는 스레드를 설정하기 위하여 삽입이나 삭제함수가 더 많은 일을 하므로 비추합니다.

 

 

 

 

다음 시간엔 이진트리에 노드를 동적으로 삽입 그리고 트리의 노드를 삭제하는 방법을 자세히 알아보도록 하겠습니다.