자료구조 - 트리

기본적인 트리 구조

 

 

노드 : node

트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소

 

간선 : edge

노드와 노드를 연결하는 연결선

 

루트 노드 : root node

트리 구조에서 최상위에 존재하는 A와 같은 노드

 

단말 노드 : terminal node

아래에 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드

 

내부 노드 : internal node

단말 노드를 제외한 모든 노드로 A, B 와 같은 노드

 

서브트리로 구성된 큰 트리

다음 그림과 같이 트리는 작은 트리로 구성된다. 이 때 작은 트리는 서브트리라 부른다.

 

 

서브트리의 서브트리

또 서브트리는 서브트리로 나뉠 수 있다.

 

 

이진 트리

이진트리가 되기 위한 두 조건

● 루트 노드를 중심으로 두개의 서브 트리로 나뉘어진다.

● 나뉘어진 두 서브 트리도 모두 이진 트리여야 한다.

 

 

 

높이와 레벨의 정의

트리에서는 각 층별로 숫자를 매겨서 레벨이라 하고 트리의 최고 레벨을 높이라 한다.

 

 

포화 이진 트리

모든 레벨이 꽉 찬 이진트리를 포화 이진 트리라 한다.

 

 

완전 이진 트리

루트 노드부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드

순서대로 데이터가 차례대로 삽입되는 트리를 완전 이진 트리라 한다.

 

 

그냥 이진 트리

다음 트리는 포화 이진 트리도 아니고 빈 틈이 있기 때문에 완전 이진 트리도 아니다.

 

 

 

▼ 이진 트리 구현

헤더파일

 

함수 정의 및 메인 문

 

---

 

▼ 코드 설명

노드 생성 함수

노드의 left 와 right 는 NULL 로 설정 후 반환한다.

 

 

노드 데이터 출력 함수

노드의 데이터를 반환한다.

 

 

노드 데이터 입력 함수

노드의 데이터를 입력받은 data로 설정한다.

 

 

노드 왼쪽 서브트리의 노드 반환 함수

매개변수로 입력받은 bt 노드의 왼쪽 트리를 반환한다.

 

 

노드 오른쪽 서브트리의 노드 반환 함수

매개변수로 입력받은 bt 노드의 오른쪽 트리를 반환한다.

 

 

매개변수로 입력받는 main 의 왼쪽 서브트리를 sub로 설정하는 함수

main 의 left 노드가 존재할 경우 메모리 반환하고 sub로 설정한다.

 

 

매개변수로 입력받는 main 의 오른쪽 서브트리를 sub로 설정하는 함수

main 의 right 노드가 존재할 경우 메모리 반환하고 sub로 설정한다.

 

 

1. bt1, bt2, bt3, bt4 노드를 생성 후 

2. setData 함수를 통해 bt1 노드의 데이터에 1, bt2 노드의 데이터에 2, bt3 노드의 데이터에 3, bt4 노드의 데이터에 4 로 설정한다.

3. bt1 노드의 왼쪽 서브트리로 bt2 , bt1 노드의 오른쪽 서브 트리에 bt3, bt2 노드의 왼쪽 서브트리로 bt4 로 설정한다.

4. bt1 노드의 왼쪽 서브트리의 data 를 출력한다.

5. bt1 노드의 왼쪽 서브트리의 왼쪽 서브트리의 data 를 출력한다.

 

 

위 코드 실행 후 트리 모습

bt1 노드의 왼쪽 서브트리의 data 를 출력한다.

bt1 노드의 왼쪽 서브트리의 왼쪽 서브트리의 data 를 출력한다.