트리(Tree)

트리는 비선형 자료구조이다(선형이 아니다 )

Node( vertex) 와 Link(edge)로 구성됨

Node 는 정보(data)를 포함한다

Link는 두 Node 간의 연결을 나타냄

특징 :

Root 가 하나 존재 해야 한다 Root 는 최상의 Node

Root를 제외한 모든 Node 는 하나의 부모를 가져야 함

Node 는 여러개으 자식을 가질 수 있다

한 Node로 부터 다른 Node로 가는 경로는 유일해야 함

ex ) 윈도우 파일 구조( 윈도우 탐색기 )

leafNode

줄기의 끝 = 자식이 없는 노드 H,J,D,E,F,G , 최 하위 노드

Terminal node : 끝인 노드

Internal Node : Leaf Node 가 아닌 노드 , 즉 자식이 하나라도 있는 노드 B,C,I,A

sub tree : 트리의 부분 집합 {B,E,F,G} , {I,J} , {D}, ,

Path : 한 Node로 부터 다른 Node 로 가는 경로(중복없이 가능 경로)

만약 G와 C 가 연결 되어 있다면 G 에서 C 로 가는 경로가 한가지가 아닌 다른 경우의 수가 생김으로 그때는 트리가 되지 않느다

만약 연결됐다면 이때는 이것을 그래프 라고 한다

레벨(Level) : Root 에서 특정 노드로 가는 경로의 노드 수, 이때 Root 를 Level 1 로 친다

그래서 위 그래프의 레벨은 4 이다

최소공통선조(Least Common Ancedstors) ; 두 노드의 공통적인 선조중 가장 레벨이 높은 선조 노드

H,J 를 놓고 봤을때

H의 선조 = C,A

J 의 선조 = I ,C, A

공통 선조 C,A

가장 높은 선조는 Level 2 인 C 가 된다

이것이 중요한 이유는 경로는 항상 최소공통선조를 거쳐서 지나가기 때문!!!

자식 노드 : 자신의 아래에 연결되어 있는 노드 => C 의 자식 노드는 H,I

부모노드는 : 자신의 위에 있는 노드 =>I 의 부모는 C

조부모 : 자신의 부모의 부모노드 I 의 부모는 C , C의 부모는 A, 그래서 I 의 조부모 노드는 A 가 된다, J 의 조부모는 C