노드 : 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 의 left 노드가 존재할 경우 메모리 반환하고 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 를 출력한다.
'CS > 자료구조' 카테고리의 다른 글
자료구조 - 우선순위 큐 (0) | 2024.01.22 |
---|---|
자료구조 - 트리 순회(전위/중위/후위) (0) | 2024.01.22 |
자료구조 - 큐(배열 기반) (0) | 2024.01.17 |
자료구조 - 전위/중위/후위 표기법 (0) | 2024.01.16 |
자료구조 - 스택(연결 리스트 기반) (0) | 2024.01.16 |