트리(Tree)

이전까지 공부했던 스택, 큐, 덱은 선형 자료구조라고 말한다. 트리는 선형 자료구조가 아닌 계층적인 구조를 가지는 자료구조이다.

트리는 한 개 이상의 노드로 이루어진 유한 집합이다. 이들 중 하나인 루트(Root)라는 노드를 기준으로 계층적인 구조를 유지하면서 아래로 뻗어나가는 자료구조이다.

​트리의 종류에는 여러 가지가 존재하지만 이번에는 자식 노드의 개수가 최대 2개인 이진 트리를 다뤄보겠다.

이진 트리의 정의는 다음과 같다.

공집합이거나 루트와 왼쪽 서버 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진트리여야 한다.

 

이진 트리는 형태에 따라 다음과 같이 분류할 수 있다.

포화 이진 트리 : 트리의 각 레벨에 노드가 꽉 차 있는 이진 트리
완전 이진 트리 : 높이가 k 일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터
                      오른쪽으로 노드가 순서대로 채워져 있는 이진트리

 

​이진 트리의 순회 방법은 대표적으로 전위, 중위, 후위 순회로 3가지가 있다.

• 전위 순회(preorder traversal) : VLR
• 중위 순회(inorder traversal) : LVR
• 후위 순회(postorder traversal) : LRV

 

이진 트리는 배열, 링크 2가지 방법으로 구현할 수 있다. 나는 보통 링크로 구현하지만 후에 배울 힙(Heap) 자료구조를 구현할 때는 배열을 이용해서 구현한다. 다음은 간단하게 링크로 구현한 이진 트리이다.

class Node {
	char data;
	Node left, right;

	public Node() {}

	public Node(char data, Node left, Node right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}
}

class Tree {
	private Node root;

	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}

	public Node createNode(char data, Node left, Node right) {
		return new Node(data, left, right);
	}

	public void preOrder(Node root) {
		if (root == null) return;
		System.out.print(root.data + " ");
		preOrder(root.left);
		preOrder(root.right);
	}

	public void inOrder(Node root) {
		if (root == null) return;
		inOrder(root.left);
		System.out.print(root.data + " ");
		inOrder(root.right);
	}

	public void postOrder(Node root) {
		if (root == null) return;
		postOrder(root.left);
		postOrder(root.right);
		System.out.print(root.data + " ");
	}
}

구현한 이진 트리로 간단한 예제를 테스트한 결과는 다음과 같다.

Tree tree = new Tree();
Node[] node = new Node[5];
node[4] = tree.createNode('E', null, null);	
node[3] = tree.createNode('D', null, null);
node[2] = tree.createNode('C', null, null);
node[1] = tree.createNode('B', node[3], null);
node[0] = tree.createNode('A', node[1], node[2]);
tree.setRoot(node[0]);
System.out.println("preOrder");
tree.preOrder(tree.getRoot());
System.out.println("\n--------");
System.out.println("inOrder");
tree.inOrder(tree.getRoot());
System.out.println("\n--------");
System.out.println("postOrder");
tree.postOrder(tree.getRoot());