[자료구조] 트리(Tree)

트리(Tree)

트리(Tree)는 원소들 간에 1 : N 관계를 가지는 비선형 자료구조이다. 

 

한 개 이상의 노드(node)로 이루어진 유한 집합으로서

• 노드 중에는 루트(root)라고 하는 노드가 하나 있고
• 나머지 노드들은 n(>=0)개의 분리집합 T1, ,,, Tn으로 분할될 수 있다. 여기서 T1, ,,, Tn은 각각 하나의 트리이며 루트의 서브트리(subtree)라고 한다.

한 노드의 서브트리의 수를 그 노드의 차수(degree)라고 한다.

예를 들어 트리의 구조가 다음과 같을 때, A의 차수는 3이고, C의 차수는 1, L의 차수는 0이다.

차수가 0인 노드를 리프(leaf) 또는 단말 노드(terminal node)라 한다.

그 외의 나머지 노드들은 비단말 노드(nonterminal node)라 한다.

 

노드의 높이(height)는 루트에서 노드에 이르는 간선의 수다.

루트의 레벨에 따라 높이가 달라지는데,  위 트리에서는 루트 노드의 레벨이 0이므로 높이가 3이 된다.

만일 한 노드의 레벨이 l이면 그 자식의 레벨은 l + 1이 된다.

 

트리의 리스트 표현

트리는 다음과 같은 리스트로 표현될 수 있다.

( A ( B ( E ( K , L ) , F ) , C ( G ) , D ( H ( M ), I, J ) )

루트 노드가 먼저 나온 후 서브 트리들의 리스트를 나열한 것이다.

위와 같이 리스트만 이용할 경우 공간 낭비가 심하다.

 

노드의 구조는 다음과 같다.

data
left child	right sibling

트리를 이러한 표현으로 바꾸기 위해서는 모든 노드라 하나의 가장 왼쪽 자식과 하나의 가장 오른쪽 형제를 가진다는 것에 주목해야 한다.

왼쪽 자식(left child) 필드는 자식이 있는 경우 가장 왼쪽 자식을 가리키며,

오른쪽 형제(right sibling) 필드는 오른쪽 형제가 있는 경우 가장 가까운 오른쪽 형제를 가리킨다.

위의 그림은 트리를 왼쪽 자식 - 오른쪽 형제 표현으로 다시 나타낸 것이다.

 

이진 트리(binary tree)

이진 트리는 공백이거나 루트와 왼쪽 서브트리, 오른쪽 서브트리라고 하는 두 개의 분리된 이진 트리로 구성된 노드의 유한 집합이다.

 

특징

• 한 노드가 최대 두 개의 가지만 갖는다는 것이 특징이다.  (즉, 차수가 2보다 큰 노드는 없다.)
• 이진 트리는 0개의 노드를 가질 수 있다. (그러므로 이진트리는 트리와 아주 다른 객체인 것이다.)
• 자식의 순서를 구분한다.

성질

• 이진 트리의 레벨 i에서의 최대 노드 수는 2^i-1 (i>=1)이다.
• 깊이가 k인 리진 트리의 최대 노드 수는 2^k-1 (k>=1)이다.

 

이진 트리의 종류

포화 이진 트리 (Full Binary Tree)

모든 레벨에 노드가 포화상태로 차 있는 이진 트리이다.

즉, 깊이가 k일 때, 최대 노드 개수인 2^k-1 (k>=0)의 노드를 갖는 이진 트리

그리고 노드 번호를 순차적으로 부여 가능하다.

 

완전 이진 트리 (Complete Binary Tree)

깊이가 k이고 노드 수가 n인 이진 트리이다.

n노드 완전 이진 트리의 높이: log2(n+1)

 

편향 이진 트리 (Skewed Binary Tree)

높이가 k일 때, k개의 노드를 가지면서 모든 노드가 왼쪽이나 오른쪽 중 한 방향으로만 서브 트리를 가지고 있는 트리이다.

 

이진 트리의 표현

배열을 활용한 표현

1차원 배열에 노드를 저장

- 인덱스 0번: 실제로 사용하지 않고 비워 둠

- 인덱스 1번: 루트 저장

 

완전 이진 트리: 낭비 되는 공간 없음

편향 이진 트리: 공간 낭비

 

연결 자료구조를 활용한 표현

 

<노드 표현>

left child

data

right child

 

<클래스 정의>

template <class T> class Tree; // 전방선언
template <class T>
class TreeNode{
friend class Tree<T>;
private:
	T data;
    TreeNode<T> *leftchild;
    TreeNode<T> *rightchild;
};

template <class T>
class Tree{
public:
	// 트리의 연산들
private:
	TreeNode<T> *root;
};

 

트리 순회 (Tree traversal)

• 트리에 있는 모든 노드를 한 번씩만 방문하는 것이다.
• 모든 가능한 순회 방법

LVR, LRV, VLR, VRL, RVL, RLV

• L과 R에 대한 V의 상대적 위치에 따라 아래의 세 가지 순회 방법이 있다. (왼쪽을 오른쪽보다 먼저 방문한다고 한정한 다면 다음과 같다.)

LVR: 중위(inorder) 순회

VLR: 전위(preorder) 순회

LRV: 후위(postorder) 순회

중위 순회 처리 

1.  왼쪽 서브 트리의 순회
2. 루트 노드(V)의 방문
3. 오른쪽 서브 트리의 순회

template <class T>
void Tree<T>::Inorder(TreeNode<T> *currNode) {
	if (currNode) {
    	Inorder(currNode->leftChild);
        Visit(currNode);
        Inorder(currNode->rightChild);
    }
}

수식 이진 트리를 중위 순회하면 수식에 대한 중위 표기식을 구할 수 있다.

 

전위 순회

template <class T>
void Tree<T>::Preorder(TreeNode<T> *currNode) {
	if (currNode) {
        Visit(currNode);
        Preorder(currNode->leftChild);
        Preorder(currNode->rightChild);
    }
}

후위 순회

template <class T>
void Tree<T>::Postorder(TreeNode<T> *currNode) {
	if (currNode) {
        Postorder(currNode->leftChild);
        Postorder(currNode->rightChild);
        Visit(currNode);
    }
}

레벨 순서 순회

template <class T>
void Tree<T>::LevelOrder() {
	Queue<TreeNode<T>*> q;
    TreeNode<T> *currentNode = root;
    while(currentNode) {
    	Visit(currentNode);
        if(currentNode->leftChild) q.Push(currentNode->leftchild);
        if(currentNode->rightChild) q.Push(currentNode->rightChild);
        if(q.IsEmpty()) return;
        currnetNode = q.Front();
        q.Pop();
    }
}