[ 자료구조 ] 트리와 이진트리의 개념과 구조 - C언어

트리 Tree

트리 : 원소들 간에 1:n 관계를 가지는 비선형 자료구조, 원소들 간에 계층 관계를 가지는 계층형 자료구조, 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조

트리는 하나의 루트 노드를 가지며 각 자식 노드와 부모 노드는 간선(edge)로 연결되어 있다.

 

트리의 이해

트리의 구조 F가 루트 노드

차수

노드의 차수 : 노드에 연결된 자식 노드의 수. ex ) 위 노드를 예로 들어 F의 차수는 2, G의 차수는 1, H의 차수는 0

트리의 차수 : 트리에 있는 노드의 차수 중 가장 큰 값  ex ) 위 트리의 차수는 2

단말 노드 : 차수가 0인 노드. 자식 노드가 없는 노드.  ex ) 위 노드에서는 A, C, E, H가 해당

 

높이

노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨  ex ) B의 높이는 1, E의 높이는 3

트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨  ex ) 위 트리의 높이는 3.

 

포리스트 Forest

: 서브 트리의 집합

ex ) 아래 트리에서 루트 노드 A를 제거하면 A의 자식 노드 B와 C에 대한 서브 트리가 생기고 이들의 집합은 포리스트가 됨.

서브 트리 예시

 

이진트리 Binary Tree

: 트리의 모든 노드의 차수를 2 이하로 제한하여 전체 트리의 차수가 2이하가 되도록 정의. 이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드만 가짐. 공백 노드도 자식 노드로 취급하기 때문에 노드의 차수는 0 이상 2 이하.

이진트리 예시

이진 트리의 특성

: 노드가 n개인 이진 트리는 항상 간선이 n-1개이다.  ex ) 위 트리 중 부모 노드 36을 서브 트리로 봤을 때, 노드가 36, 25, 1 총 세 개일 때 간선의 갯수는 2개이다.

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

 

이진 트리의 종류

포화 이진 트리 Full Binary Tree

: 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리. 높이가 h일 때, 최대 노드 개수인 2^(h+1)-1d의 노드를 가진 이진 트리.

완전 이진 트리 Complete Binary Tree

: 높이가 h이고 노드 수가 n개 일 떼, 노드 위치가 포화 이진 트리에서의 노드 1번 부터 n번까지의 위치와 완전히 일치하는 이진 트리. 간단히 말해서, 자식노드가 왼쪽부터 차례대로 채워져 있는 트리이다.

완전 이진 트리 예시

왼쪽 트리는 자식노드가 왼쪽부터 차례대로 채워져 있기에 완전 이진 트리지만, 오른쪽 트리는 왼쪽 자식 노드가 비워져 있으므로 완전 이진 트리가 아니다. 왼쪽 트리에서 노드 3에도 자식 노드가 꽉 차 있다면 포화 이진 트리.

편향 이진 트리 Skewed Binary Tree

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

 

편향 이진 트리 예시

 

이진 트리 구현

연결 자료 구조를 이용한 이진 트리 구현

:  저장하는 데이터 필드, 왼쪽 자식 노드를 연결하는 왼쪽 링크 필드, 오른쪽 자식 노드를 연결하는 오른쪽 링크 필드로 구성. 자식 노드가 없으면 링크 필드에 NULL 저장.

typedef struct treeNode {
    int data;
    struct treeNode *left;
    struct treeNode *right;
} treeNode;

이진 트리 노드의 구조체 정의

연결 자료 구조로 구현한 완전 이진 트리

 

이진 트리의 순회 개념

: 모든 원소를 빠트리거나 중복하지 않고 처리하는 연산을 의미

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

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

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

위의 작업 순서에 따라 전위 순회 DLR, 중위 순회 LDR, 후위 순회 LRD로 나눔.

순회 예시

전위 순회 순서 : 20-15-10-4-12-17-19-28-26-33-30-35

중위 순회 순서 : 4-10-12-15-17-19-20-26-28-33-30-35

후위 순회 순서 :  4-12-10-19-17-15-26-30-35-33-28-20

수식 A*B-C/D를 이진 트리로 만든 후, 순회하면 표기식을 구할 수 있음

전위 순회 후 전위 표기식 : -*AB/CD

중위 순회 후 중위 표기식 : A*B-C/D

후위 순회 후 후위 표기식 : AB*CD/-

 

다음 글에서 이진 탐색 트리에 키를 탐색, 삽입, 삭제하는 방법 알아볼 예정 👇🏻

https://tildacoderecorder.tistory.com/105

[ 자료구조 ] 이진 탐색 트리의 탐색/삽입/삭제 연산 - C언어

 

참고 : C로 배우는 쉬운 자료구조 / 이지영 / 한빛아카데미