[자료구조] 이진트리란 && 전위 중위 후위 순회 구현(Java)

이진트리

• 많아야 두 개의 자식 노드를 가짐
• 왼쪽 자식과 오른쪽 자식으로 구분
• 완전이진트리처럼 트리의 균형이 유지가 되지 않음
• 균형이 없는 트리이기 때문에 연결리스트로 표현하는 게 적합
• root node로부터 이진트리를 표현한다.
• 연결리스트로 표현 돼서 배열처럼 트리의 원소를 찾기 힘들다.
  • 그래서 이진트리는 순회 알고리즘을 이용해서 노드의 수나 정점을 찾는다.

이진트리의 순회 방법

1. 전위 (VLR)
2. 중위 (LVR)
3. 후위 (LRV)

기준은 visit을 기준으로 전위 중위 후위를 나눈다

 

전위(Preorder traversal)

root node부터 시작한다.

• Visit 하고
• 왼쪽(left)으로 가고(visit)한다.
• 왼쪽이 없으면 오른쪽으로 간다.(Right)

• 위 순서대로 방문한다.

중위(Inorder traversal)

root node부터 시작한다.

• 왼쪽(left)으로 가고(visit)한다.
• Visit 하고
• 왼쪽이 없으면 오른쪽으로 간다.(Right)

후위(Postorder traversal)

root node부터 시작한다.

• 왼쪽(left)으로 가고(visit)한다.
• 왼쪽이 없으면 오른쪽으로 간다.(Right) 오른쪽이 없으면
• Visit 한다.

트리의 노드 수와 리프노드 수

• 전위 중위 후위를 사용해서 노들의 수를 알 수 있다.
• 전위 중위 후위를 사용해서 리프노드의 수를 알 수 있다.

순회 구현 (Java)

class Node{
    int data;
    Node left;
    Node right;
    public Node(int data){
        this.data = data;
        this.left = null;
        this.right = null;
    }
}


public class Main {
    public static void VLR(Node root){
        if (root == null){
            return;
        }
        else{
            System.out.print(root.data+"->");
            VLR(root.left);
            VLR(root.right);
            return;
        }
    }
    public static void LVR(Node root){
        if(root == null){
            return;
        }
        else{
            LVR(root.left);
            System.out.print(root.data + "->");
            LVR(root.right);

        }
    }
    public static void LRV(Node root){
        if(root == null){
            return;
        }
        else{
            LRV(root.left);
            LRV(root.right);
            System.out.print(root.data + "->");
        }
    }
    public static void main(String []args){
        Node root = new Node(10);
        root.left = new Node(15);
        root.right = new Node(20);
        root.left.right  = new Node(3);
        root.left.right.right = new Node(6);
        root.right.left = new Node(8);
        VLR(root);
        System.out.println();
        LVR(root);
        System.out.println();
        LRV(root);
    }

}