#스택과 큐는 list자료구조의 특별한경우.
트리와 그래프는 비선형 자료구조의 특별한 경우.
< Tree >
-나무를 거꾸로 뒤집어 놓은 듯한 모습.(하나의 뿌리로부터 가지가 사방으로 뻗은 형태)
-그래프의 여러 구조중 단방향 그래프의 한 구조.
-계층적 자료구조: 데이터가 바로 아래에 있는 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결됨.
-비선형구조: 데이터를 순차적으로 나열시킨 선형구조가 아니라, 하나의 데이터 아래에 여러개의 데이터가 존재할수있음(나뭇가지처럼)
-계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클(cycle)이 없다.
-사이클이 없는 하나의 연결 그래프(connected Graph)라고 할수있다.
-사이클: 시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 돌아올수있다면 사이클이 존재한다고 표현한다.
< Tree의 구조와 특징 >
#노드(node): 트리 구조를 이루는 모든 개별 데이터
루트(root): 트리 구조의 시작점이 되는 노드
부모 노드(parent node): 두 노드가 상하관계로 연결되어 있을때 상대적으로 루트에서 가까운 노드 (위쪽방향)
자식 노드(child node): 두 노드가 상하관계로 연결되어 있을때 상대적으로 루트에서 먼 노드(아래쪽방향)
리프(leaf): 트리 구조의 끝 지점이고, 자식 노드가 없는 노드(가장 아래쪽방향)
#루트에서 시작.
여러개의 데이터를 간선(edge)으로 연결.
각 데이터를 노드(node)라고 한다.
두개의 노드가 상하계층으로 연결되면 부모/자식 관계를 맺는다.
#A는 B와C의 부모노드(parent node)
B와 C는 A의 자식노드(child node)
자식이 없는 노드는 리프 노드(leaf node)
# tree는 깊이와 높이, 레벨 등을 측정할수있다
#깊이(Depth)
-루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할수있다.
-루트 노드는 깊이가 0이다.
-A의 깊이는 0.
B와 C의 깊이는 1.
D,E,F,G의 깊이는 2.
#레벨(Level)
- 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할수있다.
-같은 레벨에 나란히 있는 노드를 형제 노드(Sibling node)라고 한다.
- A의 level은 1이다.(깊이가0)
B와 C의 level은 2이다.(깊이가1)
D,E,F,G의 level은 3이다.
#높이(height)
- 리프 노드를 기준으로 루트까지의 높이.(리프 노드와 직간접적으로 연결된 노드의 높이를 표현)
-높이를 표현할때는 각 리프 노드의 높이를 0으로 놓는다.
-부모 노드는 자식 노드의 가장 높은 높이 값에 +1한 값을 높이로 가진다.
-H,I,E,F,J의 높이는 0이다.
D, G의 높이는 1이다.
B, C의 높이는 2이다.
B는 D의 height+1
C는 G의 height+1
A의 높이는 3이다.
#서브 트리(sub tree)
-큰 트리의 내부에 트리 구조를 갖춘 작은 트리를 말한다.
- (D, H, I), (B, D, E), (C, F, G, J)
<예제>
-컴퓨터의 디렉토리 구조(모든 폴더는 하나의 폴더에서 시작되어 가지를 뻗어나가는 모양새를 띈다.)
-월드컵의 토너먼트 대진표, 가계도(족보), 조직도 등
출처
코드스테이츠
