[algorithm] binary tree

• binary tree 정의
• binary tree 종류
  • full binary tree
    • 모든 node는 0개 혹은 2개의 child
  • perfect binary tree
    • 모든 interior node는 2개의 child, 모든 leaf는 같은 level에 존재
  • complete binary tree
    • 마지막 level 이전은 perfect binary tree, 마지막 level(h)은 왼쪽부터 채워지고 1 ~ (2^h - 1)까지만 가능
• binary tree 특징
  • 일반적으로 array로 표현 가능하다.
    • root : 0
    • left child : 2*i + 1
    • right child : 2*i + 2
    • parent : (i-1)/2
    • level(depth) : h (0은 root)
    • level h에 가능한 node의 최대값 : 2^h
    • perfect binary tree에서 node의 수가 n일 때, depth는 log(n+1) - 1
• binary tree 순회
  • stack(recursive)
    • in-order : left -> parent -> right
      • 만약 binary search tree(left <= parent <= right 관계를 만족하는 binary tree)라고 한다면, 특정 node에서 in-order traversal하면 항상, 그 node보다 더 작은 왼쪽 방향 node들을 정렬된 순서로 방문된다. 그리고 나서 node 자신을 방문하고, 오른쪽 방향 node들을 정렬된 순서로 방문한다.
      • 따라서, binary search tree에서 k번째 작은 값을 구하는 방법에 참조할 수 있다. 물론, 배열로 구현된 경우는 array의 index로 바로 접근 가능하다.
    • pre-order : parent -> left -> right
    • post-order : left -> parent -> right
  • queue
    • level-order : level i를 모두 방문하고 level i+1으로 이동

    root를 enqueue
    while is_empty(queue)
      dequeue, visit
      left child enqueue
      right child enqueue
    

  • sample code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void inorder(int* list, int parent, int size)
{
    int left, right;

    left = 2*parent + 1;
    right = 2*parent + 2;
    if( left < size ) {
        inorder(list, left, size);
    }
    fprintf(stdout, "%d ", list[parent]);
    if( right < size ) {
        inorder(list, right, size);
    }
}

void preorder(int* list, int parent, int size)
{
    int left, right;

    left = 2*parent + 1;
    right = 2*parent + 2;
    fprintf(stdout, "%d ", list[parent]);
    if( left < size ) {
        preorder(list, left, size);
    }
    if( right < size ) {
        preorder(list, right, size);
    }
}

void postorder(int* list, int parent, int size)
{
    int left, right;

    left = 2*parent + 1;
    right = 2*parent + 2;
    if( left < size ) {
        postorder(list, left, size);
    }
    if( right < size ) {
        postorder(list, right, size);
    }
    fprintf(stdout, "%d ", list[parent]);
}

typedef struct {
    int idx;
    int value;
} element_t;

int enqueue(element_t** queue, int qsize, int* rear, int* front, element_t* element)
{
    // push element to rear
    if( *rear >= qsize ) return 0;

    queue[*rear] = element;
    *rear += 1;
    if( *front == -1 ) *front = 0;
    return 1;
}

element_t* dequeue(element_t** queue, int qsize, int* rear, int* front)
{
    element_t* element;

    if( *front == -1 ) return NULL;

    // pop element from front
    element = queue[*front];
    *front += 1;
    if( *front > *rear ) {
        *front = -1;
        *rear = 0;
    }
    return element;
}

void levelorder(element_t* elements, int parent, int size)
{
    int qsize = size;
    int front = -1;
    int rear = 0;
    element_t** queue = (element_t**)malloc(qsize * sizeof(element_t*));
    element_t* element;
    int left;
    int right;

    // enqueue root
    enqueue(queue, qsize, &rear, &front, &elements[parent]);
    while( (element = dequeue(queue, qsize, &rear, &front)) != NULL ) {
        fprintf(stdout, "%d ", element->value);
        left = (element->idx)*2 + 1;
        right = (element->idx)*2 + 2;
        if( left < size ) {
            enqueue(queue, qsize, &rear, &front, &elements[left]);
        }
        if( right < size ) {
            enqueue(queue, qsize, &rear, &front, &elements[right]);
        }
    }
    if( queue ) free(queue);
}

int main(int argc, char** argv)
{
    int list[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    // 8 4 9 2 10 5 1 6 3 7
    inorder(list, 0, 10);
    fprintf(stdout, "\n");

    // 1 2 4 8 9 5 10 3 6 7
    preorder(list, 0, 10);
    fprintf(stdout, "\n");

    // 8 9 4 10 5 2 6 7 3 1
    postorder(list, 0, 10);
    fprintf(stdout, "\n");

    // copy list -> elements
    element_t elements[10] = { {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10} };
    levelorder(elements, 0, 10);
    // 1 2 3 4 5 6 7 8 9 10
    fprintf(stdout, "\n");

    return 0;
}