이진트리의 순회에는 총 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 + " ");
}
}
위 그림으로 순회코드를 만들어보자.
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);
}
}
}