07-01 트리(Tree)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

 

 

 

1.트리(Tree)

 1)정의

  -노드들이 나무 가지처럼 연결된 비선형 자료구조이다.

 2)구성요소 및 용어

  -트리의 가장 최상단 노드를 뿌리라고 그외 하며 가지나 잎이라고 한다.

  -뿌리(Root): 최상단 노드

  -가지(Branch) ,잎(Leaf): 뿌리외에 하단 노드

   -깊이(Depth): 뿌리에서 데이터를 찾기 위해 이동한 노드의 개수

  -높이(Height): 가장 최하단 노드의 깊이.

  -레벨(Level): 깊이가 같은 노드의 집합

  -차수(Degree): 노드가 가지고 있는 자식의 개수

3)트리의 표현방법

 -괄호로 표현하기

 -집합으로 표현하기

4)노드의 표현방법

-N 링크 표현법

 노드의 차수가 N개이면 N개의 자식 노드의 연결을 가진다.

 이 연결 그대로 자식 노드를 가리키도록 하는 표현법

-왼쪽 자식 오른쪽 형제 표현법(Left Child-Right Sibling)

 두 개의 데이터로 한 쪽은 자식 노드 한쪽은 같은 깊이의 노드에 대한 정보로

 표현하는 방법