搜索二叉树

搜索二叉树的创建

  #include
using namespace std;
template
struct Treenode {
	struct Treenode* lchild, * rchild;
	K val;
	Treenode(const K&key):lchild(nullptr),rchild(nullptr),val(key){}
};

template
class Tree {
public:
	typedef struct Treenode node;
	bool insert(K key) {//插入
		if (root == NULL) {
			root = new node(key);
			return true;

		}
		node* parent = nullptr;
		node* cur = root;
		while (cur) {
			if (cur->val > key) {
				parent = cur;
				cur = cur->lchild;
			}
			else if (cur->val < key) {
				parent = cur;
				cur = cur->rchild;
			}
			else {
				return false;
			}
		}
		cur = new node(key);
		if (parent->val > key)
			parent->lchild = cur;
		if (parent->val < key) {
			parent->rchild = cur;
		}
		return true;


	}
	//查找
	bool find(K key) {
		node* p = root;
		while (p) {
			if (p->val > key) {
				p = p->lchild;
			}
			if (p->val < key) {
				p = p->rchild;
			}
			else {
				return true;
			}
			
		}
		return true;
	}
	//中序遍历，由于无法自身传入参数，
	void _inorder(node*root) {
		if (root==nullptr)
			return;
		_inorder(root->lchild);
		cout << root->val<<" ";
		_inorder(root->rchild);

	}
	void inorder() {
		_inorder(root);
	}
	//删除参数
	bool erase(const K &key) {
		node* parent = nullptr;
		node* cur = root;
		while (cur) {
			if (cur->val > key) {
				parent = cur;
				cur = cur->lchild;
			}
			else if (cur->val < key) {
				parent = cur;
				cur = cur->rchild;
			}
			else {
				//找到了
				//1、作为空
				//2、右为空
				// 3、左右都为空
				if (cur->lchild == NULL) {
					if (parent->rchild = cur) {
						parent->rchild = cur->rchild;
					}
					else {
						parent->lchild = cur->rchild;
					}
					delete cur;
				}
				else if (cur->rchild == nullptr) {
					if (parent->lchild = cur) {
						parent->lchild = cur->lchild;
					}
					else {
						parent->rchild = cur->lchild;
					}
					delete cur;
				}
				else {
					node* max1 = cur;
					node* minrchild = cur->rchild;
					while (minrchild->lchild) {
						max1 = minrchild;
						minrchild = minrchild->lchild;
					}
					cur->val = minrchild->val;
					if(max1->lchild==minrchild)
					max1->lchild = minrchild->rchild;
					else
						max1->rchild = minrchild->rchild;

					delete minrchild;
				}
				return true;
				
			}
		}
	}
private:
	node* root=NULL;
};
int main() {
	Treetree;
	int a[] = { 5,3,4,1,7,8,2,6,0,9 };
	for (auto e : a) {
		tree.insert(e);
	}
	tree.erase(1);
	tree.inorder();
	cout << endl;

	cout<