[고2 자료구조] 2학기 1차

 

트리(tree)

각각의 자료들을 계층적으로 서로 연결한 자료 구조

 

트리의 특징

• 상위 원소에서 하위 원소로 내려가면서 확장되는 나무 모양 구조
• 노드와 연결된 노드들 사이에는 부모와 자식 관계가 있다.(계층적 구조)
• 한 방향으로만 연결되어 있고, 자식 노드는 반드시 하나의 부모만 갖는다.
• 여러 노드가 한 노드를 가리킬 수 없는 구조이다.

 

트리 용어

※ 레벨, 높이, 깊이 주의

간선(edge)	노드와 노드의 연결
노드(node)	트리를 구성하는 요소 하나하나
루트(root node)	트리의 시작 노드. 부모가 없는 노드. 트리는 하나의 루트 노드만을 가진다.
단말 노드(leaf node)	자식을 갖지 않는 노드
부모(Parent Node)	특정 노드의 바로 위에 있느 노드
자식(Child Node)	특정 노드의 하위에 있는 노드
형제(Sibling Node)	같은 부모를 가지는 노드
깊이(Depth)	루트 노드에서 자신까지 가는 경로의 길이(즉, edge의 개수)
레벨(Level)	루트를 레벨1로 하고 그 자식노드는 +1
노드의 차수(degree)	임의의 노드가 갖는 자식 노드의 수
트리의 차수	각 노드의 차수 중 최댓값
숲(forest)	루트를 제거했을 때 생기는 서브 트리

 

---

 

이진 트리(binary tree)

모든 노드의 차수가 2 이하인 트리

 

이진 트리의 성질

• 이진 트리에서 노드의 개수를 $n$개로 정의하였을 때, 간선의 개수는 항상 $n-1$개를 가진다.
• 높이가 h일 때 노드의 최소 개수는 $h$개이며, 최대 개수는 $2^h-1$개이다.

 

이진 트리의 종류

포화 이진 트리 (full binary tree)	완전 이진 트리 (complete binary tree)	편향 이진 트리 (skewed binary tree)
모든 레벨에 노드가 완전히 찬 트리	높이가 $h$인 트리의 레벨 $1$부터 $h-1$까지 모든 노드가 채워져 있고 마지막 레벨에서는 노드가 왼쪽에서 오른쪽으로 저장된 구조	각 노드가 왼쪽 혹은 오른쪽으로 치우쳐 있는 구조
최대 레벨 수를 $k$라고 할 때, 전체 노드의 수는 $2^k-1$이다. 노드에 번호를 붙이는 순서는 각 레벨을 단위로 왼쪽에서 오른쪽으로 부여한다.	노드의 개수는 $n$개이고 최대 레벨이 $k$인 완전 이진 트리에서 $n<=2^k-1$이 성립한다.

 

 

이진 트리의 순회(traversal)

이진 트리의 모든 노드를 정해진 순서에 따라 한 번씩 방문하는 것

전위 순회	중위 순회	후위 순회
루트 노드 → 왼쪽 서브 트리 → 오른쪽 서브 트리	왼쪽 서브 트리 → 루트 노드 → 오른쪽 서브 트리	왼쪽 서브 트리 → 오른쪽 서브 트리 → 루트 노드

 

※ 선 안 겹치게 점 이으면 쉽게 풀 수 있다

 

---

 

그래프(graph)

[정점] 자료가 저장되어 있는 각 노드

[간선] 정점을 연결하는 링크

 

※ 트리와 그래프의 차이

트리	그래프
방향이 있음	방향이 없을 수도 있음
한 자식 노드에 한 부모 노드	한 자식 노드에 여러 부모 노드 가능

 

[정방 행렬] 두 정점 사이에 간선이 있을 경우 1, 아니면 0

 

[깊이 우선 탐색] 정점 A부터 나아가다가 없으면 되돌아와서 다른 길을 찾음

[너비 우선 탐색] 정점 A부터 가까운 정점을 찾다가 없으면 나아감