[자료구조] 이진 트리의 순회 (의사코드, 소스코드 포함) :: 늦깎이 IT

이번 포스팅에서는 이진 트리의 순회 방법에 대해 알아봅니다.

[이진 트리]

1. 중위 순회 (Inorder-Traverse)

A → B → C → D → E → F → G → H → I

1) 왼쪽 자식 노드를 중위 순회한다.

2) 루트 노드를 방문한다.

3) 오른쪽 자식 노드를 중위 순회한다.

[의사 코드]

INORDER-TRAVERSE(x)
    if x is not NULL
        then INORDER-TRAVERSE(left[x])
             print key[x]
             INORDER-TRAVERSE(right[x])

---

2. 후위 순회 (Postorder-Traverse)

A → C → E → D → B → H → I → G → F

1) 왼쪽 자식 노드를 후위 순회한다.

2) 오른쪽 자식 노드를 후위 순회한다.

3) 루트노드를 방문한다.

[의사 코드]

POSTORDER-TRAVERSE(x)
    if x is not NULL
        then POSTORDER-TRAVERSE(left[x])
             POSTORDER-TRAVERSE(right[x])
             print key[x]

---

3. 전위 순회 (Preorder-Traverse)

F → B → A → D → C → E → G → I → H

1) 루트노드를 방문한다.

2) 왼쪽 자식 노드를 전위 순회한다.

3) 오른쪽 자식 노드를 전위 순회한다.

[의사 코드]

PREORDER-TRAVERSE(x)
    if x is not NULL
        then print key[x]
             PREORDER-TRAVERSE(left[x])
             PREORDER-TRAVERSE(right[x])

---

4. 레벨오더 순회 (Levelorder Traverse)

F → B → G → A → D → I → C → E → H

1) 첫 번째 레벨의 노드들을 방문한다.

2) 두 번째 레벨의 노드들을 방문한다.

3)  ......................................................................

4) N번째 레벨의 노드들을 방문한다.

[의사코드]

LEVELORDER-TRAVERSE(root)
    if root is not null
        then    Q <- root
                while Q is not empty do
                      v <- deque(Q)
                      print key[v]
                      if children of v is not null
                        then Q <- children
                end

---

[구현 코드]

[Node 클래스]

package datastruct;
 
public class Node<T> {
 
    T data;
    Node leftChild;
    Node rightChild;
 
    public Node(T data, Node leftChild, Node rightChild) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
 
    public Node(T data) {
        this.data = data;
        this.leftChild = null;
        this.rightChild = null;
    }
 
}
 

[BinaryTree 클래스]

package datastruct;
 
import java.util.LinkedList;
import java.util.Queue;
 
public class BinaryTree {
 
    public static <T> Object getData(Node root) {
        return root.data;
    }
 
    public static Node getLeftSubTree(Node root) {
        return root.leftChild;
    }
 
    public static Node getRightSubTree(Node root) {
        return root.rightChild;
    }
 
    public static void setLeftSubTree(Node root, Node leftChild) {
        root.leftChild = leftChild;
    }
 
    public static void setRightSubTree(Node root, Node rightChild) {
        root.rightChild = rightChild;
    }
 
    public static void preorderTraverse(Node root) {
        if (root == null)
            return;
 
        System.out.print(root.data + " ");
        preorderTraverse(root.leftChild);
        preorderTraverse(root.rightChild);
    }
 
    public static void postorderTraverse(Node root) {
 
        if (root == null)
            return;
 
        postorderTraverse(root.leftChild);
        postorderTraverse(root.rightChild);
        System.out.print(root.data + " ");
 
    }
 
    public static void inorderTraverse(Node root) {
        if (root == null)
            return;
 
        inorderTraverse(root.leftChild);
        System.out.print(root.data + " ");
        inorderTraverse(root.rightChild);
    }
 
    public static void levelorderTraverse(Node root) {
 
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            if (node == null)
                continue;
 
            System.out.print(node.data + " ");
            q.offer(node.leftChild);
            q.offer(node.rightChild);
        }
 
    }
 
}
 

[Main 클래스]

package datastruct;
 
public class Main {
 
    public static void main(String[] args) {
 
        Node A = new Node('A');        Node B = new Node('B');
        Node C = new Node('C');        Node D = new Node('D');
        Node E = new Node('E');        Node F = new Node('F');
        Node G = new Node('G');        Node H = new Node('H');
        Node I = new Node('I');
 
        BinaryTree.setLeftSubTree(F, B);
        BinaryTree.setRightSubTree(F, G);
 
        BinaryTree.setLeftSubTree(B, A);
        BinaryTree.setRightSubTree(B, D);
 
        BinaryTree.setLeftSubTree(D, C);
        BinaryTree.setRightSubTree(D, E);
 
        BinaryTree.setRightSubTree(G, I);
        BinaryTree.setLeftSubTree(I, H);
 
        System.out.println("[전위 순회]");
        BinaryTree.preorderTraverse(F);
        System.out.println();
        
        System.out.println("[중위 순회]");
        BinaryTree.inorderTraverse(F);
        System.out.println();
        
        System.out.println("[후위 순회]");
        BinaryTree.postorderTraverse(F);
        System.out.println();
        
        System.out.println("[레벨 순회]");
        BinaryTree.levelorderTraverse(F);
        System.out.println();
 
    }
 
}
 

[실행 결과]

[전위 순회]
F B A D C E G I H 
 
[중위 순회]
A B C D E F G H I 
 
[후위 순회]
A C E D B H I G F 
 
[레벨 순회]
F B G A D I C E H