愚人节

ゝ一世哀愁。 2022-06-18 08:40 122阅读 0赞

二叉搜索树：

*  1.每个节点都有一个作为搜索依据的关键码（key)，所有节点关键码（key）；
 *  2.左子树上所有节点的1关键码（key）都小于根节点的关键码（key）；
 *  3.右子树所有节点的关键码（key）都大于根节点的关键码（key）；
 *  4.左右子树都是二叉搜索树。

实现：

*  二叉搜索树（节点插入、删除和查找）

#include<iostream>
    using namespace std;
    
    template<class K, class V>
    struct BSTNode
    {
    	K _key;
    	V _value;
    	BSTNode* _left;
    	BSTNode* _right;
    
    	BSTNode(const K& key, const V& value)
    		:_key(key)
    		, _value(value)
    		, _left(NULL)
    		, _right(NULL)
    	{}
    };
    
    template<class K, class V>
    class BSTree
    {
    	typedef BSTNode<K, V> Node;
    public:
    
    	BSTree()
    		:_root(NULL)
    	{}
    
    	//插入(非递归)
    	bool Insert(const K& key, const V& value)
    	{
    		if (_root == NULL)
    		{
    			_root = new Node(key, value);
    			return true;
    		}
    
    		Node* parent = NULL;
    		Node* cur = _root;
    		while (cur)
    		{
    			if (key > cur->_key)
    			{
    				parent = cur;
    				cur = cur->_right;
    			}
    			else if (key < cur->_key)
    			{
    				parent = cur;
    				cur = cur->_left;
    			}
    			else
    			{
    				return false;
    			}
    		}
    
    		cur = new Node(key, value);
    		if (parent->_key > key)
    		{
    			parent->_left = cur;
    		}
    		else
    		{
    			parent->_right = cur;
    		}
    		return true;
    	}
    
    	//插入（递归）
    	bool Insert_R(const K& key, const V& value)
    	{
    		return _Insert_R(_root, key, value);
    	}
    
    	//查找
    	Node* Find(const K& key)
    	{
    		if (_root == NULL)
    		{
    			return NULL;
    		}
    		Node* cur = _root;
    		while (cur)
    		{
    			if (key < cur->_key)
    			{
    				cur = cur->_left;
    			}
    			else if (key > cur->_key)
    			{
    				cur = cur->_right;
    			}
    			else
    			{
    				break;
    			}
    		}
    		return cur;
    	}
    
    	//删除（非递归）
    	bool Remove(const K& key)
    	{
    		if (_root == NULL)
    		{
    			return false;
    		}
    		if (_root->_left == NULL && _root->_right == NULL)
    		{
    			delete _root;
    			_root = NULL;
    			return true;
    		}
    
    		Node *parent = _root;
    		Node *del = _root;
    		while (del)
    		{
    			if (key < del->_key)
    			{
    				parent = del;
    				del = del->_left;
    			}
    			else if (key > del->_key)
    			{
    				parent = del;
    				del = del->_right;
    			}
    			else
    			{
    				break;
    			}
    		}
    		if (del == NULL)
    		{
    			return false;
    		}
    
    		if (del->_left == NULL)
    		{
    			if (del == _root)
    			{
    				_root = del->_right;
    			}
    			else
    			{
    				if (parent->_left == del)
    				{
    					parent->_left = del->_right;
    				}
    				else
    				{
    					parent->_right = del->_right;
    				}
    			}
    		}
    		else if (del->_right == NULL)
    		{
    			if (del == _root)
    			{
    				_root = del->_left;
    			}
    			else
    			{
    				if (parent->_left == del)
    				{
    					parent->_left = del->_left;
    				}
    				else
    				{
    					parent->_right = del->_left;
    				}
    			}
    		}
    		else
    		{
    			Node* sub = del;
    			Node* First = del->_right;
    			while (First->_left)
    			{
    				sub = First;
    				First = First->_left;
    			}
    			swap(del->_key, First->_key);
    			swap(del->_value, First->_value);
    			del = First;
    			if (del->_left == NULL)
    			{
    				if (sub->_left == del)
    				{
    					sub->_left = del->_right;
    				}
    				else
    				{
    					sub->_right = del->_right;
    				}
    			}
    			else if (del->_right == NULL)
    			{
    				if (sub->_left == del)
    				{
    					sub->_left = del->_left;
    				}
    				else
    				{
    					sub->_left = del->_left;
    				}
    			}
    		}
    		delete del;
    		del = NULL;
    		return true;
    	}
    
    	//删除（递归）
    	bool Remove_R(const K& key)
    	{
    		return _Remove_R(_root, key);
    	}
    
    	//遍历（中序）
    	void InOrder()
    	{
    		_InOrder(_root);
    		cout << endl;
    	}
    
    protected:
    
    	bool _Insert_R(Node*& root, const K& key, const V& value)
    	{
    		if (root == NULL)
    		{
    			root = new Node(key, value);
    			return true;
    		}
    		if (key < root->_key)
    		{
    			return _Insert_R(root->_left, key, value);
    		}
    		else if (key > root->_key)
    		{
    			return _Insert_R(root->_right, key, value);
    		}
    		else
    		{
    			return false;
    		}
    	}
    
    	bool _Remove_R(Node*& root, const K& key)
    	{
    		if (root == NULL)
    		{
    			return false;
    		}
    		if (key < root->_key)
    		{
    			return _Remove_R(root->_left, key);
    		}
    		else if (key > root->_key)
    		{
    			return _Remove_R(root->_right, key);
    		}
    		else
    		{
    			Node* del = root;
    			if (root->_left == NULL)
    			{
    				root = root->_right;
    			}
    			else if (root->_right == NULL)
    			{
    				root = root->_left;
    			}
    			else
    			{
    				Node* First = root->_right;
    				while (First->_left)
    				{
    					First = First->_left;
    				}
    				swap(del->_key, First->_key);
    				swap(del->_value, First->_value);
    				return _Remove_R(root->_right, key);
    			}
    			delete del;
    			del = NULL;
    			return true;
    		}
    	
    	}
    
    	void _InOrder(Node* root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		_InOrder(root->_left);
    		cout << root->_key << " ";
    		_InOrder(root->_right);
    	}
    
    private:
    	BSTNode<K, V>* _root;
    };