[알고리즘] 이진트리의 순회

이진트리의 순회에는 총 3가지가 있다.

전위 순회, 중위 순회, 후위 순회

전위 순회

• 루트를 서브 트리에 앞서 먼저 방문한다.

위의 그림에서 보면 전위 순회 라면 방문 순서는
[6, 3, 1, 5, 9, 7, 11]이 된다.

---

중위 순회

• 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문한다.

위의 그림에서 보면 중위 순회 라면 방문 순서는
[1, 3, 5, 6, 7, 9, 11]이 된다.

---

후위 순회

• 루트를 서브 트리 방문 후에 방문한다.

위의 그림에서 보면 후위 순회 라면 방문 순서는
[1, 5, 3, 7, 11, 9, 6]이 된다.

---

공통 코드

우선, 공통적으로 트리의 노드 정보를 가질 Node 클래스를 사용할 것이다.

Node Class

class Node { 
	int data;
	Node left;
	Node right; 
	
	Node(int data){ 
		this.data = data;
	}
}

Create Node Class

public void createNode(int data, int leftData, int rightData) {
	if(root == null) {
		root = new Node(data);

		if(leftData != -1) {
			root.left = new Node(leftData); 
		}
		if(rightData != -1) {
			root.right = new Node(rightData); 
		}
	} else { 
		searchNode(root, data, leftData, rightData);
	}
}

Search Node method
값을 어디에 추가해야할지 알아야 한다.
루트 노드가 있다면 루트 노드로부터 왼쪽인지 오른쪽인지 어디에 들어갈지를 정해야 한다.

	public static void searchNode(Node node, int data, int leftData, int rightData){
		if(node == null){
			return;
		}else if(node.data == data){
			if(leftData != -1){
				node.left = new Node(leftData);
			}
			if(rightData != -1){
				node.right = new Node(rightData);
			}
		}else{
			searchNode(node.left, data, leftData, rightData);
			searchNode(node.right, data, leftData, rightData);
		}
	}

전위, 중위, 후위 순회 메소드

전위 순회

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

중위 순회

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

후위 순회

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

---

Ex

위 그림으로 순회코드를 만들어보자.

import java.util.*;
class Main {
	
	public static class Node{
		int data;
		Node left;
		Node right;
		
		Node(int data){
			this.data = data;
		}
	}
	
	public static Node root;
	
	public static void main(String[] args) throws Exception {		
		createNode(6,3,9);
		createNode(3,1,5);
		createNode(9,7,11);		
		createNode(1,-1,-1);		
		createNode(5,-1,-1);		
		createNode(7,-1,-1);		
		createNode(11,-1,-1);		
		
		inOrder(root);
	}
	
	public static void createNode(int data, int leftData, int rightData){
		if(root==null){
			root = new Node(data);
			
			if(leftData != -1){
				root.left = new Node(leftData);
			}
			if(rightData != -1){
				root.right = new Node(rightData);
			}
		}else{
			searchNode(root, data, leftData, rightData);
		}
	}
	
	public static void searchNode(Node node, int data, int leftData, int rightData){
		if(node == null){
			return;
		}else if(node.data == data){
			if(leftData != -1){
				node.left = new Node(leftData);
			}
			if(rightData != -1){
				node.right = new Node(rightData);
			}
		}else{
			searchNode(node.left, data, leftData, rightData);
			searchNode(node.right, data, leftData, rightData);
		}
	}
	
	public static void inOrder(Node node){
		if(node!=null){
			if(node.left != null) inOrder(node.left);
			System.out.print(node.data + " ");
			if(node.right != null) inOrder(node.right);
		}
	}
}

Reference

• 관련 문제
• 관련 개념