#pragma once
#include"BirTree.h"
class BiSortTree :public BirTree
{
public:
	BiSortTree(int legnth);
	BiNode* searchBST(int key) { return searchBST(root, key); }
	bool deleteBST(int key) { return deleteBST(root, key); }
	void insertBST(int key) { insertBST(root, key); }
private:
	void insertBST(BiNode*& bt, ElemType key);		//插入节点
	bool deleteBST(BiNode*& bt, ElemType key);		//删除结点
	void deleteNode(BiNode*& bt);	//删除结点详细步骤
	BiNode* searchBST(BiNode* bt, ElemType key);	//查找结点
private:	//下面四个函数都是使用deleteNode左右孩子不为空的情况删除结点的几种方法
	//让左孩子的最右结点(最大)结点代替自己
	void deleteNodeleft1(BiNode*& bt);		//左孩子成为左子树最大结点最左结点的左孩子
	void deleteNodeleft2(BiNode*& bt);		//让左孩子的右节点由最大结点的第一个左孩子来替代
	//让右孩子的最左结点(最小)代替自己		
	void deleteNoderight1(BiNode*& bt);		//右孩子成为右子树最小结点最右结点的右孩子
	void deleteNoderight2(BiNode*& bt);		//让右孩子的左节点由最小结点的第一个右孩子来替代
};