그래프
그래프는 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조
연결된 노드 간의 관계를 표현할 수 있음
특징
-
그래프는 순환 혹은 비순환 구조
-
그래프는 방향이 있는 그래프와 방향이 없는 그래프로 나뉨
-
루트 노드 / 부모-자식 관계 없음
-
2개 이상의 경로가 가능
(무방향, 방향, 양방향 가능) -
네트워크 모델
트리
트리는 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조
두 개의 노드 사이에 반드시 1개의 경로만을 가지며 사이클이 존재하지 않는 방향 그래프
부모-자식 관계가 성립하는 계층형 모델
특징
-
부모-자식 관계가 존재해 레벨이 존재(최상위 노드=Root)
-
노드가 N개이면 간선은 N-1개 / 각 레벨 k에 존재하는 노드는 2^k개(완전이진트리의 경우)
-
방향성이 존재하고 사이클은 존재하시 않음(비순환)
-
전위순회, 중위순회, 후위순회 3가지
