이진 트리 (Binary Tree)

트리를 공부할 때 하나의 노드에 대해 무제한으로 하위 항목(자식 노드)를 추가할 수 있었다.

하지만 이진 트리의 경우에는 왼쪽, 오른쪽으로 최대 2개의 자식 노드를 갖는 데이터 구조이다.

이진 트리 기본 구조

완전한 이진트리는 마지막 레벨에 모든 노드가 위치해있다.

트리의 자료구조에는 이진 검색 트리, 힙 트리, AVL 트리, 레드-블랙 트리 등이 있다.

이들은 모두 이진 트리이며 기본 속성은 이진 트리에서 파생된 것이다.

이진 트리를 구성하는 방법은 2가지가 있다.

1. Linked List

노드에서 왼쪽 포인터와 오른쪽 포인터를 가진다. 이 포인터는 자식 노드의 물리적인 위치를 표시한다.

• 포인터가 null일 경우 자식 노드가 없다는 의미이다.

public class BinaryNode {
    public String value;
    public BinaryNode left;
    public BinaryNode right;
    public int height;
}

public class BinaryTryeLinkedList {
    BinaryNode root;

    public BinaryTryeLinkedList() {
        this.root = null;
    }

    // PreOrder Traversal : root -> left subtree -> right subtree
    void preOrder(BinaryNode node) {
        if (node == null) return;
        System.out.print(node.value + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    // InOrder Traversal : left subtree -> root -> right subtree
    void inOrder(BinaryNode node) {
        if (node == null) return;
        inOrder(node.left);
        System.out.print(node.value + " ");
        inOrder(node.right);
    }

    // Post Traversal : left subtree -> right subtree -> root
    void postOrder(BinaryNode node) {
        if (node == null) return;
        postOrder(node.left);
        preOrder(node.right);
        System.out.print(node.value + " ");
    }

    // Level Order
    void levelOrder() {
        Queue<BinaryNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            BinaryNode presentNode = queue.poll();
            System.out.print(presentNode.value + " ");

            if (presentNode.left != null) queue.add(presentNode.left);
            if (presentNode.right != null) queue.add(presentNode.right);
            System.out.println();
        }
    }

    // Search Method = levelOrder를 사용한다.
    public void search(String value) {
        Queue<BinaryNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            BinaryNode presentNode = queue.poll();

            if (presentNode.value == value) {
                System.out.println("find Value : " + value);
                return;
            } else {
                if (presentNode.left != null) queue.add(presentNode.left);
                if (presentNode.right != null) queue.add(presentNode.right);
            }
        }
        System.out.println("value not found");
    }

    // Insert Method
    void insert(String value) {
        BinaryNode newNode = new BinaryNode();
        newNode.value = value;

        if (root == null) {
            root = newNode;
            return;
        }

        Queue<BinaryNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            BinaryNode presentNode = queue.poll();

            if (presentNode.left == null) {
                presentNode.left = newNode;
                break;
            } else if (presentNode.right == null) {
                presentNode.right = newNode;
                break;
            } else {
                queue.add(presentNode.left);
                queue.add(presentNode.right);
            }
        }
    }
}

1. Array

계산의 편의를 위해서 0번 인덱스는 비어두고, 1번 인덱스부터 시작한다.

왼쪽, 오른쪽 자식의 인덱스는 다음과 같은 공식으로 표현한다.

• Left Child = arr[2x]

• Right Child = arr[2x + 1]