[Java] - 자바로 이진트리(Binary Tree) 구현하기

 

 

 

연결 체인을 사용하여 이진트리를 구현해 보도록 하겠습니다.

 

 

 

 

이진트리란?

https://ttl-blog.tistory.com/699

[자료구조] - 트리(Tree)[1] - 트리의 정의와 용어

https://ttl-blog.tistory.com/700

[자료구조] - 트리(Tree)[2] - 트리의 표현

https://ttl-blog.tistory.com/701

[자료구조] - 트리(Tree)[3] - 이진 트리(Binary Tree)

https://ttl-blog.tistory.com/702

[자료구조] - 트리(Tree)[4] - 이진 트리의 구현

https://ttl-blog.tistory.com/704

[자료구조] - 트리(Tree)[5] - 이진 트리의 구현

 

 

 

 

 

 

 

 

 

BinaryTree<T> 인터페이스

interface BinaryTree<T>{

	boolean isEmpty();

	boolean isFull();

	int size();

	int height();

	boolean add(T item);

	void inOrder();

	void preOrder();

	void postOrder();

	void levelOrder();
}

 

 

 

 

 

 

 

 

 

 

 

BinaryNode<T> 구현

이진트리를 연결체인으로 구현할 것이기에, 연결체인에 사용할 node를 다음과 같이 구현합니다.

public class BinaryNode<T> {

	private T element;
	private BinaryNode<T> leftChild;
	private BinaryNode<T> rightChild;



	public T getElement() {
		return element;
	}

	public void setElement(T element) {
		this.element = element;
	}

	public BinaryNode<T> leftChild() {
		return leftChild;
	}

	public void setLeftChild(BinaryNode<T> leftChild) {
		this.leftChild = leftChild;
	}

	public BinaryNode<T> rightChild() {
		return rightChild;
	}

	public void setRightChild(BinaryNode<T> rightChild) {
		this.rightChild = rightChild;
	}



	public BinaryNode() {}
	public BinaryNode(T element) {
		this.element = element;
	}

	public BinaryNode(T element, BinaryNode<T> leftChild, BinaryNode<T> rightChild) {
		this.element = element;
		this.leftChild = leftChild;
		this.rightChild = rightChild;
	}

	/**
	 * 왼쪽 자식 노드가 있는지 확인한다.
	 */
	public boolean hasLeftChild() {
		return this.leftChild != null;
	}


	/**
	 * 오른쪽 자식 노드가 있는지 확인한다.
	 */
	public boolean hasRightChild() {
		return this.rightChild != null;
	}


	/**
	 * Leaf 노드인지 확인
	 */
	public boolean isLeaf(){
		return this.leftChild == null && this.rightChild == null;
	}



}

 

 

 

 

 

 

 

 

 

 

BinaryTree<T> 전체 구현

import java.util.ArrayDeque;
import java.util.Queue;


public class BinaryTreeByLinkedNode<T> implements BinaryTree<T>{


   private BinaryNode<T> root;


   private int size;
   private int height;



   public BinaryTreeByLinkedNode() {}


   public BinaryTreeByLinkedNode(BinaryNode<T> root) {
      this.root = root;
      this.size = 1;
      this.height = 1;
   }



   public BinaryNode<T> getRoot() {
      return root;
   }

   public void setRoot(BinaryNode<T> root) {
      this.root = root;
   }

   public int getSize() {
      return size;
   }

   public void setSize(int size) {
      this.size = size;
   }

   public int getHeight() {
      return height;
   }

   public void setHeight(int height) {
      this.height = height;
   }



   /**
    * 트리가 비어있는지 확인
    */
   public boolean isEmpty() {
      return this.root == null;
   }


   /**
    * 트리가 가득 찼는지 확인
    */
   public boolean isFull(){
      return false;
   }




   /**
    * 트리의 원소의 개수를 반환
    */
   public int size() {
      return this.sizeOfSubTree(this.root);
   }


   /**
    * 서브 트리의 원소의 개수를 구한다
    */
   private int sizeOfSubTree(BinaryNode<T> subTreeRoot) {

      if(subTreeRoot.isLeaf()) return 1;

      return sizeOfSubTree(subTreeRoot.leftChild()) + sizeOfSubTree(subTreeRoot.rightChild()) + 1;
   }


   /**
    * 트리의 높이를 반환
    * (이때 루트 노드의 레벨은 1)
    */
   public int height() {
      return this.heightOfSubTree(this.root);
   }


   /**
    * 서브 트리의 높이를 반환
    * (이때 루트 노드의 레벨은 1)
    */
   private int heightOfSubTree(BinaryNode<T> subTreeRoot) {
      if(subTreeRoot.isLeaf()) return 1;
      return  Math.max(heightOfSubTree(root.leftChild()), heightOfSubTree(root.rightChild())) + 1;
   }






   @Override
   public boolean add(T item) {
      BinaryNode<T> newNode = new BinaryNode<>(item);
      if (size == 0) {
         root = newNode;
         size++;
         return true;
      }

      BinaryNode<T> current = root;

      Queue<BinaryNode<T>> q = new ArrayDeque<>();
      q.add(current);

      while (!q.isEmpty()) {
         current = q.poll();

         //== 좌측 서브트리 우선 탐색 ==//
         if (!current.hasLeftChild()) {
            current.setLeftChild(newNode);
            break;
         }

         q.add(current.leftChild());


         //== 이후 우측 서브트리 탐색 ==//
         if (!current.hasRightChild()) {
            current.setRightChild(newNode);
            break;
         }

         q.add(current.rightChild());
      }

      size++;
      return true;
   }


   public void inOrder() {
      this.inOrderRecursively(this.root);
   }


   private void inOrderRecursively (BinaryNode<T> root) {
      if(root == null) return;

      this.inOrderRecursively(root.leftChild());

      System.out.print(" -> " + root.getElement() );
      this.inOrderRecursively(root.rightChild());
   }



   public void preOrder() {
      this.preOrderRecursively(this.root);
   }




   private void preOrderRecursively (BinaryNode<T> root) {
      if(root == null) return;

      System.out.print(" -> " + root.getElement() );
      this.preOrderRecursively(root.leftChild());
      this.preOrderRecursively(root.rightChild());
   }




   public void postOrder() {
      this.postOrderRecursively(this.root);
   }




   private void postOrderRecursively (BinaryNode<T> root) {
      if(root == null) return;

      this.postOrderRecursively(root.leftChild());
      this.postOrderRecursively(root.rightChild());
      System.out.print(" -> " + root.getElement() );
   }




   public void levelOrder() {
      Queue<BinaryNode<T>> nodeQueue = new ArrayDeque<>();

      nodeQueue.add(this.root);

      while (!nodeQueue.isEmpty()) {
         BinaryNode<T> visitingNode = nodeQueue.remove();

         System.out.print(" -> " + visitingNode.getElement() );

         if(visitingNode.hasLeftChild()){
            nodeQueue.add(visitingNode.leftChild());
         }
         if(visitingNode.hasRightChild()){
            nodeQueue.add(visitingNode.rightChild());
         }
      }
   }



}

 

 

 

 

 

 

 

 

 

 

 

 

세부 구현

 

BinaryTree<T> 사이즈 확인

/**
 * 서브 트리의 원소의 개수를 구한다
 */
private int sizeOfSubTree(BinaryNode<T> subTreeRoot) {

   if(subTreeRoot.isLeaf()) return 1;

   return sizeOfSubTree(subTreeRoot.leftChild()) + sizeOfSubTree(subTreeRoot.rightChild()) + 1;
}

설명

트리에 존재하는 원소의 크기를 재귀적으로 구합니다.

만약 리프 노드라면 1을 반환하고, 그렇지 않다면 오른쪽 서브트리와 왼쪽 서브트리의 개수에 1을 더한 값을 반환합니다.

여기서 더해지는 1은 자기 자신의 크기입니다.

 

 

 

 

BinaryTree<T> 높이 확인

/**
 * 트리의 높이를 반환
 * (이때 루트 노드의 레벨은 1)
 */
public int height() {
   return this.heightOfSubTree(this.root);
}


/**
 * 서브 트리의 높이를 반환
 * (이때 루트 노드의 레벨은 1)
 */
private int heightOfSubTree(BinaryNode<T> subTreeRoot) {
   if(subTreeRoot.isLeaf()) return 1;
   return  Math.max(heightOfSubTree(root.leftChild()), heightOfSubTree(root.rightChild())) + 1;
}

설명

트리의 높이를 재귀적으로 구합니다.

만약 리프 노드라면 1을 반환하고, 그렇지 않다면 오른쪽 서브트리와 왼쪽 서브트리의  높이 중 더 큰 값에 1을 더해 반환합니다.

여기서 더해지는 1은 바로 자기 자신의 높이입니다.

 

 

 

 

 

BinaryTree<T> 추가

@Override
public boolean add(T item) {
   BinaryNode<T> newNode = new BinaryNode<>(item);
   if (size == 0) {
      root = newNode;
      size++;
      return true;
   }

   BinaryNode<T> current = root;

   Queue<BinaryNode<T>> q = new ArrayDeque<>();
   q.add(current);

   while (!q.isEmpty()) {
      current = q.poll();

      //== 좌측 서브트리 우선 탐색 ==//
      if (!current.hasLeftChild()) {
         current.setLeftChild(newNode);
         break;
      }

      q.add(current.leftChild());


      //== 이후 우측 서브트리 탐색 ==//
      if (!current.hasRightChild()) {
         current.setRightChild(newNode);
         break;
      }

      q.add(current.rightChild());
   }

   size++;
   return true;
}

설명

Queue를 사용하여 구현하였습니다.

 

루트 노드를 Queue에 삽입한 후에, 아래 과정을 반복합니다.

 

1. Queue가 비어있지 않다면 Queue에서 원소를 하나 꺼냅니다. 이를 current로 두었습니다.

 

2. current의 왼쪽 서브트리를 우선 탐색합니다. leftchild가 존재하지 않는다면 삽입할 노드를 leftChild로 설정한 뒤 종료합니다.

 

3. current의 왼쪽 서브트리가 존재한다면 이를 Queue에 넣고 오른쪽 서브트리를 탐색합니다.  마찬가지로  rightChild가 존재하지 않는다면 삽입할 노드를 leftChild로 설정한 뒤 종료합니다.

 

4. 오른쪽 서브트리도 존재한다면 Queue에 삽입한 뒤 다시 1번으로 돌아갑니다.

 

 

 

 

 

 

 

BinaryTree<T>  탐색

 

1. inorder

public void inOrder() {
   this.inOrderRecursively(this.root);
}


private void inOrderRecursively (BinaryNode<T> root) {
   if(root == null) return;

   this.inOrderRecursively(root.leftChild());

   System.out.print(" -> " + root.getElement() );
   this.inOrderRecursively(root.rightChild());
}

설명

Inorder는 left -> 루트 -> right 순서로 탐색합니다.

이를 재귀적으로 구현하였습니다.

 

 

 

 

 

 

 

 

2. preorder

public void preOrder() {
   this.preOrderRecursively(this.root);
}




private void preOrderRecursively (BinaryNode<T> root) {
   if(root == null) return;

   System.out.print(" -> " + root.getElement() );
   this.preOrderRecursively(root.leftChild());
   this.preOrderRecursively(root.rightChild());
}

설명

Preorder는 루트 -> left -> right 순서로 탐색합니다.

이를 재귀적으로 구현하였습니다.

 

 

 

 

 

 

 

3. postorder

public void postOrder() {
   this.postOrderRecursively(this.root);
}




private void postOrderRecursively (BinaryNode<T> root) {
   if(root == null) return;

   this.postOrderRecursively(root.leftChild());
   this.postOrderRecursively(root.rightChild());
   System.out.print(" -> " + root.getElement() );
}

설명

Postorder는  left -> right -> 루트  순서로 탐색합니다.

이를 재귀적으로 구현하였습니다.

 

 

 

 

 

4. levelorder

public void levelOrder() {
   Queue<BinaryNode<T>> nodeQueue = new ArrayDeque<>();

   nodeQueue.add(this.root);

   while (!nodeQueue.isEmpty()) {
      BinaryNode<T> visitingNode = nodeQueue.remove();

      System.out.print(" -> " + visitingNode.getElement() );

      if(visitingNode.hasLeftChild()){
         nodeQueue.add(visitingNode.leftChild());
      }
      if(visitingNode.hasRightChild()){
         nodeQueue.add(visitingNode.rightChild());
      }
   }
}

설명

Level Order는 레벨별로 트리를 순회하는 방법으로 Queue를 사용하여 쉽게 탐색이 가능합니다.

 

먼저 루트 노드를 Queue 에 넣은 체로 시작합니다.

 

Queue에서 노드 하나를 꺼내어 해당 노드의 left와 right를 다시 queue에 삽입하며, 이 과정을 Queue가 빌 때까지 반복합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

테스트코드

public class Test {
   public static void main(String[] args) {
      BinaryTreeByLinkedNode<String> binaryTree = new BinaryTreeByLinkedNode<>();

      binaryTree.add("A");
      binaryTree.add("B");
      binaryTree.add("C");
      binaryTree.add("D");
      binaryTree.add("E");
      binaryTree.add("F");
      binaryTree.add("G");
      binaryTree.add("H");
      binaryTree.add("I");


      System.out.println("inorder 시작");
      binaryTree.inOrder();
      System.out.println();
      System.out.println("inorder 끝");
      System.out.println();

      System.out.println("postOrder 시작");
      binaryTree.postOrder();
      System.out.println();
      System.out.println("postOrder 끝");
      System.out.println();

      System.out.println("preOrder 시작");
      binaryTree.preOrder();
      System.out.println();
      System.out.println("preOrder 끝");
      System.out.println();

      System.out.println("levelOrder 시작");
      binaryTree.levelOrder();
      System.out.println();
      System.out.println("levelOrder 끝");
      System.out.println();

   }
}