#include "BinarySearchTree.h"
#include <cstdlib>
#include <cstdio>

BinarySearchTree::BinarySearchTree(void):m_root(0)
{
}


BinarySearchTree::~BinarySearchTree(void)
{
}

void BinarySearchTree::insert(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 (m_root == 0)    // 目前無資料
        m_root = new_node;
    else
    {
        current = m_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;
}

void BinarySearchTree::print_inorder(void)
{
    print_inorder(m_root);
}


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


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


void BinarySearchTree::freeMem(void)
{
    freeMem(m_root);
}


void BinarySearchTree::freeMem(BSTNode* ptr)
{
    if (ptr != 0)
    {
        freeMem(ptr->left);       // 釋放左子樹
        freeMem(ptr->right);      // 釋放右子樹
        free(ptr);
    }
}
