자바로 Tree 구현하기

트리에는 선회방법이 3가지가 있다.

중위순회(Inorder) Left -> Root -> Right

전위순회(PreOrder) Root -> Left -> Right

후위순위(PostOrder) Left -> Right -> Root

외우기 힘들다면 Root를 기준으로 중위면 Root가 가운데이 있고, 전위라면 Root가 앞에, 후위라면 Root가 뒤에 그리고 무조건 Left 다음 Right인 것을 인지한다면 쉽게 외울 수 있을 것 같다.

중위 순회 Inorder = Left -> Root -> Right

4 -> 2 -> 5 -> 1 -> 3

전위순회 Preorder = Root -> Left -> Right

1 -> 2 -> 4 -> 5 -> 3

후위순회 Postorder = Left -> Right -> Root

4 -> 5 -> 2 -> 3 -> 1

class Node {
    int data;
    Node left;
    Node right;
}
 
class Tree {
    public Node root;
    
    public void setRoot(Node node) {
        
        this.root = node;
    }
    
    public Node getRoot() {
        
        return root;
    }
    
    public Node createNode(Node left, int data, Node right) {
        Node node = new Node();
        node.data = data;
        node.left = left;
        node.right = right;
        
        return node;
    }
    
    //중위 순회 Inorder = Left -> Root -> Right
    //4 -> 2 -> 5 -> 1 -> 3
    public void inOrder(Node node) {
        if(node != null) {
            inOrder(node.left);
            System.out.println(node.data);
            inOrder(node.right);
        }
    }
    
    //전위순회 Preorder = Root -> Left -> Right
    //1 -> 2 -> 4 -> 5 -> 3
    public void preOrder(Node node) {
        if(node != null) {
            System.out.println(node.data);
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    
    //후위순회 Postorder = Left -> Right -> Root
    //4 -> 5 -> 2 -> 3 -> 1
    public void postOrder(Node node) {
        if(node != null) {
            preOrder(node.left);
            preOrder(node.right);
            System.out.println(node.data);
        }
    }
}
 
public class Main {
    public static void main(String[] args) {
        Tree t = new Tree();
        Node n4 = t.createNode(null, 4, null);
        Node n5 = t.createNode(null, 5, null);
        Node n2 = t.createNode(n4, 2, n5);
        Node n3 = t.createNode(null, 3, null);
        Node n1 = t.createNode(n2, 1, n3);
        
        t.setRoot(n1);
        t.inOrder(t.getRoot());
    }
}