#include "BSTree.h"
#include<iostream>

using namespace std;


//前序遍历二叉树
template<class T>
void BSTree<T>::preOrder(BSTNode<T> *tree) const
{
 if(tree!=nullptr)
 {
 cout<<tree->key<<" ";
 preOrder(tree->left);
 preOrder(tree->right);
 }
}

template<class T>
void BSTree<T>::preOrder()
{
 preOrder(mRoot);
}
//中序遍历二叉树
template<class T>
void BSTree<T>::inOrder(BSTNode<T> *tree) const
{
 if(tree!=nullptr)
 {
 inOrder(tree->left);
 cout<<tree->key<<" ";
 inOrder(tree->right);
 }
}
template<class T>
void BSTree<T>::inOrder()
{
 inOrder(mRoot);
}
//后序遍历二叉树
template<class T>
void BSTree<T>::postOrder(BSTNode<T> *tree) const
{
 if(tree!=nullptr)
 {
 postOrder(tree->left);
 postOrder(tree->right);
 cout<<tree->key<<" ";
 }
}
template<class T>
void BSTree<T>::postOrder()
{
 postOrder(mRoot);
}
//递归实现查找二叉树中键值为key的节点
template<class T>
BSTNode<T>* BSTree<T>::search(BSTNode<T> *x, T key)const
{
 if(x->key==key)
 return x;
 else if(x->key>key)
 return search(x->left,key);
 else
 return search(x->right,key);
}

template<class T>
BSTNode<T>* BSTree<T>::search(T key)
{
 return search(mRoot,key);
}

//非递归实现查找二叉树中键值为key的节点
template<class T>
BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T> *x, T key)const
{
 while(x!=nullptr)
 {
 if(x->key==key)
 return x;
 else if(x->key>key)
 x=x->left;
 else
 x=x->right;
 }
 return x;
}
template<class T>
BSTNode<T>* BSTree<T>::iterativeSearch(T key)
{
 return iterativeSearch(mRoot,key);
}

//查找最小节点，返回最小节点
template<class T>
BSTNode<T>* BSTree<T>::minimum(BSTNode<T> *tree)
{
 while(tree->left!=nullptr)
 {
 tree=tree->left;
 }
 return tree;
}

template<class T>
T BSTree<T>::minimum()
{
 return minimum(mRoot)->key;
}

//查找最大节点，返回最大节点
template<class T>
BSTNode<T>* BSTree<T>::maximum(BSTNode<T> *tree)
{
 while(tree->right!=nullptr)
 {
 tree=tree->right;
 }
 return tree;
}

template<class T>
T BSTree<T>::maximum()
{
 return maximum(mRoot)->key;
}

//插入节点到二叉搜索树
template<class T>
void BSTree<T>::insert(BSTNode<T> *&tree, BSTNode<T> *z)
{
 if(tree==nullptr)
 {
 tree=z;
 return;
 }
 BSTNode<T>* p=nullptr;
 BSTNode<T>* tmp=tree;
 while(tmp)
 {
 if(tmp->key==z->key)
 return;
 p=tmp;
 if(tmp->key>z->key)
 {
 tmp=tmp->left;
 }
 else
 {
 tmp=tmp->right;
 }
 }
 if(p->key>z->key)
 p->left=z;
 else
 p->right=z;
}

template<class T>
void BSTree<T>::insert(T key)
{
 BSTNode<T>* node=new BSTNode<T>(key);
 insert(mRoot,node);
}

//删除节点
template<class T>
BSTNode<T>* BSTree<T>::remove(BSTNode<T> *&tree, BSTNode<T> *z)
{
 if(tree==nullptr) return;
 BSTNode<T>* pcur=tree;
 while(pcur!=nullptr && pcur->key!=z->key)
 {
 if(pcur->key>z->key)
 pcur=pcur->left;
 else
 pcur=pcur->right;
 }
 if(pcur==nullptr)
 return;
 if(!pcur->left && !pcur->right)
 {
 delete pcur;
 pcur=nullptr;
 return;
 }
 if(pcur->left && pcur->right)
 {
 BSTNode<T>* tmp=pcur->right;
 while(tmp->left)
 tmp=tmp->left;
 if(pcur->right=tmp)
 {
 pcur->right=tmp->right;
 delete tmp;
 tmp=nullptr;
 return;
 }
 BSTNode<T>* node=pcur;
 pcur=tmp;
 tmp=node;
 delete tmp;
 tmp=nullptr;
 return;
 }
 if(pcur->left)
 {
 BSTNode<T>* p=pcur->parent;
 if(p==nullptr)
 {
 tree=pcur->left;
 delete pcur;
 pcur=nullptr;
 return;
 }
 if(p->right==pcur)
 {
 p->right=pcur->left;
 }
 if(p->left==pcur)
 {
 p->left=pcur->left;
 }
 return;
 }
 if(pcur->right)
 {
 BSTNode<T>* p=pcur->parent;
 if(p==nullptr)
 {
 tree=pcur->right;
 delete pcur;
 pcur=nullptr;
 return;
 }
 if(p->right==pcur)
 {
 p->right=pcur->right;
 }
 if(p->left==pcur)
 {
 p->left=pcur->right;
 }
 return;
 }
}
template<class T>
void BSTree<T>::remove(T key)
{
 BSTNode<T>* node=new BSTNode<T>(key);
 remove(mRoot,node);
}

//销毁二叉树
template<class T>
void BSTree<T>::destory(BSTNode<T> *&tree)
{
 if(tree)
 {
 BSTNode<T>* l=tree->left;
 BSTNode<T>* r=tree->right;
 delete tree;
 destory(l);
 destory(r);
 }
}
template<class T>
void BSTree<T>::destory()
{
 destory(mRoot);
}

//查找节点x的后继节点
template<class T>
BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x)
{
 if(x==nullptr || x->right==nullptr) return nullptr;
 BSTNode<T>* node=x->right;
 while(node->left)
 node=node->left;
 return node;
}

//查找节点x的前驱节点
template<class T>
BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x)
{
 if(x==nullptr) return nullptr;
 if(x->left)
 {
 x=x->left;
 while(x->right)
 x=x->right;
 return x;
 }
 BSTNode<T>* p=x->parent;
 if(p==nullptr) return p;
 if(p->right==x) return p;
 if(p->left==x)
 {
 BSTNode<T>* q=p->parent;
 while(q->right!=p)
 {
 p=q;
 q=p->parent;
 }
 return q;
 }

}