[윤성우의 열혈 자료구조]트리(Tree) - 이진 트리(Binary Tree) 자바(Java) 구현

배열기반 트리

• 노드에 번호를 부여하고 그 번호에 해당하는 값을 배열의 인덱스 값으로 활용한다.
  • 노드 번호는 완전 이진 트리 삽입 순서와 일치되도록 한다.

• 일반적으로 편의상 배열의 첫 번째 요소는 사용하지 않는다.

• 배열의 기본적인 장점인 접근이 용이하다는 특성이 그대로 반영이 되고 배열기반 트리에서 완성하기 용이한 트리 관련 연산도 존재한다.

 

연결리스트기반 트리

• 트리의 구조와 리스트의 연결 구조가 일치한다.
  • 구현 시, 메모리에 저장된 형태가 일치하여 직관적인 이해가 더 좋다

• 배열기반 트리에서 구현하기 용이한 연산을 구현하려면 복잡하다.

 

이진 트리의 순회(Traversal)

• 순회의 세 가지 방법(루트 노드를 접근 하는 시점에 따라 분류)
  • 중위 순회
    • 왼쪽 노드 방문 → 루트 노드 방문 → 오른쪽 노드 방문
  • 후위 순회
    • 왼쪽 노드 방문 → 오른쪽 노드 방문 → 루트 노드 방문
  • 전위 순회
    • 루트 노드 방문 → 왼쪽 노드 방문 → 오른쪽 노드 방문

• 재귀적으로 순회의 과정을 구성하면 높이에 상관없이 모든 노드를 조회할 수 있다.

 

이진 트리의 추상 자료형(ADT)

BinaryNode MakeBinaryTreeNode() //이진 트리의 노드(이진 트리)를 생성하여 반환하는 메소드

T GetData(BinaryNode bn) //이진 트리의 노드(이진 트리)의 데이터를 반환하는 메소드

void SetData(BinaryNode bn, T data) //이진 트리의 노드(이진 트리)에 데이터를 저장하는 메소드

BinaryNode GetLeftSubTree(BinaryNode bn) //이진 트리의 노드(이진 트리)의 왼쪽 서브 트리를 반환하는 메소드

BinaryNode GetRightSubTree(BinaryNode bn) //이진 트리의 노드(이진 트리)의 오른쪽 서브 트리를 반환하는 메소드

void MakeLeftSubTree(BinaryNode main, BinaryNode sub) //이진 트리의 노드(이진 트리)의 왼쪽 서브 트리를 생성하는 메소드

void MakeRightSubTree(BinaryNode main, BinaryNode sub) //이진 트리의 노드(이진 트리)의 오른쪽 서브 트리를 생성하는 메소드

void InorderTraverse(BinaryNode bn) //이진 트리의 중위 순회

void InorderTraverse(BinaryNode bn, BinaryTreeVisitor<T> visitFuncPtr) //이진 트리의 중위 순회(방문 목적 사용)

void PostorderTraverse(BinaryNode bn) //후위 트리의 중위 순회

void PreorderTraverse(BinaryNode bn) //전위 트리의 중위 순회

 

연결리스트기반 이진 트리

구현 코드에서 만들어진 이진 트리의 형태

package datastructure.binarytree;

public interface BinaryTreeVisitor<T> {
	void action(T data);
}

package datastructure.binarytree;

public class LinkedListBinaryTree<T> {
	
	/*
	 * 이진 트리의 노드이자 이진 트리를 표현한 클래스
	 * 이진 트리의 모든 노드는 직/간접적으로 연결되어 있다. 
	 * 따라서 루트 노드의 값만 기억하면, 이진 트리 전체를 가리키는 것과 다름이 없다.
	 * 
	 * 논리적으로도 하나의 노드는 그 자체로 이진트리이다.
	 * 따라서 노드를 표현한 클래스는 실제로 이진 트리를 표현한 클래스가 된다.
	 */
	private class BinaryNode{
		private T data;
		private BinaryNode left;
		private BinaryNode right;
		
		public BinaryNode(){
			data = null;
			left = null;
			right = null;
		}

		public T getData() {
			return data;
		}

		public void setData(T data) {
			this.data = data;
		}
	}
	
	/**
	 * 이진 트리 노드 생성
	 * @return
	 */
	public BinaryNode MakeBinaryTreeNode() {
		BinaryNode binaryNode = new BinaryNode();
		return binaryNode;
	}
	
	/**
	 * 이진 트리 노드에 저장된 데이터를 반환
	 * @param bn
	 * @return
	 */
	public T GetData(BinaryNode bn) {
		return bn.getData();
	}
	
	/**
	 * 이진 트리 노드에 데이터를 저장
	 * @param bn
	 * @param data
	 */
	public void SetData(BinaryNode bn, T data) {
		bn.setData(data);
	}
	
	/**
	 * 이진 트리 왼쪽 서브 트리의 주소 값 반환
	 * @param bn
	 * @return
	 */
	public BinaryNode GetLeftSubTree(BinaryNode bn) {
		return bn.left; 
	}
	
	/**
	 * 이진 트리 오른쪽 서브 트리의 주소 값 반환
	 * @param bn
	 * @return
	 */
	public BinaryNode GetRightSubTree(BinaryNode bn) {
		return bn.right; 
	}

	/**
	 * 이진 트리 왼쪽 서브 트리 설정
	 * main의 왼쪽의 서브 트리를 sub로 설정
	 * @param main
	 * @param sub
	 * @return
	 */
	public void MakeLeftSubTree(BinaryNode main, BinaryNode sub) {
		main.left = sub; 
	}
	
	/**
	 * 이진 트리 오른쪽 서브 트리 설정
	 * main의 오른쪽의 서브 트리를 sub로 설정
	 * @param main
	 * @param sub
	 * @return
	 */
	public void MakeRightSubTree(BinaryNode main, BinaryNode sub) {
		main.right = sub;
	}

	/**
	 * 이진 트리의 중위 순회
	 * @param bn
	 */
	public void InorderTraverse(BinaryNode bn) {
		if(bn == null) return;	//현재 노드가 자식이 없는 경우 탈출. 즉, 서브 트리가 없고 단순히 노드일 경우

		//일단 서브트리가 존재하는 것으로 가정하고 순회
		InorderTraverse(bn.left);
		System.out.printf("%d \t", bn.data); //루트 노드의 데이터 출력
		InorderTraverse(bn.right);
	}

	/**
	 * 이진 트리의 중위 순회(방문 목적 사용)
	 * @param bn
	 */
	public void InorderTraverse(BinaryNode bn, BinaryTreeVisitor<T> visitFuncPtr) {
		if(bn == null) return;	//현재 노드가 자식이 없는 경우 탈출. 즉, 서브 트리가 없고 단순히 노드일 경우

		//일단 서브트리가 존재하는 것으로 가정하고 순회
		InorderTraverse(bn.left, visitFuncPtr);
		visitFuncPtr.action(bn.data); //루트 노드의 데이터 출력(방문 목적)
		InorderTraverse(bn.right, visitFuncPtr);
	}
	
	/**
	 * 이진 트리의 후위 순회
	 * @param bn
	 */
	public void PostorderTraverse(BinaryNode bn) {
		if(bn == null) return;	//현재 노드가 자식이 없는 경우 탈출. 즉, 서브 트리가 없고 단순히 노드일 경우

		//일단 서브트리가 존재하는 것으로 가정하고 순회
		PostorderTraverse(bn.left);
		PostorderTraverse(bn.right);
		System.out.printf("%d \t", bn.data); //루트 노드의 데이터 출력
	}

	/**
	 * 이진 트리의 전위 순회
	 * @param bn
	 */
	public void PreorderTraverse(BinaryNode bn) {
		if(bn == null) return;	//현재 노드가 자식이 없는 경우 탈출. 즉, 서브 트리가 없고 단순히 노드일 경우

		//일단 서브트리가 존재하는 것으로 가정하고 순회
		System.out.printf("%d \t", bn.data); //루트 노드의 데이터 출력
		PreorderTraverse(bn.left);
		PreorderTraverse(bn.right);
	}
	
	public static void main(String[] args) {
		LinkedListBinaryTree<Integer> binaryTree = new LinkedListBinaryTree<>();
		
		//이진 트리 노드 4개 생성
		LinkedListBinaryTree<Integer>.BinaryNode binaryTreeNode1 = binaryTree.MakeBinaryTreeNode();
		LinkedListBinaryTree<Integer>.BinaryNode binaryTreeNode2 = binaryTree.MakeBinaryTreeNode();
		LinkedListBinaryTree<Integer>.BinaryNode binaryTreeNode3 = binaryTree.MakeBinaryTreeNode();
		LinkedListBinaryTree<Integer>.BinaryNode binaryTreeNode4 = binaryTree.MakeBinaryTreeNode();
		
		//이진트리 노드 데이터 저장
		binaryTree.SetData(binaryTreeNode1, 1);
		binaryTree.SetData(binaryTreeNode2, 2);
		binaryTree.SetData(binaryTreeNode3, 3);
		binaryTree.SetData(binaryTreeNode4, 4);
		
		//서브 트리 설정
		binaryTree.MakeLeftSubTree(binaryTreeNode1, binaryTreeNode2); // 노드2를 노드1의 왼쪽 서브 트리로
		binaryTree.MakeRightSubTree(binaryTreeNode1, binaryTreeNode3); // 노드3를 노드1의 오른쪽 서브 트리로
		binaryTree.MakeLeftSubTree(binaryTreeNode2, binaryTreeNode4); // 노드4를 노드2의 왼쪽 서브 트리로
		
		System.out.println("이진 트리의 서브트리 데이터 조회");
		System.out.printf("%d \t", binaryTree.GetData(binaryTree.GetLeftSubTree(binaryTreeNode1)));
		System.out.printf("%d \t", binaryTree.GetData(binaryTree.GetLeftSubTree(binaryTree.GetLeftSubTree(binaryTreeNode1))));
		System.out.println("\n중위 순회");
		binaryTree.InorderTraverse(binaryTreeNode1);
		System.out.println("\n후위 순회");
		binaryTree.PostorderTraverse(binaryTreeNode1);
		System.out.println("\n전위 순회");
		binaryTree.PreorderTraverse(binaryTreeNode1);
	
		//중위 순회(방문 목적 사용)
		System.out.println("\n중위 순회(방문 목적 사용)");
		binaryTree.InorderTraverse(binaryTreeNode1, 
				(T)-> System.out.printf("[%d] \t", T)
		);
	}
}

 

---

[참고자료]

윤성우의 열혈 자료구조