[JAVA/자료구조] 강의노트 4-2강 : 이진트리의 순회(Tree Traversal), 전위순회(Preorder Traversal), 후위 순회(Post Traversal), 중위 순회(Inorder Traversal) 구현

안녕하세요. 오늘은 이진트리에서 순회하는 방식에 대하여 알아보겠습니다.

다른 List형 자료구조를 출력하는 것과 달리, Tree는 계층적 구조이기 때문에,

그 구조를 글로 표현할 때 일정한 규칙에 따라 표현됩니다.

그리고 그 규칙을 순회라고 부르는데, 오늘 세가지 순회방식을 살펴보겠습니다.

---

!) 자료구조 Tree를 잘 모르시다면?

Tree 개념설명 보러가기

---

 

* 본 구현에 사용된 Node, Tree 코드는 글 하단에 있습니다.

 

1) Preorder

A - B - D- E- C- F -G

Root부터 시작하여 모든 왼쪽 노드를 순회한 후 오른쪽의 노드를 순회하는 방식입니다.

 public void preOrder(MyBinNode v) {
        
        System.out.print(v.element()+" ");
        
        if(this.hasLeft(v))
            preOrder(this.left(v));
        
        if(this.hasRight(v))
            preOrder(this.right(v));
        
    }

 

2) Postorder

D - E - B - F - G - C -A

맨 왼쪽 아래노드부터 오른쪽 노드를 탐색 후 루트를 마지막으로 방문하는 방식입니다.

    public void postOrder(MyBinNode v) {
        
        if(this.hasLeft(v)) {
            System.out.print("(");
            inOrder(this.left(v));
        }
                        
        if(this.hasRight(v)) {
            inOrder(this.right(v));
            System.out.print(")");
        }
        
        System.out.print(v.element()+"");    
    }

 

3) Inorder

D - B - E - A - F -C -G

맨 왼쪽 아래노드부터 시작하여 루트, 오른쪽 노드를 순회하는 방식입니다.

    public void inOrder(MyBinNode v) {
        
        if(this.hasLeft(v)) {
            System.out.print("(");
            inOrder(this.left(v));
        }
                    
        System.out.print(v.element()+"");        
        
        if(this.hasRight(v)) {
            inOrder(this.right(v));
            System.out.print(")");
        }
    }

---

'Tree + Node'코드 보러가기

---

Binary Seach Tree 구현을 위해선 트리 순회를 알아야 하기 때문에 간단하게 트리 순회에 대하여 알아보았습니다.

다음시간엔 BST에 관한 글로 찾아 뵙겠습니다. 감사합니다 :)