[자료구조]CH7. 트리 (트리의 이해~이진트리의 순회)

참조 : C로 배우는 쉬운 자료구조

공부날짜 : 2021.02.17

 

<Section1> 트리의 이해

 

 트리는 1:n 관계의 비선형 자료구조이자 계층 관계로 만들어진 계층형 자료구조이다.

트리를 구성하는 원소(자료)를 노드(Node) 라고 하고, 노드를 연결하는 선을 간선(Edge)이라고 한다.

 

트리의 시작노드, 가장 위의 0레벨의 노드를 루트(Root) 노드라고 한다.

부모 노드(상위 레벨)와 자식 노드(하위 레벨)는 간선으로 이어져 있고, 같은 부모를 가진 자식 노드들은 형제 노드가 된다. 한 노드에서 간선을 따라 루트 노드까지 이르는 경로의 모든 노드는 그 노드의 조상 노드이다.

각 노드의 자식 노드 수만큼 서브 트리를 가지며 이를 노드의 차수(Degree)라 한다.

차수가 0인 노드는 단말노드 또는 리프 노드라고 하고 차수가 1 이상인 노드는 내부 노드라고 한다. 

노드의 차수 중에서 가장 큰 값이 그 트리의 차수가 된다.

한 노드의 높이는 루트에서 그 노드까지의 간선의 수이고, 최대 높이는 트리의 높이가 된다. 

여러 개의 트리의 집합을 포리스트(Forest)라고 한다. 

 

<Section2> 이진 트리

 

1. 이진 트리의 개념과 구조 

 

 트리의 모든 노드의 차수를 2 이하로 제한하여 전체 트리의 차수가 2 이하가 되도록 정의한 것이 이진 트리이다.

공백 노드도 노드로 취급하며, 이때 이진 트리의 노드의 좌우는 구분되어 있어서 차수가 1이어도 왼쪽 자식 노드를 가지고 있느냐 오른쪽 자식 노드를 가지고 있느냐로 구분할 수 있다. 

또한 순환적으로 반복되어야 하므로 이진 트리의 각 서브 트리 역시 모두 이진 트리이다. 

 

<일반 트리를 이진 트리로 변환하는 방법>

 1) 루트부터 하위 레벨로 내려가면서 첫 번째 자식 노드로의 간선만 남겨두고 나머지의 자식 노드로의 간선을 제거

 2) 형제 노드끼리 간선으로 연결

 3) 시계 방향으로 45도 회전 

 

2. 이진 트리의 추상 자료형

 이진트리의 특징

 1) 노드가 n개인 이진 트리는 항상 간선이 (n-1)개이다.

 2) 높이가 h인 이진 트리가 가질 수 있는 노드의 개수는 최소 (h+1)이며, 최대 (2^(h+1)-1)개이다.

 

3. 이진 트리의 종류

 1) 포화 이진 트리 : 모든 레벨의 노드가 꽉 차서 높이를 늘리지 않는 한 노드를 추가할 수 없는 상태의 이진 트리이다.

 2) 완전 이진 트리 : 높이가 h이고 노드의 수가 n개이지만 최대의 노드 수를 가지고 있지 않는다. n< (2^(h+1)-1)

      노드의 위치가 포화 이진 트리에서의 노드 1번부터 n번까지의 위치가 일치한다. 즉, 그 이후부터는 공백 노드이다.

 3) 편향 이진 트리 : 높이가 h일 때 h+1개의 노드의 수를 가지고, 모든 노드가 왼쪽, 오른쪽 중 한 방향으로만 뻗어있다. 

 

<Section3> 이진 트리의 구현

 

1. 순차 자료구조를 이용한 이진 트리의 구현

 

 높이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 사용한다. 0번은 비우고 1번에 루트를 저장한다.

쉽게 만들 수 있고, 규칙으로 부모 노드와 자식 노드를 쉽게 찾을 수 있다. 하지만 편향 이진 트리의 경우에는 메모리 낭비가 일어난다.

노드	인덱스	성립 조건
노드 i의 부모 노드	i/2	i>1
노드 i의 왼쪽 자식 노드	2*i	(2*i)<=n
노드 i의 오른쪽 자식 노드	(2*i)+1	(2*i+1)<=n
루트 노드	1	n>0

2. 연결 자료구조를 잉요한 이진 트리의 구현

 

 연결 자료구조인 포인터를 이용한다. 데이터 필드, 왼쪽 자식 링크를 연결하는 왼쪽 링크 필드와 오른쪽 자식 링크를 연결하는 오른쪽 링크 필드로 구성되어 있다. 자식 노드가 없으면 NULL을 저장한다.

 

typedef struct treeNode {

     char data;

     struct treeNode *left;

     struct treeNode *right;

 } treeNode;

 

<Section4> 이진 트리의 순회

 

1. 이진 트리의 순회의 개념

 

 순회란 모든 원소를 빠뜨리거나 중복하지 않고 처리하는 연산을 의미한다, 이진 트리는 1: 2의 비선형 계층 구조이기 때문에 순회 연산이 필요하다. 

 

작업 D : 현재 노드를 방문하여 처리한다.

작업 L : 현재 노드의 외쪽 서브 트리로 이동한다.

작업 R : 현재 노드의 오른쪽 서브 트리로 이돟한다.  

 

2. 전위 순회 (D-L-R)

 

 preorder(T)

      if (T!=NULL) then {

         visit T.data;

         preorder(T.left);

         preorder(T.right);

      }

 end preorder()

 

3. 중위 순회 (L-D-R)

 

 inorder(T)

      if (T!=NULL) then {

         inorder(T.left);

         visit T.data;

         inorder(T.right);

      }

 end inorder()

 

4. 후위 순회 (L-R-D)

 

 postorder(T)

      if (T!=NULL) then {

         postorder(T.left);

         postorder(T.right);

         visit T.data;

      }

 end postorder()

 

5, 스레드 이진 트리

 

 재귀 호출 없이 순회할 수 있도록 수정한 이진 트리이다. 

자식 노드가 없으면 링크 필드에 순서 상의 다음 노드를 가리키도록 설정하는데, 이런 링크 필드를 스레드라고 한다.

스레드의 왼쪽 링크 필드는 선행자, 오른쪽 링크 필드에는 후행자에 대한 포인터를 저장한다.

순회 방법에 따라 경로가 달라지므로 미리 방법을 정한 후 경로에 따라 스레드를 설정한다.

 

typedef struct treeNode {

     char data;

     struct treeNode *left;

     struct treeNode *right;

     int isThreadLeft;

     int isThreadRight;

 } treeNode;

 

isThread 필드는 true나 false를 통해 자식 노드 대신 스레드가 저장되었는지 구별하기 위함이다.