이진트리의 개념

이진 트리란 자식을 둘 이하 가진 트리이다.
오늘 면접에서 코드를 만들 때 둘 이상으로 만들었다...

위의 그림처럼
자식이 0, 1, 2까지는 모두 이진트리이고 자식이 3명이 되는 순간 이진트리가 아니다.

이진트리의 속성

• 이진트리에서 각 레벨에서 최대 노드의 수는 2^(레벨) 이다.
  

• 특정 높이에서 가질 수 있는 최대 노드의 수는 레벨 0 일때를 제외하고 2^(높이) -1 이다. 레벨 0 은 1이다.
  

이진트리 순회(Traversal)

전위 순회

• 부모노드 > 왼쪽 자식노드 > 오른쪽 자식노드 순서로 순회하기
  0->1->3->7->8->4->9->10->2->5->11->6

중위 순회

• 왼쪽 자식노드 > 부모노드 > 오른쪽 자식노드 순서로 순회하기
  7->3->8->1->9->4->10->0->11->5->2->6

후위 순회

• 왼쪽 자식노드 > 오른쪽 자식노드 > 부모노드 순서로 순회하기
  7->8->3->9->10->4->1->11->5->6->2->0

이진트리 종류

정 이진트리 (Full Binary Tree or Strict Binary Tree)

모든 노드가 0 또는 2개의 자식 노드를 갖는 트리

완전 이진 트리 (Complete Binary Tree)

완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리
마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

포화 이진 트리 (Perfect Binary Tree)

포화 이진 트리는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는다

균형 이진 트리 (Balanced Binary Tree)

균형 이진 트리는 왼쪽과 오른쪽 트리의 높이 차이가 모두 1만큼 나는 트리

편향 이진 트리 (skewed binary tree)

모든 노드가 왼쪽에 있거나 오른쪽에만 있는 트리

이진 탐색 트리 (Binary Search Tree)

모든 왼쪽 자식 노드는 부모 노드의 값보다 작고, 모든 오른쪽 자식 노드는 부모의 값보다 크며 값의 중복은 없다.

• 중복 노드가 없어야 하는 이유 : 검색 목적의 자료구조인데 굳이 중복을 추가하여 검색 속도를 느리게 할 필요가 없다.

Java에서 이진 트리 노드 구현

class Node {
    int value;
    Node leftChild;
    Node rightChild;

    public Node(int value) {
        this.value = value;
        this.leftChild = null;
        this.rightChild = null;
    }
}

위와 같이 노드를 데이터, 왼쪽 자식, 오른쪽 자식으로 구성할 수 있다.

노드를 활용하여 이진 탐색 트리 구현

class BinaryTree {
    Node rootNode = null;

    // 삽입
    public void insertNode(int element) {

        // 루트가 없는 경우
        if (rootNode == null) {
            rootNode = new Node(element);
        } else {
            Node head = rootNode;
            Node currentNode;

            while (true) {
                currentNode = head;

                // head보다 작기때문에 왼쪽으로 탐색
                if (head.value > element) {
                    head = head.leftChild;
                    
                    // 비어있으면 왼쪽 노드에 넣기
                    if (head == null) {
                        currentNode.leftChild = new Node(element);
                        break;
                    }
                } else {
                    // 큰 경우 오른쪽 탐색
                    head = head.rightChild;
                    if (head == null) {
                        currentNode.rightChild = new Node(element);
                        break;
                    }
                }
            }
        }
    }
}