자료구조 - Tree와 순회, 코드로 알아보기

자료구조 - Tree와 순회 구현

지난 포스트에서는 binary tree에 대한 기본 개념을 익혀보았습니다.
이번 포스트에서는 Java를 이용해서 지난번 설명한 개념을 토대로 구현해보도록 하겠습니다.

Tree - 구현된 코드 살펴보기

---

👇Node를 구현한 Class와 설명

하나의 node는 자기 자신(의 데이터), 그리고 child node-left & right의 정보를 가지고 있습니다.
자식이 부모를 기억하거나, 자식과 부모가 서로를 참조하고 있거나 할 수도 있는데 일단 여기서는 parent node가 child node를 갖고 있는 걸로 간단하게 구현해보았어요.

class Node<T> {
    T data;
    Node left;
    Node right;
}

👇Tree를 구현한 코드와 설명

Tree는 Node들을 갖습니다. Tree의 node를 생성할 수 있도록 해주어야겠죠(makeNode()).
그리고 탐색하면서 콘솔에 출력하도록 세 가지 동작을 구현해보았습니다.
중위(inorderedPrint()), 전위(preorderedPrint()), 후위(postorderedPrint())의 세가지입니다.
순회 방식에 따라서, 자기 자신을 출력하는 것, 왼쪽 child node를 재귀적으로 탐색하는 것, 오른쪽 child node를 재귀적으로 탐색하는 것을 순서에 맞게 실행합니다.

class Tree<T> {
    public Node root;

    public Node makeNode(Node left, T data, Node right) {
        Node node = new Node();
        node.data = data;
        node.left = left;
        node.right = right;
        return node;
    }

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

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

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

👇구현된 결과를 확인해보기

TreeImpl이라는 클래스를 하나 만들어서, main() 메서드에서 확인해보았어요.
맨 위 주석에 나와있는 형태의 트리를 만든 것이고요.
그 아래에서 순회를 해보고 있습니다. 각 출력된 결과는 옆에 주석으로 붙여놓았는데요. 잘 출력되었죠?

public class TreeImpl {

    public static void main(String[] args) {
        /*
        *         1
        *     2        3
        * 4      5  6
        * */
        Tree<Integer> tree = new Tree<>();
        Node node4 = tree.makeNode(null, 4, null);
        Node node5 = tree.makeNode(null, 5, null);
        Node node2 = tree.makeNode(node4, 2, node5);
        Node node6 = tree.makeNode(null, 6, null);
        Node node3 = tree.makeNode(node6, 3, null);
        Node node1 = tree.makeNode(node2, 1, node3);

        /* 순회해보기 */
        tree.inorderedPrint(node1); // 출력 결과 : 4  2  5  1  6  3
        System.out.println();
        tree.postorderedPrint(node2); // 출력 결과 : 4  5  2
        System.out.println();
        tree.preorderedPrint(node3); // 출력 결과 : 3  6
    }

}

마무리

---

이렇게 해서 Tree와 tree를 구성하는 node, 그리고 순회 방식까지 더 잘 알아보았습니다.
Tree에서 어떤 노드가 Root인지 기억하는 속성을 추가한다면, 특별히 어떤 노드를 지정하지 않아도 root node부터 순회하도록 할 수 있겠죠. 직접 추가해보는 것도 좋을 것 같습니다.