[자료구조] 이진 트리의 구현, 순회 (자바/Java)

728x90

이진 트리를 각각 배열과 링크드 리스트로 구현하고 트리의 노드들을 전위순회, 중위순회, 후위순회하는 코드를 구현하였다.

1. 배열

1-1. 트리 구현

배열로 이진 트리를 구현할 때는 배열의 index를 통해 부모와 자식 노드를 확인할 수 있다.

루트 노드의 index를 1로 하고, 같은 층위의 노드들을 순서대로 배열에 삽입하면 부모 노드의 인덱스가 i일 때 자식 노드의 인덱스는 i*2, i*2+1이 된다.

전체 정점의 개수를 입력받고 그 다음 줄에 각 간선의 parent와 child 값을 입력받는다.

13
1 2 1 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 11 13

위 케이스에서 1 2는 부모가 1, 자식 노드가 2임을 의미한다. 이때 루트노드는 부모 노드가 없으니 첫 간선을 삽입할 때는 루트 노드를 처리해줘야 한다.

		for (int i = 0; i < V - 1; i++) {
			int parent = sc.nextInt();
			int child = sc.nextInt();
			if (tree[1] == 0)
				tree[1] = parent;
			for (int p = 1; p < length; p++) {
				if (tree[p] == parent) {
					if (tree[2 * p] == 0)
						tree[2 * p] = child;
					else
						tree[2 * p + 1] = child;

					break;
				}
			}
		} // 이진트리 배열로 만들기

루트 노드를 처리하기 위해 tree[1]이 0인 경우 (아직 루트 노드가 삽입되지 않은 경우)에는 해당 노드를 parent로 설정하였다.

1-2. 전위 순회, 중위 순회, 후위 순회

전위 순회: 자기 자신 - 왼쪽 자식 - 오른쪽 자식

중위 순회: 왼쪽 자식 - 자기 자신 - 오른쪽 자식

후위 순회: 왼쪽 자식 - 오른쪽 자식 - 자기 자신

순서로 순회하는 것을 의미한다.

전위 순회

	static void preOrder(int i) {
		if (i < tree.length && tree[i] != 0) {
			System.out.print(tree[i] + " ");
			preOrder(i * 2);
			preOrder(i * 2 + 1);
		}
	}

배열의 index를 사용하기 때문에 배열이 꽉 차 있을 경우를 대비하여 tree.length보다 index가 작고, 0이 아닐 때에만 순회하도록 하였다.

int 배열을 선언하였기 때문에 초기값이 0이고, String이나 다른 타입이라면 null로 조건을 만들면 된다.

중위 순회

	static void inOrder(int i) {
		if (i < tree.length && tree[i] != 0) {
			inOrder(i * 2);
			System.out.print(tree[i] + " ");
			inOrder(i * 2 + 1);
		}
	}

후위 순회

	static void postOrder(int i) {
		if (i < tree.length && tree[i] != 0) {
			postOrder(i * 2);
			postOrder(i * 2 + 1);
			System.out.print(tree[i] + " ");
		}
	}

1-3. 전체 코드

package tree;

import java.util.Arrays;
import java.util.Scanner;

public class BinaryTreeArray {
	static int[] tree;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int length = (int) Math.pow(2, V + 1);
		tree = new int[length]; // 최대 배열 크기

		for (int i = 0; i < V - 1; i++) {
			int parent = sc.nextInt();
			int child = sc.nextInt();
			if (tree[1] == 0)
				tree[1] = parent;
			for (int p = 1; p < length; p++) {
				if (tree[p] == parent) {
					if (tree[2 * p] == 0)
						tree[2 * p] = child;
					else
						tree[2 * p + 1] = child;

					break;
				}
			}
		} // 이진트리 배열로 만들기
		System.out.println(Arrays.toString(tree));

		preOrder(1); // 전위순회
		System.out.println();
		inOrder(1);
		System.out.println();
		postOrder(1);

	} // main

	static void preOrder(int i) {
		if (i < tree.length && tree[i] != 0) {
			System.out.print(tree[i] + " ");
			preOrder(i * 2);
			preOrder(i * 2 + 1);
		}
	}

	static void inOrder(int i) {
		if (i < tree.length && tree[i] != 0) {
			inOrder(i * 2);
			System.out.print(tree[i] + " ");
			inOrder(i * 2 + 1);
		}
	}

	static void postOrder(int i) {
		if (i < tree.length && tree[i] != 0) {
			postOrder(i * 2);
			postOrder(i * 2 + 1);
			System.out.print(tree[i] + " ");
		}
	}
}

2. 링크드 리스트

2-1. 노드

링크드 리스트를 활용하기 위해서 노드 클래스를 정의하였다.

노드는 자기 자신의 data와 왼쪽 자식(left) 오른쪽 자식(right)를 변수로 가진다.

class MyNode {
	int data;
	MyNode left;
	MyNode right;

	public MyNode(int data) {
		this.data = data;
		this.left = null;
		this.right = null;
	}
}

2-2. 이진 트리의 검색

링크드 리스트는 배열과 달리 index로 자료를 관리하지 않기 때문에 부모 노드에 자식 노드를 추가하려면 부모 노드를 검색하는 메소드가 필요하다.

또한 기존의 이진 탐색 트리는 왼쪽 자식은 자기 자신보다 값이 작고, 오른쪽 자식은 자기 자신보다 값이 크지만, 크기를 보장하지 않는 경우의 검색은 방식이 다르다.

	public MyNode search(MyNode curr, int key) {
		MyNode leftNode = null;
		MyNode rightNode = null;
		if (curr != null) {
			if (curr.data == key)
				return curr;
			if (curr.left != null)
				leftNode = search(curr.left, key);
			if (curr.right != null)
				rightNode = search(curr.right, key);
		}

		if (leftNode != null)
			return leftNode;
		else if (rightNode != null)
			return rightNode;
		return null;
	}

leftNode와 rightNode 중 하나만 parent가 될 수 있기 때문에, 각각 다른 변수로 지정해야 한다.

변수를 지정하지 않고 재귀함수를 실행하면 다른 자식에 찾고자 하는 key가 있음에도 null을 반환하는 경우가 있었다.

2-3. 이진 트리의 삽입

	public void insert(int parent, int child) {
		MyNode parentNode = search(root, parent);
		if (parentNode == null) { // root가 비어있을 때
			parentNode = new MyNode(parent);
			this.root = parentNode;
		}

		MyNode childNode = new MyNode(child);
		if (parentNode.left == null)
			parentNode.left = childNode;
		else
			parentNode.right = childNode;

	}

이진 트리에 값을 삽입하기 위해서 먼저 부모 노드를 search메소드를 통해 찾는다.

만약 node가 존재하지 않는다면 tree가 비어 있는 경우를 의미하기 때문에 새로운 루트 노드를 만들어주고 root를 이 노드로 설정한다.

그리고 childNode를 삽입하는 경우이니 새로 노드를 만들어준 후, 왼쪽 자식이 비어있다면 왼쪽에, 아니라면 오른쪽에 자식을 삽입한다.

2-4. 전위 순회, 중위 순회, 후위 순회

기본적인 순회의 알고리즘은 동일하지만 배열과 달리 index가 아니라 left, right라는 변수로 자식 노드를 순회할 수 있다.

전위 순회

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

배열에서 index로 리프 노드를 확인했다면, 이 경우에는 root부터 시작해서 해당 값이 null이 아닐 때에만 재귀를 지속한다.

중위 순회, 후위 순회

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

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

2-5. 전체 코드

package tree;

import java.util.Scanner;

public class BinaryTreeLinkedList {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		MyBinaryTree tree = new MyBinaryTree();

		for (int i = 0; i < V - 1; i++) {
			int parent = sc.nextInt();
			int child = sc.nextInt();
			tree.insert(parent, child);
		}
		tree.preOrder(tree.root);
		System.out.println();
		tree.inOrder(tree.root);
		System.out.println();
		tree.postOrder(tree.root);

	}

}

class MyNode {
	int data;
	MyNode left;
	MyNode right;

	public MyNode(int data) {
		this.data = data;
		this.left = null;
		this.right = null;
	}
}

class MyBinaryTree {

	MyNode root;

	public MyBinaryTree() {
		this.root = null;
	}

	public void insert(int parent, int child) {
		MyNode parentNode = search(root, parent);
		if (parentNode == null) { // root가 비어있을 때
			parentNode = new MyNode(parent);
			this.root = parentNode;
		}

		MyNode childNode = new MyNode(child);
		if (parentNode.left == null)
			parentNode.left = childNode;
		else
			parentNode.right = childNode;

	}

	public MyNode search(MyNode curr, int key) {
		MyNode leftNode = null;
		MyNode rightNode = null;
		if (curr != null) {
			if (curr.data == key)
				return curr;
			if (curr.left != null)
				leftNode = search(curr.left, key);
			if (curr.right != null)
				rightNode = search(curr.right, key);
		}

		if (leftNode != null)
			return leftNode;
		else if (rightNode != null)
			return rightNode;
		return null;
	}

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

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

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

}