이진트리(Binary Tree)
이진트리(Binary Tree)는 트리 중에서도 각 노드가 최대 2개의 자식노드를 가질 때 이진트리(Binary Tree)라고 한다.
최대 2개이기 때문에 자식이 없을 수도 있고, 한개만 있을 수도 있다.
이때 자식노드는 각각 왼쪽 자식노드와 오른쪽 자식노드로 표현을 한다.
그래서 같은 루트에 같은 자식노드 하나를 가지고 있어도
자식노드의 위치가 각각 왼쪽과 오른쪽으로 다르다면 그 두 트리는 서로 다른 트리가 된다.
완전이진트리(Complete binary tree)
이 트리는 두가지 조건을 충족해야 한다.
첫째, 마지막 레벨(level)을 제외하고 모든 노드가 채워져있어야 한다.
마지막 레벨의 노드는 다 채워져 있을 수도 있고 아닐수도 있다.
둘째, 노드는 왼쪽에서 오른쪽 방향 으로 채워져야 한다.
그래서 어느 노드에 오른쪽 자식이 존재한다면 왼쪽 자식도 가지고 있어야 완전이진트리로 볼 수 있다.
위 왼쪽 그림에서 이 부분은 왼쪽 자식 하나만 있어도 왼쪽에서 오른쪽으로 채워져야 한다는 완전이진트리(Complete binary tree)의 조건을 충족하기 때문에 완전이진트리(Complete binary tree)라고 할 수 있다.
위 왼쪽 그림의 트리처럼 오른쪽 자식노드는 있지만 왼쪽 자식 노드는 없다면 완전이진트리가 성립하지 않는다. 그리고 오른쪽 그림의 트리도 왼쪽부터 채우고 있지 않기 때문에 완전 이진트리가 될 수 없다.
이진트리의 특징
1) 1차원 배열로 표현 할 수 있다.
그래서 이런 이진트리는 트리지만 선형자료구조인 1차원 배열로도 표현할 수 있다는 특징을 가진다.
위 그림처럼 루트에서 시작해서 왼쪽노드부터 오른쪽 노드까지 순서를 매기면
완전이진트리(Complete binary tree)같은 경우는 빈숫자가 없게 된다.
그래서 완전이진트리(Complete binary tree)는 각 번호를 인덱스로 써서 1차원 배열로 표현이 가능하다.
완전 이진트리는 1차원 배열에서 이렇게 빈틈없이 값을 채운 배열이 될 수 있고,
중간에 빈 값이 있는 이진트리는 배열로 표현하면 비어있는 공간의 인덱스에
null값이 들어간 1차원 배열로 표현할 수 있다.
2) 이진트리의 연산
i번재 인덱스에 들어있는 노드의 부모는 i/2연산을 한 인덱스의 위치에 들어가 있게 되고,
노드 i의 왼쪽 자식은 i*2를한 인덱스에 들어있다.
노드 i의 오른쪽 자식은 i*2+1을한 위치의 인덱스에서 찾을 수 있다.
배열로 표현된 트리에서 6번째 노드의 부모는 나누기2를 한 3번째 인덱스에 위치하게 되고,
노드 2의 왼쪽 자식 노드는 2*2를한 4번째 위치에서 찾을 수 있다는 것을 알 수 있다.
