본문 바로가기

전산 기초/자료구조

[자료구조/java] 이진 트리 (Binary Tree) 의 순회 (traversal)


* 이진 트리 (Binary Tree) 의 순회 (traversal)


"순회(traversal)"  이진 트리에 있는 모든 노드를 한번씩 모두 방문하여 노드가 가지고 있는 데이터를 처리하는 것


- 리스트나 스택, 큐와 같은 선형 자료구조는 순회하는 방법이 한 가지였지만, 트리는 계층적인 구조를 가지고 있기 때문에 여러가지 순회 방법이 있을 수 있다.

  (1) 현재 노드를 방문하여 데이터를 읽는 작업 D

  (2) 현재 노드의 왼쪽 서브트리로 이동하는 작업 L

  (3) 현재 노드의 오른쪽 서브트리로 이동하는 작업 R 


- 서브트리를 순회하는 순서는 항상 왼쪽 서브트리를 먼저 방문하고, 그 후에 오른쪽 서브트리를 방문한다.

- 노드를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나눌 수 있다.



★ 전위 순회 (Preorder Traversal)

"(1) 현재 노드를 방문하여 데이터를 읽는 작업 D" 을 가장 먼저 수행하여 DLR 의 순서로 순회하는 방법



★ 중위 순회 (Inorder Traversal)

"(1) 현재 노드를 방문하여 데이터를 읽는 작업 D" 을 L과 R의 사이에 수행하여 LDR 의 순서로 순회하는 방법



★ 후위 순회 (Postorder Traversal)

"(1) 현재 노드를 방문하여 데이터를 읽는 작업 D" 을 가장 나중에 수행하여 LRD 의 순서로 순회하는 방법


TreeNode.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package Tree;
 
public class TreeNode {
    Object data;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(Object data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
    
    public Object getData(){
        return this.data;
    }
}


LinkedTree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package Tree;
 
public class LinkedTree {
    private TreeNode root;
    
    public TreeNode makeBT(TreeNode bt1, Object data, TreeNode bt2){
        TreeNode root = new TreeNode(data);
        root.left = bt1;
        root.right = bt2;
        return root;
    }
    
    public void preorder(TreeNode root){
        if(root!=null){
            System.out.print(root.data + " ");
            preorder(root.left);
            preorder(root.right);
        }
    }
    
    public void inorder(TreeNode root){
        if(root!=null){
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }
    
    public void postorder(TreeNode root){
        if(root!=null){
            postorder(root.left);
            postorder(root.right);
            System.out.print(root.data + " ");
        }
    }
}


Test.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package Tree;
 
public class Test {
    public static void main(String[] args) {
        LinkedTree tree = new LinkedTree();
        
        TreeNode n7 = tree.makeBT(null'D'null);
        TreeNode n6 = tree.makeBT(null'C'null);
        TreeNode n5 = tree.makeBT(null'B'null);
        TreeNode n4 = tree.makeBT(null'A'null);
        TreeNode n3 = tree.makeBT(n6, '/', n7);
        TreeNode n2 = tree.makeBT(n4, '*', n5);
        TreeNode n1 = tree.makeBT(n2, '-', n3);
        
        System.out.print("\nPreorder : ");
        tree.preorder(n1);
        
        System.out.print("\nInorder : ");
        tree.inorder(n1);
        
        System.out.print("\nPostorder : ");
        tree.postorder(n1);
    }
}