[자료구조] 트리(Tree) 란? - 컴도리돌이

 

트리(Tree)란?

 

트리는 부모-자식 관계의 노드들로 이루어져있으며, 계층적인 구조를 나타내는 자료구조입니다.

응용분야로는 회사의 조직도, 컴퓨터의 폴더 구조 ,인공지능 바둑 프로그램의 거대한 결정 트리 , 등이 있습니다.

 

트리(Tree)의 용어 

트리의 용어1

노드(node) : 트리의 구성요소

루트(root) 부모가 없는 노드(A)

서브트리(subtree) : 하나의 노드와 자손들로 이루어짐

단말노드(terminal) : 자식이 없는 노드(E,FG,H,I,J)

비단말노드 : 자식을 가지는 노드(A,B,C,D)

 

트리의 용어2

레벨(level) :트리의 각층의 번호

높이(height) : 트리의 최대 레벨

차수(degree) : 노드의 자식 노드수

 

트리(Tree)의 종류

트리(tree)의 종류

이진트리(binary tree)

 

이진트리란 모든 노드가 2개의 서브트리를 가지고 있는 트리(tree)이다.

-서브트리는 공집합일 수 있다.

-각 노드에는 최대 2개까지의 자식 노드가 존재한다.

-모든 노드의 차수가 2 이하가 된다-> 구현하기가 편리함

-서브 트리간의 순서가 존재(왼쪽, 오른쪽)

 

이진트리(binary tree)

이진트리(binary tree)의 성질

-노드의 개수가 n개이면 간선의 개수는 n-1개이다.

-높이가 h이면 최소 h개 ~ 최대 2^h-1개의 노드를 가진다.

-n개의 노드의 이진트리 높이 : : 𝑙𝑜𝑔2(𝑛+1) ~ 𝑛

 

이진트리(binary tree)의 ADT

 

▪ init (): 이진트리를 초기화한다.
▪ is_empty (): 이진트리가 공백 상태인지 확인한다.
▪ create_tree (e, left, right): 이진트리 left 와 right 를 받아 e 를 루트로 하는 이진트리를 생성한다.
▪ get_root (): 이진트리의 루트 노드를 반환한다.
▪ get_count (): 이진트리의 노드의 수를 반환한다.
▪ get_leaf_count (): 이진트리의 단말 노드의 수를 반환한다. 
▪ get_height (): 이진트리의 높이를 반환한다.

 

연결리스트로 구현한 이진트리 && c언어

 

연결리시트로 구현한 이진트리(binary tree) 그림 예시

연결리스트로 구현한 이진트리(binary tree) && c언어 코드

 

구조체 트리 노드 안에 트리 노드의 left와 right를 포인터로 설정하고, 전역 변수로 root를 포인터로 설정하면 이진트리 구성은 기본적으로 표현할 수 있습니다. 추가적으로 트리를 초기화하는데에는 전역 변수 root를 null값을 주면 됩니다. 트리를 생성할 때는 새로운 노드를 동적 할당하여 값(value)와 left와 right를 직접 설정하여 새로운 노드를 반환(return) 해주면 됩니다. 사실 트리에서 제일 중요한 것은 순회와 이진 탐색 트리(Binary Search Tree) , 힙(heap)과 마지막 그래프(graph)이지만 단계적으로 트리부터 포스팅 했습니다~~