트리 순회(Tree Traversal)란?

 트리 순회

트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말합니다.

하나도 빠뜨리지 않고, 정확히 한 번만 중복없이 방문해야 하는데, 노드를 방문하는 순서에 따라 세 가지로 나뉩니다.

• 전위순회(preorder)
• 중위순회(inorder)
• 후위순회(postorder)

 

전위 순회 [Preorder]

루트 노드에서 시작해서 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회하는 방식입니다.

깊이 우선 순회(depth-first-traversal) 이라고도 합니다. 

위 예시 트리에 전위 순회 방식을 적용하면, 

1 - 2 - 4 - 5 - 3 이 됩니다.

 

중위 순회 [Inorder]

루트 노드에서 시작해서 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순으로 순회하는 방식입니다. 

대칭 순회(symmetric traversal) 이라고도 합니다.

위 예시 트리에 중위 순회 방식을 적용하면,

4 - 2 - 5 - 1 - 3 이 됩니다.

 

후위 순회 [Postorder]

루트 노드에서 시작해서 왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드 순으로 순회하는 방식입니다.

위 예시 트리에 후위 순회 방식을 적용하면,

4 - 5 - 2 - 3 - 1 이 됩니다.

 

 

 

Java 로 트리 순회를 구현해보겠습니다.

 

// 각 노드
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 makeNode(Node left, int data, Node right) {
        Node node = new Node();
        node.data = data;
        node.left = left;
        node.right = right;

        return node;
    }

    // 전위
    public void preorder(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preorder(node.left);
            preorder(node.right);
        }
    }
    // 중위
    public void inorder(Node node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.data + " ");
            inorder(node.right);
        }
    }
    // 후위
    public void postorder(Node node) {
        if (node != null) {
            postorder(node.left);
            postorder(node.right);
            System.out.print(node.data + " ");
        }
    }
}

public class BinaryTree {
    public static void main(String[] args) {
        Tree t = new Tree();
        Node n4 = t.makeNode(null, 4, null);
        Node n5 = t.makeNode(null, 5, null);
        Node n2 = t.makeNode(n4, 2, n5);
        Node n3 = t.makeNode(null, 3, null);
        Node n1 = t.makeNode(n2, 1, n3);

        t.setRoot(n1);

        System.out.println("Inorder 중위");
        t.inorder(t.getRoot());
        System.out.println();
        System.out.println("Preorder 전위");
        t.preorder(t.getRoot());
        System.out.println();
        System.out.println("Postorder 후위");
        t.postorder(t.getRoot());
    }
}