[DS]chapter8 트리 개념1

[8-1] 트리의 개요

트리를 이용하여 무엇인가를 저장하고 꺼내야한다는 생각은 지운다! 대신 무엇인가를 표현하는 도구라 생각!

 

*무언가 네트워크 처럼 생겼네. 노드도 있고 간선도 있고..

 

 이진트리(Binary Tree) 와 서브트리(Sub Tree)

 

- 이진 트리의 조건(*Binary니까 두개가 까지)

 

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

 

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

 

(*하나만 트리가 있어도 이진트리! 노드가 존재하지않는다면 공집합 노드가 존재한다고 판단한데)

 

 포화이진트리(Full Binary Tree) 와 완전 이진 트리 (Complete Binary Tree)

포화이진 트리 : 모든 레벨이 꽉 찬 이진 트리

완전이진 트리 : 포화 이진 트리 처럼 모든 레벨이 꽉차진않았지만 빈틈없이 노드가 채워진 상태 

+ 노드가 위에서 아래로, 그리고 왼쪽에서 오른쪽으로 순서대로 채워진상태

[8-2] 이진트리의 구현  

이진트리는 재귀적인 특성을 지니고있다.

 

이진트리의 구현 방법 : 배열 기반 OR 연결 리스트 기반

 

우선 배열기반

(*배열 기반은 연결 리스트에 비해서 탐색이 매우 용이하데)

(* 완전 이진 트리의 구조를 갖는 힙(Heap)이 라는 자료구조는 배열을 기반으로 구현해서 힙을 만족시키기가 배열이 훨씬 용이)

 

연결 리스트 기반 

 

- 헤더파일에 선언된 함수들의 기능

MakeBtreeNode 함수는 호출되면 다음형태의ㅣ 노드를 동적할당 및 초기화하여 그 주소값을 반환.

 

데이터가 저장되는 멤버 data를 대상으로 별도의 초기화를 진행하지않음

그러나 왼쪽 서브트리 오른쪽 서브트리를 가리키기 위한 멤버 left 와 right는 Null로 초기화

직접 돌려보고 마무리~.

 

<출처 -윤성우의 열혈 자료구조>