[C++] 트리 #1 Tree

목차

1. 트리의 구성요소

2. 트리 구현

 

---

1. 트리의 구성요소

Tree는 컴퓨터 친화적인 선형 자료구조가 아닌 사용자 친화적인 비선형 계층 자료 구조이다.

사용자가 원하는 데이터를 얻기 쉽도록 데이터를 구분하여 연결해 준다.

ex) 컴퓨터 파일 경로, 회사 조직도

트리 예시

가. 노드(Node)

- 트리의 각 요소

- 데이터를 저장하고 다음 노드로 연결 시켜줄 주소 값이 저장되어 있다.

 

1) 루트 노드

- 트리 구조에서 최상위 노드 (트리 예시 기준 A)

- 부모 노드가 없음

 

2) 부모 노드

- 해당 노드와 연결 된 윗 노드 (트리 예시 기준 D와 E의 부모 노드 : B)

2-a) 조상 노드

- 해당 노드에서 루트 노드까지 경로 상의 윗 노드 들 (트리 노드 예시 기준 H의 조상 노드 : D, B, A)

 

3) 자식 노드

- 해당 노드와 연결 된 아랫 노드 (트리 예시 기준 C의 자식 노드 : F, G)

 

4) 형제 노드

- 해당 노드와 같은 부모를 둔 노드 (트리 예시 기준 D의 형제 노드 : E)

 

5) 단말 노드, 리프 노드

- 자식 노드가 없는 노드 (트리 예시 기준 : H, I, E, F, G)

 

6) 비 단말 노드, 가지 노드

- 자식 노드가 존재하는 노드 (트리 예시 기준 : A, B, C, D)

 

 

나. 간선(Edge), 가지(branch)

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

 

다. 깊이(Depth)

- 루트 노드에서 해당 노드까지 가는데 도착하는 간선의 수 (트리 예시 기준 D의 레벨 : 2)

 

1) 레벨(Level)

- 같은 깊이의 집합

 

2) 높이(Height)

- 해당 노드에서 가장 깊은 단말 노드까지 가는 간선의 수

- 레벨의 역순

 

라. 차수(Degree)

- 노드의 자식 갯수 (트리 예시 기준 D의 차수 : 2)

 

 

2. 트리 구현 (예시 기준 : 상단의 트리 예시)

 

가. 노드 구조체

  - 각 노드는 두개의 하위 노드로 향하는 링크 주소값을 가지고 있다. 

    (이진노드 기준, 하위 노드 갯수는 선언하는 만큼 늘릴 수 있다)

  - 현재 노드의 데이터 값 (key)를 지니고 있다.

 

 

 

 

 

 

 

 

나. 노드 생성

- 노드 구조체를 기준으로 새로운 노드를 생성 해 준다.

- key 값을 받아 저장한다.

 

 

 

 

다. 노드 탐색

- 탐색하고 싶은 _key 값의 위치를 current 변수에 저장해주는 함수

 

- _key값이 현재 탐색 중인 노드와 같지 않다면 하위 노드 (left, right)에서 재귀로 다시 탐색을 시도한다.

 

 

 

 

 

 

 

라. 3가지 운행 구조 (전위 순회, 중위 순회, 후위 순회)

 

1) 전위 순회

- 루트 노드 부터 시작하여 왼쪽 노드 부터 내려가며 순회한다.

- 내려가다 리프노드에 도달하면 부모 노드의 탐색하지 않은 노드에 대해 탐색한다.

- 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드

- 예시 기준 A-B-D-H-I-E-C-F-G

 

 

 

 

 

 

2) 중위 순회

- 왼쪽 자식 노드 부터 시작하여 부모 노드를 탐색하고 오른쪽 자식 노드를 탐색하는 순으로 순회한다.

- 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드

- 예시 기준 H-D-I-B-E-A-F-C-G

 

 

 

 

 

 

3) 후위 순회

- 자식 노드들을 모두 탐색 후 부모 노드를 탐색한다.

- 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드

- 예시 기준 H-I-D-E-B-F-G-C-A

 

 

 

 

 

 

 

마. 메인 함수 구현, 트리 내용 입력

 

- 현재 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 입력을 받는다.

- 0을 입력하면 입력을 종료하고 각 순회의 결과를 출력한다.

- '.'을 입력하면 해당 자식 노드가 없다는 뜻이다.

 

노드 실행 결과