[자료구조] 이진트리의 순회 및 java구현

순회는 이진 트리에 있는 모든 노드를 한번씩 방문하여 노드가 가지고 있는 데이터를 처리하는 것이다. 여기서 처리라 함은 노드 안의 데이터를 출력할 수도 있고, 데이터 값을 변환할수도 있다.

순회의 종류에는 총3가지가 있다. 전위순회 중위순회 후위순회

• 현재 노드를 방문하여 데이터를 읽는 작업을 D또는 V라고 한다.
• 현재 노드의 왼쪽 서브트리로 이동하는 작업을 L이라고 한다.
• 현재 노드의 오른쪽 서브트리로 이동하는 작업을 R이라고 한다.

전위 순회

전위 순회의 순서는 현재노드(V) -> 왼쪽 서브트리(L) -> 오른쪽 서브트리(R) 순으로 순회 한다. VLR 이라고도 부른다.

전위 순회로 트리를 순회하면 방문하는 노드의 순서이다.

중위 순회

중위 순회의 순서는 왼쪽 서브트리(L) -> 현재노드(V) -> 오른쪽 서브트리(R) 순으로 순회 한다. LVR 이라고도 부른다

중위 순회로 트리를 순회하면 방문하는 노드의 순서이다.

후위 순회

후위 순회의 순서는 왼쪽 서브트리(L) -> 오른쪽 서브트리(R) -> 현재 노드(V) 순으로 순회 한다. LRV 이라고도 부른다.

후위 순회로 트리를 순회하면 방문하는 노드의 순서이다.

JAVA로 순회 구현

1. 먼저 트리를 생성한다.

public class Node {
    private int data;    //노드의 값
    private Node leftNode;    //왼쪽 자식노드의 값
    private Node rightNode;    //오른쪽 자식노드의 값

    public Node(int data, Node leftNode, Node rightNode) {
        this.data = data;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }
    public void setLeftNode(Node node) {
        this.leftNode = node;
    }
    public void setRightNode(Node node) {
        this.rightNode = node;
    }
    public Node getLeftNode() {
        return this.leftNode;
    }
    public Node getRightNode() {
        return this.rightNode;
    }
}

public class TreeClass {
    private Node newNode;    

    //현재는 이진트리탐색이 중요한 부분이 아니기 때문에 단순히 데이터와 좌우 자식노드만 지정해주는 기능만 넣었다.
    public Node makeNode(int data, Node leftNode, Node rightNode) {
        newNode = new Node(data);
        newNode.setLeftNode(leftNode);
        newNode.setRightNode(rightNode);

        return newNode;
    }
}

public class Main {
    public static void main(String[] args) {
        TreeClass tc = new TreeClass();

        Node n50 = tc.makeNode(50, null, null);
        Node n60 = tc.makeNode(60, null, null);
        Node n20 = tc.makeNode(20, n50, n60);
        Node n30 = tc.makeNode(30, null, null);
        Node n10 = tc.makeNode(10, n20, n30);

        /*
         *         10
         *       /        \
         *   20      30
         *  /  \
         * 50   60
         * 이런 구조의 트리 완성 root노드는 n10임
         */

    }
}

             10
          /     \
        20      30
       /  \
     50   60

이런 구조의 트리 생성한다.

트리를 생성하는 방법에는 1차워배열, 2차원배열, 노드 클래스 3가지 방법이 있다. 이 포스팅에서는 노드 클래스로 생성하였다. 관련 생성 방법을 보고싶으면 [자료구조] 트리(Tree)의 개념과 정리 글을 참고해보길 바란다.

2. 전위(preOrder) 중위(inOrder) 후위(postOrder) 메서드 생성

public class TreeClass {
    .
    .
    .

    //전위
    public void preOrder(Node node) {
        if(node !=null) {    
            System.out.print(node.getData() + " ");
            preOrder(node.getLeftNode());
            preOrder(node.getRightNode());
        }
    }

    //중위
    public void inOrder(Node node) {
        if(node != null) {
            inOrder(node.getLeftNode());
            System.out.print(node.getData() + " ");
            inOrder(node.getRightNode());
        }
    }

    //후위
    public void postOrder(Node node) {
        if(node !=null) {
            postOrder(node.getLeftNode());
            postOrder(node.getRightNode());
            System.out.print(node.getData()+" ");
        }
    }
}

함수를 지정한후 실행

System.out.println("PreOrder:");
        tc.preOrder(n10);
        System.out.println("\nInOrder:");
        tc.inOrder(n10);
        System.out.println("\nPostOrder:");
        tc.postOrder(n10);

출력

PreOrder:
10 20 50 60 30 
InOrder:
50 20 60 10 30 
PostOrder:
50 60 20 30 10 

출력결과를 보면 전위, 중위, 후위 순회가 제대로 출력된 것을 볼수 있다.

---

반복적 순회

반복을 이용해서 순회를 할수 있다.
스택(Stack)을 사용해 자식 노드들을 저장하고 꺼내면서 순회하면 중위 순회화 결과가 동일하다.

1. 이진트리의 왼쪽 노드들을 null 노드에 접근할때까지 스ㅐㄱ에 추가한다.
2. null 노드에 도달하면 스택에서 하나씩 pop()을 하면서 pop()으로 삭제된 노드를 출력한다.
3. pop후 pop()되어진 오른쪽 노드로 이동한다.

//반복으로 스택을 이용한 순회 중위 순회와 같음
    public void iterativeOrder(Node root) {
        Stack<Node> stack = new Stack<>();    //반복적 순회를 위한 스택 생성

        //루트 노드부터 시작 루트가 null이 아니거나 스택이 비어있지 않을때 true
        //이 조건이 중요하다 root가 null인데 인데  스택에 값이 들어가 있는 경우가 V(루트노드)를 읽는 순간이다.
        while(root !=null || !stack.isEmpty()) {    
            //현재 노드의 왼쪽노드들을 null에 도달할 때까지 스택에 추가한다.
            while(root !=null) {
                stack.push(root);
                root = root.getLeftNode();
            }

            root = stack.pop();
            System.out.print(root.getData() + " "); //삭제될 노드를 출력

            //삭제된 노드를 출력한 후 이 노드의 오른쪽 노드로 이동
            root = root.getRightNode();
        }
    }

레벨 순회

각 노드를 레벨 순으로 검사하는 순회 방법이다. 루트의 레벨이 1이고 아래로 내려갈수록 레벨의 숫자가 증가한다. 같은 레벨에서는 무조건 좌에서 우로 읽는다. 큐(Queue)를 사용한다.

//레벨 순회
    public void levelOrder(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);    //큐에 root노드 삽입

        while(!queue.isEmpty()) {
            Node node = queue.poll(); //이 부분이 제일 중요
            System.out.print(node.getData() + " ");

            //노드를 출력할때마다 출력되는 노드의 자식노드들을 바로 큐에 넣게 됨 
            if(node.getLeftNode() != null) queue.offer(node.getLeftNode());
            if(node.getRightNode() != null) queue.offer(node.getRightNode());
        }
    }
    ```