들어가며
- 이진 트리는 이전에 말했듯 배열과 연결 리스트로 구현이 가능하다.
- 이번에는 배열로 이진 트리를 구현하는 것을 해보도록 하겠다. 우리가 구현해야할 기능들은 다음과 같다.
- 트리에 원소를 추가
- 트리에 원소를 삭제
- 트리의 전위, 중위, 후위, 레벨 순회 구현
- 이때 따라붙는 제한 조건(구체적 조건)은 다음과 같다.
- 원소를 추가할 때는 complete binary tree의 방식을 따른다. 즉 좌에서 우로 원소를 추가해야한다.
- 원소를 제거할 때에는 우에서 좌로 원소를 삭제한다.
조건해석과 유의사항
- 원소를 추가할 때 complete binary tree의 방식을 따르므로 이 트리는 complete binary tree가 된다. 즉 리프 노드간의 높이 차이가 최대 1까지 존재하며, 우측 자식이 존재한다면 반드시 좌측 자식도 존재한다.
- 배열로 구현을 하기 위해서는 우선 노드의 좌 우를 어떻게 지정할 것인가를 먼저 생각해야 한다. 이때 complete binary tree를 만족하는 트리 구조에서 다음을 만족한다.
- 어떤 노드의 인덱스가 idx라고 할 때 좌측 자식의 인덱스는 idx * 2 + 1이다.
- 어떤 노드의 인덱스가 idx라고 할 때 우측 자식의 인덱스는 idx * 2 + 2이다.
- 배열의 특성 상 크기를 유동적으로 늘리기 불편하므로 이를 해결하기 위해 ArrayList를 사용할 것이다.
class BinaryTreeArr{
ArrayList<Integer> treeData;
int elementCnt;
BinaryTreeArr(){
treeData = new ArrayList<>();
elementCnt = 0;
}
public void addNode(int data){
}
public void removeNode(){
}
public void levelTraversal(){
}
public void preorderTraversal(int cur){
}
public void inorderTraversal(int cur){
}
public void postorderTraversal(int cur){
}
}
- 우리가 구현할 이진 트리의 기본적인 구조이다.
원소의 추가
- 원소의 추가는 다음과 같은 조건이 따라붙는다고 했다.
- complete binary tree의 방식을 따른다. 즉 좌에서 우로 원소들이 채워진다.
- 이는 루트인 0번 idx부터 시작하여 좌측 자식인 0 * 2 + 1 = 1번 인덱스, 0 * 2 + 2 = 2번 인덱스로 채워지며 이후 루트의 좌측 자식인 1번 idx부터 다시 시작해 좌측 자식은 1 * 2 + 1 = 3, 1 * 2 + 2 = 4번 인덱스에 채워진다.
- 여기서 그냥 배열에 원소를 idx순으로 배치만 하더라도 위 조건을 아주 잘 만족한다는 것을 알 수 있다. 따라서 노드의 추가는 다음과 같이 간단히 할 수 있다.
public void addNode(int data){
treeData.add(data);
elementCnt++;
}
원소의 삭제
- 원소를 삭제하는 연산 역시 우측부터 원소가 삭제된다.
- 즉 트리에서 가장 마지막 원소부터 순서대로 삭제되는 것을 의미한다.
public void removeNode(){
if (treeData.isEmpty()){
return;
}
treeData.remove(treeData.size() - 1);
elementCnt--;
}
트리의 순회
- 먼저 레벨 순회를 구현해보자. 루트부터 시작해 좌에서 우로 모든 노드를 방문하는 것으로 이는 곧 배열을 순회하기만 하면 레벨 순회가 구현된다는 것을 의미한다.
public void levelTraversal(){
for (Integer treeDatum : treeData) {
if (treeDatum != null) {
System.out.print(treeDatum + " ");
}
}
System.out.println();
}
- 이제 전위 순회를 구현해보자 전위 순회는 자신 - 좌측 자식 - 우측 자식으로 탐색을 진행한다. 이는 자신의 데이터를 먼저 출력하고, 좌측 자식이 자신이 되도록 재귀적 호출을 수행하고 이후 우측 자식이 자신이 되도록 다시 재귀호출을 수행함으로서 구현된다.
public void preorderTraversal(int cur){
if (treeData.isEmpty()){
return;
}
Integer data = treeData.get(cur);
int left = cur * 2 + 1;
int right = cur * 2 + 2;
if (data != null){
System.out.print(data + " ");
}
if (left < treeData.size()){
preorderTraversal(left);
}
if (right < treeData.size()){
preorderTraversal(right);
}
}
- 위에서 이미 서술했지만, 완전 이진 트리 구조에서 트리의 좌 우측은 각각 현재 인덱스의 2를 곱하고 1, 2를 더하는 것으로 접근할 수 있다는 것을 알아두자.
- 중위 후위도 전위 순회와 구조가 동일하며 단지 자신을 출력하는 파트가 어디에 존재하는지에 따라 달라진다. 크게 설명할 것은 더 이상 없다.
public void inorderTraversal(int cur){
if (treeData.isEmpty()){
return;
}
int left = cur * 2 + 1;
int right = cur * 2 + 2;
if (left < treeData.size()){
inorderTraversal(left);
}
Integer data = treeData.get(cur);
if (data != null){
System.out.print(data + " ");
}
if (right < treeData.size()){
inorderTraversal(right);
}
}
public void postorderTraversal(int cur){
if (treeData.isEmpty()){
return;
}
int left = cur * 2 + 1;
int right = cur * 2 + 2;
if (left < treeData.size()){
postorderTraversal(left);
}
if (right < treeData.size()){
postorderTraversal(right);
}
Integer data = treeData.get(cur);
if (data != null){
System.out.print(data + " ");
}
}
정리
- 배열의 구현은 그 구현이 매우 간단하며 접근 역시 간단하기 때문에 완전 이진 트리로 문제가 구성되어 있는 경우에 사용하면 효율적이다.
- 만약 메모리 풀을 사용할 경우 메모리 풀을 탐색하는 꼼수를 통해 임의의 위치에 노드를 삽입하거나 수정, 삭제가 가능하다. 기회가 된다면 한번 구현해보는 것을 권장한다.
- 다음 구현에는 연결 리스트를 사용하여 구현하는 방법에 대해 알아본다. 아래에는 배열로 구현한 이진 트리의 전체적인 코드이다.
import java.util.*;
class BinaryTreeArr{
ArrayList<Integer> treeData;
int elementCnt;
BinaryTreeArr(){
treeData = new ArrayList<>();
elementCnt = 0;
}
BinaryTreeArr(int[] dataset){
treeData = new ArrayList<>(dataset.length + 16);
elementCnt = 0;
for (int element: dataset){
treeData.add(element);
elementCnt++;
}
}
public void addNode(int data){
treeData.add(data);
elementCnt++;
}
public void removeNode(){
if (treeData.isEmpty()){
return;
}
treeData.remove(treeData.size() - 1);
elementCnt--;
}
public void levelTraversal(){
for (Integer treeDatum : treeData) {
if (treeDatum != null) {
System.out.print(treeDatum + " ");
}
}
System.out.println();
}
public void preorderTraversal(int cur){
if (treeData.isEmpty()){
return;
}
Integer data = treeData.get(cur);
int left = cur * 2 + 1;
int right = cur * 2 + 2;
if (data != null){
System.out.print(data + " ");
}
if (left < treeData.size()){
preorderTraversal(left);
}
if (right < treeData.size()){
preorderTraversal(right);
}
}
public void inorderTraversal(int cur){
if (treeData.isEmpty()){
return;
}
int left = cur * 2 + 1;
int right = cur * 2 + 2;
if (left < treeData.size()){
inorderTraversal(left);
}
Integer data = treeData.get(cur);
if (data != null){
System.out.print(data + " ");
}
if (right < treeData.size()){
inorderTraversal(right);
}
}
public void postorderTraversal(int cur){
if (treeData.isEmpty()){
return;
}
int left = cur * 2 + 1;
int right = cur * 2 + 2;
if (left < treeData.size()){
postorderTraversal(left);
}
if (right < treeData.size()){
postorderTraversal(right);
}
Integer data = treeData.get(cur);
if (data != null){
System.out.print(data + " ");
}
}
}
public class UserSolution{
public static void main(String[] args){
BinaryTreeArr bt = new BinaryTreeArr();
bt.addNode(1);
bt.addNode(2);
bt.addNode(3);
bt.addNode(4);
bt.addNode(5);
bt.addNode(6);
bt.addNode(7);
printTree(bt);
System.out.println();
bt.removeNode();
bt.removeNode();
bt.addNode(8);
bt.addNode(9);
bt.addNode(10);
printTree(bt);
}
static void printTree(BinaryTreeArr bt){
bt.levelTraversal();
bt.preorderTraversal(0);
System.out.println();
bt.inorderTraversal(0);
System.out.println();
bt.postorderTraversal(0);
System.out.println();
}
}