[Algorithm] 트리 순회(Tree Traversal)

설명

• 전위 순회(Preorder Traversal)
  • 자신을 처리 → 왼쪽 자식 방문 → 오른쪽 자식 방문
• 중위 순회(Inorder Traversal)
  • 왼쪽 자식 방문 → 자신을 처리 → 오른쪽 자식 방문
• 후위 순회(Postorder Traversal)
  • 왼쪽 자식 방문 → 오른쪽 자식 방문 → 자신을 처리
• 참고
  • https://m.blog.naver.com/ndb796/221233560789

코드

public class Node<T> {
    public T value;
    public Node<T> leftNode;
    public Node<T> rightNode;

    public Node(T value) {
        this.value = value;
    }
}

public class Tree<T> {
    private Map<T, Node<T>> nodeMap = new HashMap<>();
    private Node<T> rootNode;

    public void join(T parentValue, T leftValue, T rightValue) {
        Node<T> parentNode = nodeMap.getOrDefault(parentValue, new Node<T>(parentValue));
        Node<T> leftNode = nodeMap.getOrDefault(leftValue, new Node<T>(leftValue));
        Node<T> rightNode = nodeMap.getOrDefault(rightValue, new Node<T>(rightValue));

        if (rootNode == null) {
            this.rootNode = parentNode;
        }

        parentNode.leftNode = leftNode;
        parentNode.rightNode = rightNode;

        nodeMap.put(parentValue, parentNode);
        nodeMap.put(leftValue, leftNode);
        nodeMap.put(rightValue, rightNode);
    }

    public List<T> preorder() {
        List<T> result = new ArrayList<>();
        preorder(result, rootNode);
        return result;
    }

    // 전위 순회(Preorder Traversal)
    private void preorder(List<T> result, Node<T> node) {
        if (node != null) {
            result.add(node.value);
            preorder(result, node.leftNode);
            preorder(result, node.rightNode);
        }
    }

    public List<T> inorder() {
        List<T> result = new ArrayList<>();
        inorder(result, rootNode);
        return result;
    }

    // 중위 순회(Inorder Traversal)
    private void inorder(List<T> result, Node<T> node) {
        if (node != null) {
            inorder(result, node.leftNode);
            result.add(node.value);
            inorder(result, node.rightNode);
        }
    }

    public List<T> postorder() {
        List<T> result = new ArrayList<>();
        postorder(result, rootNode);
        return result;
    }

    // 후위 순회(Postorder Traversal)
    private void postorder(List<T> result, Node<T> node) {
        if (node != null) {
            postorder(result, node.leftNode);
            postorder(result, node.rightNode);
            result.add(node.value);
        }
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#treeData -> #preorder, #inorder, #postorder"() {
        expect:
        Tree<Integer> tree = new Tree<>();
        treeData.each { values -> tree.join(values.get(0), values.get(1), values.get(2)) }
        tree.preorder() == preorder
        tree.inorder() == inorder
        tree.postorder() == postorder

        where:
        treeData                                                                            | preorder                                            | inorder                                             | postorder
        [[1, 2, 3], [2, 4, 5], [4, 8, 9], [5, 10, 11], [3, 6, 7], [6, 12, 13], [7, 14, 15]] | [1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15] | [8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15] | [8, 9, 4, 10, 11, 5, 2, 12, 13, 6, 14, 15, 7, 3, 1]
    }
}