#include <cstdio>  // printf()
#include <cstdlib> // malloc()
#include <cassert> // assert()

struct binary_search_tree_node
{
    int data;
    struct binary_search_tree_node *left;
    struct binary_search_tree_node *right;
};
typedef struct binary_search_tree_node BSTNode;

void print_inorder(BSTNode *ptr);
BSTNode *insert_node(BSTNode *root, int value);
BSTNode *find_node(BSTNode *ptr, int value);

int main()
{
    int data[] = {10, 20, 5, 8, 30, 15, 1, 18};
    int ndata = sizeof(data)/sizeof(int);
    int i;
    BSTNode *head = 0, *ptr;

    for (i=0; i<ndata; i++)
        head = insert_node(head, data[i]);

    printf("In order listing: ");
    print_inorder(head);
    printf("\n");

    ptr = find_node(head, 15);
    assert(ptr);

    ptr = find_node(head, 11);
    assert(!ptr);

    system("pause");
    return 0;
}

// 中序走訪
void print_inorder(BSTNode *ptr)
{
    if (ptr != 0)
    {
        print_inorder(ptr->left);    // 走左子樹
        printf("%2d ", ptr->data);   // 印出節點內容
        print_inorder(ptr->right);   // 走右子樹
    }
}

// 插入節點
BSTNode *insert_node(BSTNode *root, int value)
{
    BSTNode *new_node;
    BSTNode *current;
    BSTNode *parent;

    // 建立節點
    new_node = (BSTNode *) malloc(sizeof(BSTNode));
    new_node->data = value;
    new_node->left = 0;
    new_node->right = 0;
    if (root == 0)    // 目前無資料
    {
        return new_node;
    }
    else
    {
        current = root; // 從頭找要新節點之插入點
        while (current != 0)
        {
            parent = current;       // 找新節點之父節點
            if (current->data > value)
                current = current->left;    // 往左找
            else
                current = current->right;   // 往右找
        }
        if (parent->data > value)    // 插入此父節點左邊或右邊
            parent->left = new_node;
        else
            parent->right = new_node;
    }
    return root;    // 回傳此樹
}

// 尋找節點
BSTNode *find_node(BSTNode *ptr, int value)
{
    // 從 ptr 指到的節點開始找
    while (ptr != 0)
    {
        if (ptr->data == value)
            return ptr; // 如果找到目標, 回傳此節點位址
        else if (value < ptr->data)
            ptr = ptr->left;  // 如果 value 比目前節點的鍵值小, 往左找
        else
            ptr = ptr->right; // 如果 value 不小於目前節點的鍵值, 往右找
    }
    return 0; // 找不到
}