트리

개념 및 용어 

 

가지처럼 늘려가며 뻣어나가는 모양이라 Tree라는 이름이 붙음.

계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다.

비선형 자료구조

무언가를 표현하는 것에 적절한 구조 

 디렉터리 구조, 족보, 조직도, 의사결정 트리 등

 내가 사용한 것 : 다이나믹 메쉬의 뼈, 행동 트리, 쿼드 트리 등

 

노드 node : 트리의 구성요서에 해당하는 요소

간선 edge : 노드와 노드를 연결하는 연결선

루트 노드 root node : 트리 구조에서 최상위에 존재하는 노드

단말 노드 terminal node : 아래로 또 다른 노드가 연결되어 있지 않은 노드(이 ㅍ사귀 노드 leaf node)

내부 노드 internal node : 단말노드를 제외한 모든 노드 ( 비단말 노드 nonterminal node)

부모 노드 parent node : 특정 노드를 기준으로 상위에 있는 노드

자식 노드 child node : 특정 노드를 기준으로 하위에 있는 노드

형제 노드 sibling node : 특정 노드를 기준으로 같은 층에 위치한 노드 = 부모노드가 같은 노드

 

레벨 : 트리의 층 (루트 노드는 0레벨)

높이 : 트리의 최고 레벨

 

이진 트리 binary tree :

 루트 노드를 중심으로 두 개의 서브 트리로 나누어지는 노드, 나누어진 두 서브트리도 모두 이진트리어야한다.

 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브 트리, 그 서브트리의 모든 하위 서브트리는 이진 트리어야한다.

 노드가 위치할 수있는 곳에 노드가 존재하지 않는다면 공집합 노드가 존재하는 것으로 간주한다. 

  따라서 자식이 하나만 있는 경우더라도 이진 트리로 간주한다( 두 번째 자식은 공집합 노드로 비어있는 것으로 간주함)

 

서브트리

 큰 트리에 속하는 트리

 

포화 이진 트리(Full Binary Tree)

 공집합 노드가 없는 이진트리

 모든 레벨이 꽉 찬 이진 트리

 

완전 이진 트리(Complete Binary Tree)

 공집합 노드가 없는 이진트리

 

완전 이진 트리는 이진 트리의 부분집합이고, 

포화 이진 트리는 완전 이진트리의 부분집합인 개념이다.

 

포화 이진 트리 ⊂ 완전 이진 트리 ⊂ 이진 트리

 

 

 

 

 

이진 트리 구현

 

방법

 1. 배열 기반

   완전 이진 트리이며 트리가 완성 된 이후부터 그 트리를 대상으로 매우 빈번한 탐색이 이루어진다면 배열 기반이 유리하다 ( 탐색 속도가 더 빠름)

  heap 자료구조가 완전 이진트리를 배열 기반으로 구현한 자료구조이다.

 

 0번 인덱스는 비움 (사용할  수도 있지만 그렇지 않는 편이 구현에 편의를 주고 실수할 확류릉ㄹ 낮춰준다고한다)

 1번 인덱스는 루트 노드

 2번 인덱스는 루트 노드의 왼쪽 자식

 3번 인덱스는 루트 노드의 오른쪽 자식

 4번 인덱스는 2번 인덱스의 왼쪽 자식 

 ...

 

 

 2. 연결 리스트 기반

  표현이 유연하기 때문에 대부분의 트리는 연결 리스트 기반이다.

 

 

 

 

 

 

이진 트리 자료구조 ADT

 

// 이진 트리 노드를 생성하여 그 주소 값을 반환한다.

BTreeNode* MakeBTreeNode(void);

 

// 노드에 저장된 데이터를 반환한다.

BTData GetData(BTreeNode* bt);

 

// 노드에 데이터를 저장한다. data로 전달된 값을 저장한다.

void SetData(BTreeNode* bt, BTData data);

 

 

// 왼쪽 서브 트리의 주소 값을 반환한다.

BTreeNode* GetLeftSubTree(BTreeNode* bt);

 

// 오른쪽 서브 트리의 주소 값을 반환한다.

BTreeNode* GetRightSubTree(BTreeNode* bt);

 

// 왼쪽 서브 트리를 연결한다.

void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub);

 

// 오른쪽 서브 트리를 연결한다.
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub);

 

 

 

 

이진 트리의 순회 (Traversal)

 

이진트리의 순회 방법은 재귀적인 특성을 지닌다.

 

전위 순회 (Preoder Treaversal) : 루트 노드를 먼저 순회한다.

중위 순회 (Inoder Treaversal) : 루트 노드를 중간에 순회한다.

후위 순회 (Postoder Treaversal) : 루트 노드를 마지막에 순회한다.