[Java][자료구조] Tree (3) - 이진트리 순회 구현과 예시

저번 시간에 이진트리 구현과 순회에 대해 알아봤으니 바로 순회 코드를 보도록 하자!

 

순회 코드

import java.util.LinkedList;
import java.util.Queue;
 
public class BT <key>{
    private Node<key> root;
    
    public BT(Node<key> root) {
        this.root = root;
    }
    
    public Node<key> getRoot() {
        return root;
    }
    //전위 순회
    public void preorder(Node<key> n) {
        if(n!=null) {
            System.out.print(n.getKey() + " ");
            preorder(n.getLeft());
            preorder(n.getRight());
        }
    }
 
    //중위 순회
    public void inorder(Node<key> n) {
        if(n!=null) {
            inorder(n.getLeft());
            System.out.print(n.getKey() +" ");
            inorder(n.getRight());
        }
    }
    //후위 순회
    public void postorder(Node<key> n) {
        if(n!=null) {
            postorder(n.getLeft());
            postorder(n.getRight());
            System.out.print(n.getKey() + " ");
        }
    }
    //레벨 
    public void levelorder(Node<key> n) {
        Queue<Node<key>> q = new LinkedList<Node<key>>();
        Node<key> t;
        q.add(n);
        
        while(!q.isEmpty()) {
            t = q.remove();
            System.out.print(t.getKey() + " ");
            if(t.getLeft()!=null) q.add(t.getLeft());
            if(t.getRight()!=null) q.add(t.getRight());
        }
    }
    
}
 

전위, 중위, 후위순회는 규칙이 있기 때문에 재귀호출을 사용하였고, 레벨 순회는 Queue를 이용하였다.

 

레벨 순회에 대해 좀 더 설명해 보자면 Queue를 만들고 그 큐에 root노드를 넣는다. 후에 왼쪽 자식이 있다면 왼쪽 자식을 큐에 넣고 오른쪽 자식이 있다면 오른쪽 자식을 큐에 넣는다. 그러면 그 큐에는 부모 노드 - 왼쪽 자식 노드 - 오른쪽 자식 노드 순으로 들어갈 것이고 그것은 전체 트리에 적용될 것이다. 이제 큐의 특성을 이용해 앞에서 부터 나온다면 레벨 순회가 완성 된다.

 

Main

public class Main {
 
    public static void main(String[] args) {
        Node<Character> n8 = new Node<Character>('H', null, null);
        Node<Character> n7 = new Node<Character>('G', null, null);
        Node<Character> n6 = new Node<Character>('F', null, null);
        Node<Character> n5 = new Node<Character>('E', n8, null);
        Node<Character> n4 = new Node<Character>('D', null, n7);
        Node<Character> n3 = new Node<Character>('C', null, n6);
        Node<Character> n2 = new Node<Character>('B', n4, n5);
        Node<Character> n1 = new Node<Character>('A', n2, n3);
        
        BT<Character> bt = new BT<Character>(n1);
        System.out.println("트리 노드 수 = " + bt.size(bt.getRoot()));
        System.out.println("트리 높이 = " + bt.height(bt.getRoot()));
        System.out.print("전위 순회: "); bt.preorder(bt.getRoot());
        System.out.print("\n중위 순회: "); bt.inorder(bt.getRoot());
        System.out.print("\n후위 순회: "); bt.postorder(bt.getRoot());
        System.out.print("\n레벨 순회: "); bt.levelorder(bt.getRoot());
        
        System.out.println();
 
 
    }
 
}
 
 

트리는 완전 이진트리 모양으로 A~H까지 노드가 있는 모양이다. 결과를 바로 보자.

결과

순회는 꼭 루트노드에서만 되는게 아니라 어느 서브트리에서든 다 적용된다. 하나씩 해보면서 순회에 대해 익숙해져보자!