c++ 搜索二叉樹(shù)/排序二叉樹(shù)

#pragma once

#include <iostream>

using namespace std;

template<class K, class V>

struct BsTreeNode{//二叉樹(shù) 節(jié)點(diǎn)
	K _key;
	V _value;
	BsTreeNode* _left;
	BsTreeNode* _right;
	
	BsTreeNode(const K& key,const V& value)
		:_key(key)
		, _value(value)
		, _left(NULL)
		, _right(NULL)
	{}
};


template<class K, class V>
class BsTree{

public:
typedef BsTreeNode<K, V> Node;
	BsTree()
		: _root(NULL)
	{
	}

	~BsTree(){}

	bool Insert(const K& key, const V& value)//插入 非遞歸
	{
		if (_root == NULL){
			_root = new Node(key, value);
			return true;
		}
		Node* cur = _root;
		while (1){
			if (cur->_key > key)
			{
				if (cur->_left)
					cur = cur->_left;
				else{
					cur->_left = new Node(key, value);
					return true;
				}
			}
			else if (cur->_key < key)
			{
				if (cur->_right)
					cur = cur->_right;
				else{
					cur->_right = new Node(key, value);
					return true;
				}
			}//以上為找 插入位置 并插入
			else if (cur->_key == key)//存在  插入失敗
				return false;
		}


	}

	bool InsertR(const K& key,const V& value)//插入 遞歸
	{
		return _InsertR(_root,key,value);
	}

	Node* Find(const K& key){//查找
		Node * cur = _root;
		while (cur){
			if (cur->_key > key)
				cur = cur->_left;
			else if (cur->_key < key)
				cur = cur->_right;
			else
				return cur;
		
		}
		return NULL;
	}

	bool RemoveR(const K& key)//刪除 遞歸
	{
		if (_root == NULL)
			return false;
		return _RemoveR(_root,key);
	}

	bool Remove(K key){//刪除 非遞歸
		Node* cur=_root, *prev=NULL;
		while (cur){
			if (cur->_key > key)
			{
				prev = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				prev = cur;
				cur = cur->_right;
			}// 以上為 找到要?jiǎng)h除的 節(jié)點(diǎn)
			else
			{
				if (cur->_left == NULL)//如果節(jié)點(diǎn)左或右為空，直接刪除該節(jié)//點(diǎn)將之后的節(jié)點(diǎn) 連接在其父節(jié)點(diǎn)
				{
					if (prev == NULL)
					{
						_root = cur->_right;
					
					}
					else if (prev->_left == cur)
					{
						prev->_left = cur->_right;

					}
					else
						prev->_right = cur->_right;
				}

				else if (cur->_right == NULL)//同上 右為空
				{
					if (prev == NULL)
					{
						_root = cur->_left;
						delete cur;
					}
					else if (prev->_right == cur)
					{
						prev->_right = cur->_left;

					}
					else
						prev->_left = cur->_left;
				}
				else//如果左右都不為空 找右孩子最左 或 左孩子最右 節(jié)點(diǎn)替
				//代刪除
				{

					prev = cur;
					cur = cur->_right;
					while (cur->_left){
						cur = cur->_left;
						
					}
					prev->_key = cur->_key;
					prev->_value = cur->_value;
					prev->_right =cur->_right;
					
				}

				delete cur;
				return true;
			}
		}
		return false;
	}
	bool modification(K key,V value){//修改
		
		Node* ret = Find(key);
		if (ret == NULL)
			return false;
		ret->_value = value;
		return true;

	}

private:
	bool _InsertR(Node* & root,const K& key,const V& value)//插入 遞歸函數(shù)
	{
		if (root == NULL)
		{
			root = new Node(key,value);
			return true;
		}

		if (root->_key == key)
			return false;
		else if (root->_key > key)
			return _InsertR(root->_left,key,value);
		else 
			return _InsertR(root->_right,key,value);
			
	}

	bool _RemoveR(Node* & root,const K& key)//刪除 遞歸函數(shù)
	{
		if (root->_key < key)
			return _RemoveR(root->_right, key);
		if (root->_key>key)
			return _RemoveR(root->_left, key);
		if (root->_left == NULL)
		{
			Node* dev = root;
			root = root->_right;
			delete dev;
			return true;
		}
		else if (root->_right == NULL)
		{
			Node* dev = root;
			root = root->_left;
			delete dev;
			return true;
		}
		else
		{
			root->_key = root->_right->_key;
			root->_value = root->_right->_value;
			return _RemoveR(root->_right,root->_key);
		}
	}

	Node* _root;
};