[Algorithm]이진 트리 순회(Traversal)

• 순회(traversal): 이진 트리에서 각 노드를 빠짐없이 모두 방문하는 방법
• n개의 노드 구성 이진트리 순회 방법 가지 수: n !
• 3가지 순회 방법 

a. 중위 순회(Inorder)

  - left -> root -> right(왼쪽 부터 노드를 읽음)

// 알고리즘
public void inorder(BinaryTree btree) {
   if (btree.data == null)
      return;
   inorder(btree.ltree);
   System.out.print(btree.data+" ");  // 루트 노드 방문
   inorder(btree.rtree);
} // End of inorder

  => 중위 순회 결과: 8,4,9,2,10,5,11,1,6,3,12,7

 

 b. 전위 순회(Preorder)

   - root -> left -> right(부모에서 왼쪽으로)

// 알고리즘
public void preorder(BinaryTree btree) {
   if (btree.data == null)
      return;
   System.out.print(btree.data+" ");  // 루트 노드 방문
   preorder(btree.ltree);
   preorder(btree.rtree);
} // End of Preorder

   => 전위 순회 결과: 1,2,4,8,9,5,10,11,3,6,7,12

 

 c. 후위 순회(Postorder)

   - left -> right -> root

// 알고리즘
public void postorder(BinaryTree btree) {
   if (btree.data == null)
      return;
   postorder(btree.ltree);
   postorder(btree.rtree);
   System.out.print(btree.data+" ");  // 루트 노드 방문
} // End of PostOrder

   => 후위 순회 결과: 8,9,4,10,5,11,2,6,12,7,3,1

 

•  일반 트리를 이진 트리로 표현

    첫번째 자식 노드만 그대로 두고 나머지는 단절시킴 -> 첫번째 자식 노드 포함한 모든 형제 노드들 오른쪽 링크로 연결