[Java][자료구조] Tree (2) - 이진 트리 구현과 전위,중위,후위,레벨 순회

 

Binary Tree 구현

이제 이진 트리를 구현하도록 하겠다. 필요한 클래스는 Node, Binary Tree 그리고 예시를 들어볼 Main 클래스이다.

 

Node 클래스에는 본인의 key값이 있어야 하고, 그 노드의 자식들에 대한 정보가 필요하다. 또한 key값에는 다양한 것들이 들어올 수 있으므로 제네릭으로 key값을 사용하였다. 코드는 다음과 같다.

 

Node

public class Node <key>{
    private key key;
    private Node<key> left, right;
    
    public Node(key key, Node<key> left, Node<key> right) {
        this.key = key;
        this.left = left; 
        this.right = right;;
    }
 
    public key getKey() {
        return key;
    }
 
    public void setKey(key key) {
        this.key = key;
    }
 
    public Node<key> getLeft() {
        return left;
    }
 
    public void setLeft(Node<key> left) {
        this.left = left;
    }
 
    public Node<key> getRight() {
        return right;
    }
 
    public void setRight(Node<key> right) {
        this.right = right;
    }
}
 

이제 만들어 둔 Node를 이용해서 이진트리를 만들 것이다. 이진탐색트리는 아니기 때문에 기본적으로 root를 설정, size, height를 구하는 메소드와 순회메소드만 있다. 순회 메소드는 아래서 다시 볼 예정이다.

 

Binary Tree

public class BT <key>{
    private Node<key> root;
    
    public BT(Node<key> root) {
        this.root = root;
    }
    
    public Node<key> getRoot() {
        return root;
    }
 
    public int size(Node<key> n) {
        if(n==null) return 0;
        return 1 + size(n.getLeft()) + size(n.getRight());
    }
    
    public int height(Node<key> n) {
        if(n==null) return 0;
        
        return 1 + Math.max(height(n.getLeft()), height(n.getRight()));
    }
        
}
 

순회

Main문을 보기전에 순회에 대해서 알아보겠다. 순회는 트리를 탐색하는 과정이며, 어떤 방식으로 탐색하냐에 따라서 전위 순회(preorder), 중위 순회(inorder), 후위 순회(post order), 레벨 순회(level order)로 나뉜다.

 

전위 순회의 규칙은 해당 노드 x에 도착했을 때 x를 먼저 방문하고 그 다음에 왼쪽 자식으로 순회 x의 왼쪽 서브트리의 모든 노드들을 방문한 후에는 x의 오른쪽 서브트리의 후손 노드들을 방문한다. 전위 순회는 트리의 전송을 할 때와 두 트리가 같은지 비교를 할 때 사용된다.

 

전위 순회 방문 규칙

전위 순회

중위 순회는 x의 왼쪽 서브트리로 순회를 진행하여 왼쪽 서브트리의 모든 노드들을 방문한 후에 x를 방문한다. x 방문 후에는 오른쪽 서브트리를 같은 방식으로 방문한다.

중위 순회 방문 규칙

중위 순회

후위 순회는 x의 왼쪽 서브트리로 순회를 진행한후 x를 방문 하지 않고 x의 오른쪽 서브트리로 순회를 하고 마지막으로 x를 방문한다. 후위 순회는 컴퓨터가 수식을 계산하는 방식에 쓰인다.

후위 순회 방문 규칙

후위 순회

레벨 순회는 루트노드 부터 시작하여 각 레벨마다 좌에서 우로 노드들을 방문하는 것이다.

레벨 순회

다음 시간에 순회의 코드와 Main문에서 예시를 들어가며 자세한 설명을 하도록 하겠다.