[자료구조/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);     } }