/*BiTree.h*/
#include<bits/stdc++.h>
using namespace std;
struct Node
{
	int data;
	Node* lChild;
	Node* rChild;
};
class BiSortTree
{
private:
	Node* root;
public:
	BiSortTree(int* source, int length);
	void InsertBiSortTree(Node* &rt, int target);
	Node* SearchBiSortTree(Node* rt, int target);
	Node* GetRoot();
	void MidOrder(Node* rt);
	void DeleteBST(Node* &rt,int target);
	void DeleteNode(Node*& rt, int target);
};
BiSortTree::BiSortTree(int* source, int length)
{
	root = NULL;
	for (int i = 0; i < length; i++)
		InsertBiSortTree(root, source[i]);
}
void BiSortTree::InsertBiSortTree(Node* &rt, int target)
{
	if (rt == NULL)
	{
		rt = new Node;
		rt->data = target;
		rt->lChild = NULL;
		rt->rChild = NULL;
		return;
	}
	else if (target < rt->data)
		InsertBiSortTree(rt->lChild, target);
	else
		InsertBiSortTree(rt->rChild, target);
	return;
}
Node* BiSortTree::SearchBiSortTree(Node* rt, int target)
{
	if (rt == NULL)
	{
		cout << "查找失败" << endl;
		return NULL;
	}
	else if (rt->data == target)
		return rt;
	else if (rt->data > target)
		SearchBiSortTree(rt->lChild, target);
	else 
		SearchBiSortTree(rt->rChild, target);
}
Node* BiSortTree::GetRoot() {return root;}
void BiSortTree::MidOrder(Node* rt)
{
	if (rt != NULL)
	{
		MidOrder(rt->lChild);
		cout << rt->data << ' ';
		MidOrder(rt->rChild);
	}
}
void BiSortTree::DeleteBST(Node*& rt, int target)//查找要删除的结点，与SearchBiSortTree函数类似
{
	if (rt == NULL)
	{
		cout << "没有找到要删除的值为"<<target<<"的结点" << endl;
		return;
	}
	else if (rt->data == target)
	{
		DeleteNode(rt, target);
		return;
	}
	else if (rt->data > target)
		DeleteBST(rt->lChild, target);
	else
		DeleteBST(rt->rChild, target);
}
void BiSortTree::DeleteNode(Node*& rt, int target)
{
	if (rt->lChild == NULL && rt->rChild == NULL)//要删除的结点为叶子结点
	{
		Node* p = rt;
		rt = NULL;
		delete p;
		return;
	}
	else if (rt->lChild == NULL)//要删除的结点没有左孩子
	{
		Node* p = rt;
		rt = rt->rChild;
		delete p;
		return;
	}
	else if (rt->rChild == NULL)//要删除的结点没有右孩子
	{
		Node* p = rt;
		rt = rt->lChild;
		delete p;
		return;
	}
	else//要删除的结点既有左孩子又有右孩子，将要删除的结点替换为左子树中的最大值，或者右子树中的最小值，同时删除被替换用的数
	{   //以将要删除的结点替换为左子树中的最大值为例
		Node* parent = rt;
		Node* pre = rt->lChild;
		while (pre->rChild != NULL)
		{
			parent = pre;
			pre = pre->rChild;
		}
		rt->data = pre->data;
		if (parent != rt)//非常重要，要删除结点的右孩子有没有右孩子作为两种情况
		{
			parent->rChild = pre->lChild;
			delete pre;
		}
		else
		{
			parent->lChild = pre->lChild;
			delete pre;
		}
		return;
	}
}

#include<bits/stdc++.h>
#include "BiTree.h"
using namespace std;
int main(void)
{
	int data[] = { 9,5,1,3,7,8,2,6,4 };
	BiSortTree tree(data, sizeof(data) / sizeof(data[0]));
	Node* rt = tree.GetRoot();
	/*cout << "查找数字7的地址是" << tree.SearchBiSortTree(rt, 10)<<endl;*/
	//cout << tree.SearchBiSortTree(rt, 7)->data;
	tree.MidOrder(rt);
	tree.DeleteBST(rt, 6);
	cout << endl;
	tree.MidOrder(rt);
	return 0;
}