들어가며
- 이번엔 연결 리스트를 통해 이진 트리의 구현을 수행한다. 우리가 구현할 연산은 다음과 같다.
- 원소의 삽입
- 원소의 삭제
- 임의의 위치에 존재하는 원소의 삭제
- 트리의 레벨, 전위, 중위, 후위 순회
- 임의의 노드의 부모 노드를 반환
- 트리에 존재하는 모든 노드의 개수 반환
- 이때 제한 조건 이전에 제시한 조건과 동일하다.
- 원소의 삽입과 삭제는 complete binary tree의 방식을 따른다.
- 임의의 위치에 존재하는 원소의 삭제 연산은 해당 원소에 딸려있는 모든 원소들을 삭제해야 한다.
조건해석과 구현 방법
- 이전에 수행했던 조건과 동일하므로 해석 역시 동일하다. 눈여겨보아야 할 점은 임의의 위치에 존재하는 원소의 삭제 연산이다.
- 해당 원소에 딸려있는 모든 원소를 삭제해야한다는 것은 해당 원소를 루트로 하여 구성되는 서브트리 전체를 삭제하라는 것과 동치이다. 이는 연결 리스트에서는 매우 쉽게 수행이 가능한데 구현 부분에서 살펴보도록 하자.
- 연결 리스트로 구현하는 것이기 때문에 노드 클래스가 필요하다. 이번 노드는 다음과 같이 구성될 것이다.
- 데이터를 저장하는 멤버인 data
- 해당 노드의 좌측 자식과 우측 자식을 나타내는 left, right
- 해당 노드의 부모 노드를 가리키는 parent
- 해당 구성 요소를 사용하여 구현한 노드는 다음과 같다.
class Node{
int data;
Node left;
Node right;
Node parent;
Node(int data){
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
}
}
- 또한 우리가 구현할 이진 트리 클래스는 다음과 같다.
class BinaryTree{
Node root;
int elementCnt;
BinaryTree(){
root = null;
elementCnt = 0;
}
public void addNode(int data){
}
public void removeNode(){
}
public void removeNode(int data){
}
public Node searchNode(int data){
}
public int getParent(int data){
}
public void levelTraversal(){
}
public void preorderTraversal(Node cur){
}
public void inorderTraversal(Node cur){
}
public void postorderTraversal(Node cur){
}
public int getElementCnt(){
}
}
원소의 추가
- 원소를 추가할 때 좌에서 우로 추가해야한다. 즉 레벨 순회를 하면서 left또는 right가 null인 곳을 찾아 그곳에 새로운 원소를 추가하는 것이다.
- 연결 리스트에서 레벨 순회는 이전에 사용했던 큐 자료구조를 사용하여 구현한다.
public void addNode(int data){
Node newNode = new Node(data);
if (root == null){
root = newNode;
elementCnt++;
return;
}
Deque<Node> queue = new ArrayDeque<>();
queue.addLast(root);
while(!queue.isEmpty()){
Node cur = queue.pollFirst();
if (cur.left != null){
queue.addLast(cur.left);
} else{
cur.left = newNode;
newNode.parent = cur;
break;
}
if (cur.right != null){
queue.addLast(cur.right);
} else{
cur.right = newNode;
newNode.parent = cur;
break;
}
}
elementCnt++;
}
- 루트부터 시작해 루트와 연결된 노드들을 큐에 넣고 큐에서 빼면서 해당 노드들과 이어진 노드들을 큐에 넣는 것을 반복한다. 큐는 선입선출의 성질을 가지므로 left부터 큐에 들어가므로 순회가 좌에서 우로 진행되는 것을 알 수 있다.
- 이렇게 순회를 하며 비어있는 링크가 존재하는지 각 노드에 대해 확인하고 존재한다면 새로 만든 노드를 그곳에 연결함으로서 원소 추가를 수행한다.
- 이때 트리가 완전히 비어있다면, 즉 root = null이라면 루트에 노드를 할당해주는 것으로 마무리하면 된다.
원소의 삭제
- 원소의 삭제도 트리의 끝에서부터 원소를 제거하는 방법으로 구현할 수 있다.
- 그렇다면 트리의 마지막 원소를 구해야 한다. 이는 레벨 순회를 하면서 순회중인 노드를 가리키는 포인터를 둠으로서 해결이 가능하다. 하지만 문제점이 생기는데 노드 자기 자신을 삭제하기가 곤란하다는 점이다.
- 이는 우리가 미리 선언하고 설정한 변수 parent를 사용해 해당 노드의 부모 노드를 사용하여 조작함으로서 해결이 가능하다.
public void removeNode(){
if (root == null){
return;
}
Deque<Node> queue = new ArrayDeque<>();
queue.addLast(root);
Node tgtNode = null;
while (!queue.isEmpty()){
Node cur = queue.pollFirst();
tgtNode = cur;
if (cur.left != null) queue.addLast(cur.left);
if (cur.right != null) queue.addLast(cur.right);
}
if (tgtNode == null){
return;
}
if (tgtNode.parent.left == tgtNode){
tgtNode.parent.left = null;
} else if (tgtNode.parent.right == tgtNode){
tgtNode.parent.right = null;
}
elementCnt--;
}
- 보면 마지막 노드의 부모 노드를 찾아 부모 노드의 좌 우 자식을 비교하여 해당 자식이 맞는지 확인한 후 그 링크를 끊음으로서 원소의 삭제를 구현하고 있다.
- 임의의 노드를 삭제하는 것도 살펴보자 이를 구현하기 위해서는 우선 해당 노드가 어느 위치에 존재하는지에 대하여 먼저 확인해야 한다. 이를 위해서 위치를 구하는 함수 searchNode를 사용할 것이다.
public Node searchNode(int data){
Deque<Node> queue = new ArrayDeque<>();
Node tgtNode = null;
queue.addLast(root);
while (!queue.isEmpty()){
Node cur = queue.pollFirst();
if (cur.data == data){
tgtNode = cur;
break;
}
if (cur.left != null) queue.addLast(cur.left);
if (cur.right != null) queue.addLast(cur.right);
}
return tgtNode;
}
- 레벨 순회를 사용하여 순회하면서 해당 노드가 우리가 찾는 노드가 맞는지 검사해 찾는다면 해당 노드를 반환하는 것으로 searchNode를 구현하였다.
- 이제 반환받은 노드의 부모 노드를 사용하여 링크를 끊으므로서 해당 노드와 그 노드에 딸린 모든 서브트리를 트리상에서 삭제시키는 것이 가능하다.
public void removeNode(int data){
Node tgtNode = searchNode(data);
if (tgtNode == null){
return;
}
if (tgtNode.parent.left == tgtNode){
tgtNode.parent.left = null;
} else if (tgtNode.parent.right == tgtNode){
tgtNode.parent.right = null;
}
elementCnt--;
}
트리의 순회
- 레벨 순회는 앞에서 기능들을 구현하면서 간접적으로 많이 사용하였다.
public void levelTraversal(){
Deque<Node> queue = new ArrayDeque<>();
queue.addLast(root);
while (!queue.isEmpty()){
Node cur = queue.pollFirst();
System.out.print(cur.data + " ");
if (cur.left != null) queue.addLast(cur.left);
if (cur.right != null) queue.addLast(cur.right);
}
}
- 전위 중위 후위 역시 원리가 동일하다. 달라진 건 배열에서 인덱스를 통해 조회했다면 연결 리스트에서는 링크를 통해 따라가는 것이기 때문에 상대적으로 직관적인 모습을 하고있다.
public void preorderTraversal(Node cur){
if (cur == null){
return;
}
System.out.print(cur.data + " ");
preorderTraversal(cur.left);
preorderTraversal(cur.right);
}
public void inorderTraversal(Node cur){
if (cur == null){
return;
}
inorderTraversal(cur.left);
System.out.print(cur.data + " ");
inorderTraversal(cur.right);
}
public void postorderTraversal(Node cur){
if (cur == null){
return;
}
postorderTraversal(cur.left);
postorderTraversal(cur.right);
System.out.print(cur.data + " ");
}
그 외 다른 연산들
- 어떤 노드의 부모를 구하는 연산과 트리의 전체 원소 개수를 구하는 연산은 다음과 같다.
public int getParent(int data){
if (searchNode(data) == null){
return -1;
}
return searchNode(data).parent.data;
}
public int getElementCnt(){
return elementCnt;
}
- 앞에서 필요한 기능과 맴버들을 대부분 구현하고 선언하였기에 이러한 기능들은 그져 구현된 기능이나 맴버를 호출하는 것으로 구현이 완료되었다.
정리
- 이렇게 이진 트리의 배열과 연결 리스트를 사용한 구현을 각각 알아보았다.
- 트리의 구조와 특성 그리고 순회 방식과 구현 방법은 이후 이진 탐색 트리나 트라이 등과 같은 여러 트리 자료구조들을 이해할 때 도움이 되므로 한 번씩 구현해보면서 그 원리를 익혀보도록 하자.
- 전체적인 코드는 다음과 같다.
import java.util.*;
class Node{
int data;
Node left;
Node right;
Node parent;
Node(int data){
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
}
}
class BinaryTree{
Node root;
int elementCnt;
BinaryTree(){
root = null;
elementCnt = 0;
}
public void addNode(int data){
Node newNode = new Node(data);
if (root == null){
root = newNode;
elementCnt++;
return;
}
Deque<Node> queue = new ArrayDeque<>();
queue.addLast(root);
while(!queue.isEmpty()){
Node cur = queue.pollFirst();
if (cur.left != null){
queue.addLast(cur.left);
} else{
cur.left = newNode;
newNode.parent = cur;
break;
}
if (cur.right != null){
queue.addLast(cur.right);
} else{
cur.right = newNode;
newNode.parent = cur;
break;
}
}
elementCnt++;
}
public void removeNode(){
if (root == null){
return;
}
Deque<Node> queue = new ArrayDeque<>();
queue.addLast(root);
Node tgtNode = null;
while (!queue.isEmpty()){
Node cur = queue.pollFirst();
tgtNode = cur;
if (cur.left != null) queue.addLast(cur.left);
if (cur.right != null) queue.addLast(cur.right);
}
if (tgtNode == null){
return;
}
if (tgtNode.parent.left == tgtNode){
tgtNode.parent.left = null;
} else if (tgtNode.parent.right == tgtNode){
tgtNode.parent.right = null;
}
elementCnt--;
}
public void removeNode(int data){
Node tgtNode = searchNode(data);
if (tgtNode == null){
return;
}
if (tgtNode.parent.left == tgtNode){
tgtNode.parent.left = null;
} else if (tgtNode.parent.right == tgtNode){
tgtNode.parent.right = null;
}
elementCnt--;
}
public Node searchNode(int data){
Deque<Node> queue = new ArrayDeque<>();
Node tgtNode = null;
queue.addLast(root);
while (!queue.isEmpty()){
Node cur = queue.pollFirst();
if (cur.data == data){
tgtNode = cur;
break;
}
if (cur.left != null) queue.addLast(cur.left);
if (cur.right != null) queue.addLast(cur.right);
}
return tgtNode;
}
public int getParent(int data){
if (searchNode(data) == null){
return -1;
}
return searchNode(data).parent.data;
}
public void levelTraversal(){
Deque<Node> queue = new ArrayDeque<>();
queue.addLast(root);
while (!queue.isEmpty()){
Node cur = queue.pollFirst();
System.out.print(cur.data + " ");
if (cur.left != null) queue.addLast(cur.left);
if (cur.right != null) queue.addLast(cur.right);
}
}
public void preorderTraversal(Node cur){
if (cur == null){
return;
}
System.out.print(cur.data + " ");
preorderTraversal(cur.left);
preorderTraversal(cur.right);
}
public void inorderTraversal(Node cur){
if (cur == null){
return;
}
inorderTraversal(cur.left);
System.out.print(cur.data + " ");
inorderTraversal(cur.right);
}
public void postorderTraversal(Node cur){
if (cur == null){
return;
}
postorderTraversal(cur.left);
postorderTraversal(cur.right);
System.out.print(cur.data + " ");
}
public int getElementCnt(){
return elementCnt;
}
}
public class StudyCode{
public static void main(String[] args){
BinaryTree bt = new BinaryTree();
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.getElementCnt());
bt.removeNode();
bt.removeNode();
System.out.println(bt.getElementCnt());
bt.addNode(8);
bt.addNode(9);
bt.addNode(10);
bt.removeNode(5);
printTree(bt);
System.out.println(bt.getElementCnt());
}
static void printTree(BinaryTree bt){
bt.levelTraversal();
System.out.println();
bt.preorderTraversal(bt.root);
System.out.println();
bt.inorderTraversal(bt.root);
System.out.println();
bt.postorderTraversal(bt.root);
System.out.println();
}
}