이진 트리 🌲

모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree) 라고 부른다.

🍳 이진 트리의 성질

n개의 노드를 가진 이진 트리는 n-1개의 간선을 가진다.
높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 2^h - 1 개의 노드를 가진다.
n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소 log2(n+1)이 된다. (2는 밑)

1. 이진 트리의 표현

🍔 배열 표현법

🍔 링크 표현법

class Node {
    Object data;
    Node left, right;
    public Node(Object data) {
        this.data = data;
    }
}

2. 이진 트리의 순회

🥨 전위 순회 (preorder traversal)

V -> L -> R

void preorder(Node root) {
	System.out.print(root.data);
	if (root.left != null) {
		preorder(root.left);
	}
    if (root.right != null) {
        preorder(root.right);
    }
}

🥨 중위 순회 (inorder traversal)

L -> V -> R

void inorder(Node root) {
    if (root.left != null) {
        inorder(root.left);
    }
    System.out.print(root.data);
    if (root.right != null) {
        inorder(root.right);
    }
}

🥨 후위 순회 (postorder traversal)

L -> R -> V

void postorder(Node root) {
    if (root.left != null) {
        postorder(root.left);
    } 
    if (root.right != null) {
        postorder(root.right);
    }
    System.out.print(root.data)
}

3. 이진 트리 삽입

// 데이터가 1 1 . 의 형식으로 들어온다고 가정
// .은 연결된 노드가 없다는 뜻임
class Tree {
    Node root;
    void add(Object data, Object leftData, Object rightData) {
        if (root == null) {
            if (data != '.') {
                root = new Node(data);
            }
            if (leftData != '.') {
                root.left = new Node(data);
            }
            if (rightData != '.') {
                root.right = new Node(data);
            }
        }
        else {
            search(root, data, leftData, rightData);
        }
    }
    
    void search(Node root, Object data, Object leftData, Object rightData) {
        if (root == null) {
            return ;
        }
        else if (root.data == data) {
            if (leftData != '.') {
                root.left = new Node(leftData);
            }
            if (rightData != '.') {
                root.right = new Node(rightData);
            }            
        }
        else {
            search(root.left, data, leftData, rightData);
            search(root.right, data, leftData, rightData);
        }
    }
}