01.29(14일차)

---그래프---

2개 이상의 항목이 어떤 관계를 맺고 있는지를 정점 과 간선으로 표현하는것

 

 

 

--깊이 우선 탐색--

시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 탐색하다가 갈곳이 없으면, 가장 마지막에 만났던 

부모 정점으로 돌아와서 다른 방향을 탐색하는 방법이다.

 

--너비 우선 탐색--

시작 정점에서 인접한 모든 정점들을 우선 방문한 후, 더 이상 방문하지 않은 정점이 없을 때까지 방문했던

정점들을 다시 시작점으로 해서 모든 정점들을 차례로 방문하는 방법.

 

 

 

---트리---

임의의 노드에서 다른 노드로의 경로가 하나밖에 없는 것을 트리 자료구조라 한다.

 

--루트--

트리의 가장 위쪽에 있는 노트를 루트라고한다.

 

--리프--

가장 아래쪽에 있는 노드를 리프라고한다.

 

--비단말 노드--

리프를 제외한 노드(루트 포함)

 

--자식--

어떤 노드와 가지가 연결되어있을 때 아래쪽 노드(개수상관X)

 

--부모--

어떤 노드와 가지가 연결되어있을때 가장 위쪽에 있는 노드(노드의 부모는 하나뿐이다.)

 

--형제--

부모가 같은 노드 

 

--조상--

어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드

 

--자손--

어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드

 

--레벨--

루트에서 얼마나 멀리 떨어져 있는지를 나타내는 것(가장 위쪽이0 아래로 내려갈떄마다 1씩 증가 )

 

--차수--

각 노드가 갖는 자식의 수

 

--높이--

루트에서 가장 멀리 있는 리프까지의 거리. 리프 레벨의 최댓값

 

--서브트리--

어떤 노드를 루트로 하고 , 그 자손으로 구성된 트리.

 

--빈 트리--

노드와 가지가 전혀 없는 트리를 빈트리 혹은 놀 트리 라고한다.

 

 

 

---이진 트리---

모든 노드가 최대 2개의 자식 노드를 가질수있는 구조 

왼쪽 자식을 루트로 하는 서브트리를 왼쪽 서브트리 라고한다.

오른쪽 자식을 루트로 하는 서브트리를 오른쪽 서브트리라고한다.

 

왼쪽 서브 트리의 값은 루트의 값보다 작고, 오른쪽 서브 트리의 값은 루트보다 큰값을 가지도록 구성한다.