[알고리즘] 이진 트리 (Binary Tree)의 순회방법 (Java)

미키처럼 여러번 재귀함수 돌면 됩니다.

이진트리 (Binary Tree) 🔗

최대 두개의 자식을 같은 구조

 

이진트리를 순회하는 방법은 크게 3가지가 있다.

• Inorder (left, root, right) : 본인이 왼쪽과 다음 사이에 끼인 순서
• Preorder (root, left, right) : 왼쪽과 다음 전의 순서
• Postorder (left, right, root) : 왼쪽과 다음 후의 순서

 

---

코드

package study;

/*
 *      (1)
       /   \
 *   (2)   (3)
    /     /
 *(4)  (5)

 * 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 TreeA {
    Node root;

    public TreeA() {
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = 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;
    }

    // left root right
    public void inorder(Node node) {
        //제귀함수 종료
        if (node != null) {
            System.out.println("검사하려는 값" + node.data);

            //왼쪽
            System.out.println(node.data + "의 왼쪽" + node.left);
            inorder(node.left);
            //자기 자신
            System.out.println("출력" + node.data);
            //오른쪽
            System.out.println(node.data + "의 오른쪽" + node.right);
            inorder(node.right);
        }
    }

    // root left right
    public void preorder(Node node) {
        //제귀함수 종료
        if (node != null) {
            //자기 자신
            System.out.println(node.data);
            //왼쪽
            preorder(node.left);
            //오른쪽
            preorder(node.right);
        }
    }

    // left right root
    public void postorder(Node node) {
        //제귀함수 종료
        if (node != null) {
            //왼쪽
            postorder(node.left);
            //오른쪽
            postorder(node.right);
            //자기 자신
            System.out.println(node.data);
        }
    }

}

class Node {
    int data;
    Node left;
    Node right;
}

public class BinaryTreePrintValue {
    public static void main(String[] args) {
        TreeA t = new TreeA();
        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);
        t.inorder(t.getRoot());
    }
}

출력
4 2 5 1 3

 

---

코드 작동과정

역시 재귀함수는 손으로 한 번은 써봐야 제 맛.. 반복문을 인간이 적다 보니 무너지는 글씨체.. 눈감아 주세요. 하하

 

✔️ Inorder (left, root, right)

 

✔️ Preorder (root, left, right)

 

✔️ Postorder (left, right, root)

 

학습처, 코드 출처

https://www.youtube.com/watch?v=QN1rZYX6QaA&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP&index=2