자료구조 트리(Tree) 기초 개념정리

트리(Tree)

트리는 비선형 자료구조로서 계층적 관계를 표현하는 자료구조 입니다.

트리구조의 예시: 기업의 조직도, 컴퓨터의 디렉토리 구조 (가지를 늘려가면서 뻗어나가는 특성을 가지는 구조들)

이진트리(Binary Tree)

이진트리는 루트노드를 중심으로 두개의 서브 트리로 나누어지는 트리로서, 나누어진 두개의 서브트리 역시 이진트리여야 합니다. (=자식노드가 2개씩 있는 트리)

이진트리는 노드가 위치할 수 있는 위치에 노드가 없다면 공집합 노드가 있는 것으로 간주합니다. 때문에 서브트리가 하나인 노드가 존재하더라도 이진트리가 될 수 있습니다.

이진트리의 일부 연산은 재귀호출을 사용합니다.

이진트리는 배열기반 및 연결리스트 기반으로 구현할 수 있습니다.

포화이진트리(Full Binary Tree): 모든 레벨이 가득 차 있는 이진트리 입니다. (= 공집합이 없는 이진트리)

완전이진트리(Complete Binary Tree): 모든 레벨이 가득 차 있지는 않지만 빈틈없이 노드가 채워져 있는 이진트리로서 위 -> 아래 및 왼쪽 -> 오른쪽 순서로 빈틈이 없는 이진트리입니다.

---

트리관련용어

노드: 트리의 구성요소

루트노드: 트리구조에서 최상위의 위치한 노드

단말노드: 자신의 아래에 또 다른 노드가 연결되어 있지 않은 노드

내부노드(비단말노드): 단말노드외의 나머지 노드

간선: 노드들을 연결하는 연결선

레벨: 트리의 각층을 표현한다. 루트노드는 0이며, 내려갈수록 레벨이 1 증가합니다. 

높이: 트리의 최고레벨을 높이라고 표현합니다.

이진트리의 ADT (추상자료형)

MakeBTreeNode: 이진트리노드의 생성하며, 주소값을 반환합니다.

GetData: 노드에 저장된 데이터를 반환합니다.

SetData: 노드에 데이터를 저장하는 함수로서, 매개변수로 전달된 값을 저장합니다.

GetLeftSubTree: 왼쪽 서브트리의 주소값을 반환합니다.

GetRightSubTree: 오른쪽 서브트리의 주소값을 반환합니다.

MakeLeftSubTree: 왼쪽 서브트리를 연결하는 함수입니다.

MakeRightSubTree: 오른쪽 서브트리를 연결하는 함수입니다.