/* 二叉搜索樹
 * 
 */

#ifndef BINARY_SEARCH_TREE_CLASS
#define BINARY_SEARCH_TREE_CLASS

#include <stdlib.h>
#include "treenode.h"

template <class T>
class BinSTree
{
    private:
        // 指向樹根及當前結點的指針
        TreeNode<T> *root;
        TreeNode<T> *current;
        
        // 樹中數據項個數
        int size;
      
        // 用于復制構造函數及賦值運算符
        TreeNode<T> *CopyTree(TreeNode<T> *t);
        
        // 用于析構函數，賦值運算符及 ClearList 方法
        void DeleteTree(TreeNode<T> *t);

        // 在函數 Find 和 Delete 中用來定位結點及其雙親在樹中的位置
        TreeNode<T> *FindNode(const T& item, TreeNode<T>* & parent) const;

    public:
        // 構造函數，析構函數
        BinSTree(void);
        BinSTree(const BinSTree<T>& tree);
        ~BinSTree(void);
        
        // 賦值運算符
        BinSTree<T>& operator= (const BinSTree<T>& rhs);
        
        // 標準的表處理方法
        bool Find(T& item);
        void Insert(const T& item);
        void Delete(const T& item);
        void ClearList(void);
        bool ListEmpty(void) const;
        int ListSize(void) const;
        
        // 樹的特殊方法
        void Update(const T& item);
        TreeNode<T> *GetRoot(void) const;
};

// 復制樹 t 并使其存儲在當前對象中
template <class T>
TreeNode<T> *BinSTree<T>::CopyTree(TreeNode<T> *t)
{
    TreeNode<T> *newlptr, *newrptr, *newNode;
   
    // 如果樹分支為空，返回 NULL
    if (t == NULL)
        return NULL;
        
    // 復制樹 t 的左子樹并將其根分配給 newlptr
    if (t->left != NULL) 
        newlptr = CopyTree(t->left);
    else
        newlptr = NULL;
 
    // 復制樹 t 的右子樹并將其根分配給 newrptr
    if (t->right != NULL) 
        newrptr = CopyTree(t->right);
    else
        newrptr = NULL;
 
    // 為當前根結點分配存儲器并將其數據值和指針分配給它的子樹，返回其指針
    newNode = new TreeNode<T>(t->data, newlptr, newrptr);
    return newNode;
}

// 刪除當前對象存儲的樹
template <class T>
void BinSTree<T>::DeleteTree(TreeNode<T> *t)
{
    if (t != NULL)
    {
        DeleteTree(t->left);
        DeleteTree(t->right);
        delete t;
    }
}

// 在樹中搜索數據項，若找到，則返回結點地址及指向其雙親的指針；否則，返回 NULL
template <class T>
TreeNode<T> *BinSTree<T>::FindNode(const T& item, TreeNode<T>* & parent) const
{   
    // 用指針 t 從根開始遍歷樹
    TreeNode<T> *t = root;
    
    // 根的雙親為 NULL
    parent = NULL;
    
    // 若子樹為空，則循環結束
    while(t != NULL)
    {
        // 若找到鍵值，則退出
        if (item == t->data)
            break;
        else 
        {
            // 修改雙親指針，并移到左子樹或右子樹
            parent = t;
            if (item < t->data)
                t = t->left;
            else 
                t = t->right;
        }
    }
    
    // 返回指向結點的指針；若沒找到，則返回 NULL
    return t;
}

// 構造函數，初始化 root，current 為空，size 為 0
template <class T>
BinSTree<T>::BinSTree(void):root(NULL), current(NULL), size(0)
{}

// 復制構造函數
template <class T>
BinSTree<T>::BinSTree(const BinSTree<T>& tree)
{
    // 將 tree 復制到當前對象，分配 current 和 size
    root = CopyTree(tree.root);
    current = root;
    size = tree.size;
}

// 析構函數
template <class T>
BinSTree<T>::~BinSTree(void)
{
    ClearList();
}

// 刪除樹中的所有結點
template <class T>
void BinSTree<T>::ClearList(void)
{
    DeleteTree(root);
    root = current = NULL;
    size = 0;
}

// 賦值運算符
template <class T>
BinSTree<T>& BinSTree<T>::operator= (const BinSTree<T>& rhs)
{
    // 不能將樹復制到自身
    if (this == &rhs)
        return *this;
        
    // 清除當前樹，將新樹復制到當前對象
    ClearList();
    root = CopyTree(rhs.root);
    
    // 將 current 指針指向 root 并設置樹的 size 值
    current = root;
    size = rhs.size;
    
    // 返回當前對象的指針
    return *this;
}

// 在樹中搜索 item，若找到，則將結點數據賦給 item
template <class T>
bool BinSTree<T>::Find(T& item)
{
    // 使用 FindNode，它需要 parent 參數
    TreeNode<T> *parent;

    // 在樹中搜索 item，將匹配的結點賦給 current
    current = FindNode(item, parent);
    
    // 若找到，則將數據賦給 item 并返回 True
    if (current != NULL)
    {
        item = current->data;
        return true;
    }
    else
    	// 在樹中沒找到 item，返回 False
        return false;
}

// 指示樹是否為空
template <class T>
bool BinSTree<T>::ListEmpty(void) const
{
    return (size == 0);
}

// 返回樹中的數據項個數
template <class T>
int BinSTree<T>::ListSize(void) const
{
    return size;
}

// 往查找樹中插入數據項，若元素重復，則更新現有元素
template <class T>
void BinSTree<T>::Insert(const T& item)
{
    // t 為遍歷過程中的當前結點，parent 為前一結點
    TreeNode<T> *parent = NULL;

	current = FindNode(item, parent);
    
	if (current != NULL)
		current->data = item;
	else
	{
		// 創建新的葉子結點
		TreeNode<T> *newNode = new TreeNode<T>(item,NULL,NULL);
		
		// 若 parent 為 NULL，則將其作為根結點插入
		if (parent == NULL)
			root = newNode;
        
		// 若 item < parent->data，則將其作為左孩子插入        
		else if (item < parent->data)                   
			parent->left = newNode;
        
		else
			// 若 item >= parent->data，作為右孩子插入     
			parent->right = newNode;
        
		// current 賦值為新結點的地址并將 size 加 1
		current = newNode;
		size++;
	}
}

// 如果 item 在樹中，將其刪除
template <class T>
void BinSTree<T>::Delete(const T& item)
{
    // DNodePtr = 指向被刪除結點 D 的指針
    // PNodePtr = 指定結點 D 的雙親節點 P 的指針
    // RNodePtr = 指向替換 D 的結點 R 的指針
    TreeNode<T> *DNodePtr, *PNodePtr, *RNodePtr;
    
    // 搜索數據值為 item 的結點，并保存該結點的雙親結點的指針
    if ((DNodePtr = FindNode (item, PNodePtr)) == NULL)
        return;
    
    // 如果 D 有一個指針為 NULL，則替換結點為其另一枝的某一結點
    if (DNodePtr->right == NULL)
        RNodePtr = DNodePtr->left;
    else if (DNodePtr->left == NULL)
        RNodePtr = DNodePtr->right;
        
    // DNodePtr 的兩個指針均不為 NULL
    else
    {
        // 尋找并卸下 D 的替換結點。從結點 D 的左子樹開始，找數據值小于 D 的數據值的
        // 最大值，將該結點從樹中斷開
        
        // PofRNodePtr = 指向替換結點雙親的指針
        TreeNode<T> *PofRNodePtr = DNodePtr;
        
        // 第一種可能的替換為 D 的左孩子
        RNodePtr = DNodePtr->left;
    
        // 從 D 的左孩子的右子樹繼續往下搜索最大值，并記錄當前結點及其雙親結點的
        // 指針，最后，我們將找到替換結點
        while(RNodePtr->right != NULL)
        {
            PofRNodePtr = RNodePtr;
            RNodePtr = RNodePtr->right;
        }
        
        if (PofRNodePtr == DNodePtr)
            // 被刪除結點的左孩子為替換結點，將 D 的右子樹賦給 R
            RNodePtr->right = DNodePtr->right;
        else
        {
            // 至少往右子樹移動了一個結點，從樹中刪除替換結點，將其左子樹賦給其雙親
            PofRNodePtr->right = RNodePtr->left;
            
            // 用替換結點代替 DNodePtr
            RNodePtr->left = DNodePtr->left;
            RNodePtr->right = DNodePtr->right;
        }
    }

    // 完成到雙親結點的連接。刪除根結點，并給新更賦值
    if (PNodePtr == NULL)
        root = RNodePtr;
        
    // 將 R 連到 P 的正確一枝上
    else if (DNodePtr->data < PNodePtr->data)
        PNodePtr->left = RNodePtr;
    else
        PNodePtr->right = RNodePtr;
        
    // 釋放被刪結點內存并將樹的大小減 1
    delete DNodePtr;
    size--;
}

// 若當前結點已定義且數據值與給定數據值相等，則將結點值賦給 item；否則，將 item 插入到樹中
template <class T>
void BinSTree<T>::Update(const T& item)
{   
    if (current != NULL && current->data == item)
            current->data = item;
    else
        Insert(item);
}

// 返回根結點的地址
template <class T>
TreeNode<T> *BinSTree<T>::GetRoot(void) const
{
    return root;
}

#endif  // BINARY_SEARCH_TREE_CLASS