트리와 이진트리

트리 

- 계층적인 구조를 표현

- 조직도

- 디렉토리와 서브디렉토리 구조

- 가계도

트리 용어

트리 : 노드들과 노드들을 연결하는 링크로 구성

링크 : 노드와 노드들을 연결

루트 : 맨위의 노드

노드 : 부모 노드와 자식 노드가 존재, 부모 노드와 링크되며 밑에 있는 노드를 자식노드라고 함

서브트리 : 한 노드와 그 노드의 자손들로 이루어진 트리

레벨 : 트리의 층 별로 트리의 1층,2층... 으로 만든다.

 

트리의 기본적인 성질

- 노드가 n개인 트리는 n-1개의 링크를 갖는다.

- 루트에서 어떤 경로로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다.

 

이진 트리

- 이진 트리에서 각 노드는 최대 2개의 자식을 갖는다.

- 각각의 자기 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정된다.

- 같은 데이터라도 자식이 오른쪽에 있느냐 왼쪽에 있느냐에 따라 다른 트리가 된다.

이진트리 예시

- full and complete binary trees

full binary tree는 이진트리인데 노드가 다 있는 트리이다.

complete binary tree는 만약 노드들이 다 채워져있지 않다면 오른쪽부터 비어있는 트리이다.

- 높이가 h인 full binary tree는 2^h-1개의 노드를 갖는다.

- 노드가 n개인 full 혹은 complete 이진트리의 높이는 o(logn)이다.

 

-연결구조 표현

- 각 노드에 하나의 데이터 필드와 왼쪽 자식, 오른쪽 자식, 그리고 부모노드의 주소를 저장

** 대체로 트리는 루트에서 밑으로 내려가기 때문에 부모노드의 주소가 필요한 경우가 아니라면 보통 생략한다.

**루트 노드의 주소는 따로 보관한다!!

 

이진트리의 순회

- 순회 : 이진 트리의 모든 노드를 방문하는 일

- 중순위 순회(inorder)

- 선순위 순회(preorder)

- 후순위 순회(postorder)

- 레벨오더 순회

중순위 순회(inorder)

1. 먼저 왼쪽 부트리를 순회하고 

2. r을 순회하고

3. 오른쪽 부트리를 순회한다.

 

선순위 순회(preorder)

1. r을 순회하고

2. 왼쪽 부트리를 순회하고

3. 오른쪽 부트리를 순회한다.

 

후순위 순회(postorder)

1. 먼저 왼쪽 부트리를 순회하고 

2. 오른쪽 부트리를 순회하고

3. r을 순회한다.

 

중순위 : 2,3,5,5,7,8

선순위 : 5,3,2,5,7,8

후순위 : 2,5,3,8,7,5

 

*중순위 수도코드 - 시간복잡도 : o(n)

*선순위 수도코드

*후순위 수도코드

 

level-order 순회

- 레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로

- 큐를 이용하여 구현

1. 3을 출력하면 큐에 넣는다.

2. 3을 빼면서 3의 자식들을 큐에 넣는다.

3. 1,2를 반복한다.

* level-order 순회 수도코드

* 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다.