[javascript] tree , binary Tree

포스팅 전 주저리 : 알바하고 있는 곳에 전임자가 매니저로 왔다... 가뜩이나 사람들 자꾸 나가서 짜증난데 내가 정말 싫어하는 부류인 예의도 싸가지도 없는 놈이 매니저로 오다니 ㅜ.ㅜ 빨리 그만두라는 신의 계시인 것인가 ... ? 

 

Tree 란 ? 

 

 

Tree란 조직도같이 하나의 루트(하나 밖에 없는 차상위)에서 하층구조들과 연결된 계층적 자료구조를 말한다. 대표적으로 인공지능 문제에서도 트리가 사용된다고 한다.

 

Tree를 이루고 있는 것들

 

 

Node : 데이터를 담는 공간이다. 

Root Node : 최상위 노드로 부모없이 가장 높은 곳에 있는 노드를 말한다. 

Edge : 부모와 자식노드를 연결해주는 선

Childe Node : 부모가 있는 노드로 위에 3의 데이터를 가지고 있는 노드입장에서 1을 가진 노드와 2를 가진 노드는 자식노드이다.

Parents Node : 자식이 있는 노드로 위에 3을 가지고 있는 노드는 1과 2를 가진 노드의 부모노드이다.

Sibling Node : 같은 층에 있는 노드들을 형제노드라고 한다. 1과 2, 8, 12를 가진 노드들은 서로 형제노드들이다. 

Leap Node : 자식을 가지고 있지 않은 노드들을 Leap node 라고 한다.

Degree : 어떤 노드가 가지고 있는 자식의 개수 

Tree의 종류

 

 Binary-tree 와 none Binary-tree

 

tree는 크게 두 종류로 구분 한다. 부모노드가 자식을 2개까지만 가질 수 있는 Binary-tree 와 자식노드의 수가 제한이 없는 non Binary-tree 이다. (자식이 3개면 ternary tree 라고 부르기도 한다.)

 

Binary-tree 의 종류

 

포화 이진 트리 full biary tree

 

포화 이진트리는 마지막 레벨층을 제외한 모든 노드들이 2개의 자식노드들을 가지고 있는 형태이다. 

 

포화 이진 트리는 레벨 깊이 k 인 경우 ( 2의 k제곱 - 1 )개의 노드를 가진다. 

 

완전 이진 트리 complete binary tree 

 

완전 이진 트리는 마지막 레벨 k는 왼쪽에서 오른쪽으로 차있고 중간에 있는 노드들은 레벨 k 이하의 노드들은 모두 마지막 레벨 k까지 왼쪽부터 오른쪽으로 자식을 가지고 있어야 한다. 그래서 위와 같이 포화이진트리의 형태가 완전이진트리가 될 수 있다. (포화이진트리는 항상 완전이진트리이지만 완전이진트리는 포화이진트리가 될 수 없다.) 

 

 

완전 이진 트리 Compleate binary tree

J 와 M의 왼쪽 자식노드가 비어있어 완전이진트리가 아닌 트리 

 

 

지금까지 나온 완전이진트리와 포화이진트리 중 어느 것에도 해당되지 않은 이진트리가 기타 이진트리이다. 

 

기타 이진트리 

 

이진트리의 표현방법

이진트리를 만들려면 배열과 포인터를 가진 노드로 만들 수 있다. 2부에서는 배열로 이진트리를 만드는 것에 대하여 포스팅 할 예정이다.