【二叉树】二叉搜索树

二叉搜索树:

创新互联是一家专业提供兴海企业网站建设,专注与网站设计制作、做网站、html5、小程序制作等业务。10年已为兴海众多企业、政府机构等服务。创新互联专业的建站公司优惠进行中。

1.每个节点都有一个关键码(key)作为搜索依据,关键码互不相同。

2.左子树的所有关键码都小于根节点的关键码。

3.右子树的所有关键码都大于根节点的关键码。

4.左右子树都是二叉搜索树。

删除key:左为空,右为空,左右都不空

1)左为空:cur的右树链到父节点

2)右为空:cur的左树链到父节点

3)左右都不空:找右树最左节点或左树最右节点,将找到的节点与cur交换后删除它。

二叉搜索树的增、删、查(非递归及递归)程序代码如下:

#pragma once

#include<string>
////注意:考虑边界问题_root 、左右子树问题(非递归、递归)、记住判空处理
template<class K,class V>
struct BSTNode
{
	BSTNode<K, V>* _left;   //左子数
	BSTNode<K, V>* _right;  //右子树
	K _key;
	V _value;
	//构造函数
	BSTNode(const K& key, const V& value)
		:_left(NULL)
		, _right(NULL)
		, _key(key)
		, _value(value)
	{}
};

template<class K, class V>
class BSTree
{
	typedef BSTNode<K, V> Node;
public:
	BSTree()
		:_root(NULL)
	{}

public:
	//bool Insert(const K& key, const V& value);
	//bool Remove(const K& key);
	//Node* Find(const K& key);
	//bool Insert_R(const K& key, const V& value);
	//bool Remove_R(const K& key, const V& value);
	//Node* Find_R(const K& key);

	bool Insert(const K& key, const V& value)
	{
		if(_root == NULL)
			_root = new Node(key, value);
		Node* cur = _root;
		while(cur)
		{
			if(key < cur->_key)   //key小,插入左子树
			{
				if(cur->_left == NULL)
					cur->_left = new Node(key, value);
				else
					cur = cur->_left;
			}
			else if(key > cur->_key)   //key大,插入右子树
			{
				if(cur->_right == NULL)
					cur->_right = new Node(key, value);
				else
					cur = cur->_right;
			}
			else                       //key关键码互不相同
				return false;
		}
		return true;
	}
	////////////////删除//////////////
	////边界条件判断(无节点,一个节点)
	////找key值,记录parent。
	////删除key,分三种情况(左为空,右为空,左右都不为空)
	////左右节点都存在,找到右树的最左节点或者左树的最右节点,
	////将找到的节点与cur交换后再删除找到的节点

	bool Remove(const K& key) 
	{
		//无节点
		if(_root == NULL)
			return false;
		//一个节点 _root
		if(_root->_left == NULL&&_root->_right == NULL)
		{
			if(key == _root->_key)
			{
				delete _root;
				_root = NULL;
				return true;
			}
			else
				return false;
		}

		Node* cur = _root;
		Node* parent = NULL;
		while(cur)
		{   //找key值,记录parent
			if(key < cur->_key)  
			{
				parent = cur;
				cur = cur->_left;
			}
			else if(key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			////删除key,分三种情况(左为空,右为空,左右都不为空)
			else  
			{
				Node*del=cur;
				if(cur->_left == NULL)   //将cur的右子树链到父节点
				{
					//注意parent可能为空
					if(parent == NULL)  
					{
						_root = cur->_right;
					}
					else
					{
						if(cur = parent->_left)
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
					}
		
				}
				else if(cur->_right == NULL)  //将cur的左子树链到父节点
				{
					if(parent == NULL)
					{
						_root = cur->_left;
					}
					else
					{
						if(cur = parent->_left)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}
					
				}
				////左右节点都存在,找到右树的最左节点或者左树的最右节点
				////将找到的节点与cur交换后再删除找到的节点
				else
				{
					parent = cur;
					//右树的最左节点firstLeft
					Node* firstLeft = cur->_right;
					while(firstLeft->_left)
					{
						parent = firstLeft;
						firstLeft = firstLeft->_left;
					}
					
					swap(firstLeft->_key, cur->_key);
					swap(firstLeft->_value, cur->_value);
					del = firstLeft;

					//因为左右节点都存在,所以parent不为空
					//firstLeft 左节点为空,右节点可能存在
					if(firstLeft == parent->_left)
						parent->_left = firstLeft->_right;
					else
						parent->_right = firstLeft->_right;

				} /*找到firstLeft代替del*/
				
				delete del;
				return true;
			}
		}//while end
		
		return false;
	}

//查找
	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
			{
				return cur;
			}
		}
		return NULL;
	}

	/////////////////////递归实现增删查
	bool Insert_R(const K& key, const V& value)
	{
		return _Insert_R(_root, key, value);
	}
	bool Remove_R(const K& key)
	{
		return _Remove_R(_root, key);
	}
	Node* Find_R(const K& key)
	{
		return _Find_R(_root, key);
	}

	//中序遍历
	void InOrder()
	{
		return _InOrder(_root);
	}

	bool Empty()
	{
		if(_root == NULL)
		{
			return true;
		}
		return false;
	}
protected:
	void _InOrder(Node* root)
	{
		if(root == NULL)
			return;
		_InOrder(root->_left);
		//cout << root->_key << " " << endl;
		cout << "key:" << root->_key << " ,value:" << root->_value<< endl;
		_InOrder(root->_right);
	}
	////注意:root参数应为引用&  每次递归的root即为上一次的root->_left或者root->_right
	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;
		}
	}
//查找
	Node* _Find_R(Node*& root, const K& key)
	{
		if(root == NULL)
			return NULL;

		if(key < root->_key)
		{
			return _Find_R(root->_left, key);
		}
		else if(key>root->_key)
		{
			return _Find_R(root->_right, key);

		}
		else
		{
			return root;
		}
	}
//删除
	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);
		}
		///删除key
		////以引用root作参数,root相当于上一层的root->_left或者root->_right
		else   
		{
			Node*del = root;
			if(root->_left == NULL)
			{
				root = root->_right;
				delete del;
				return true;
			}
			else if(root->_right == NULL)
			{
				root = root->_left;
				delete del;
				return true;
			}
			///左右节点都不为空
			else
			{
				//右子树的最左节点
				Node* firstLeft = root->_right;
				while(firstLeft->_left)
				{
					firstLeft = firstLeft->_left;
				}

				swap(firstLeft->_key, root->_key);
				swap(firstLeft->_value, root->_value);

				//_Remove_R(firstLeft, key);//错误,firstLeft是临时变量不能作为递归的参数
				_Remove_R(root->_right, key);
			}

		}///删除key end
		return false;
	}

protected:
	Node* _root;
};	

测试代码:

void TestBSTree()
{
	BSTree<int, int> bst;
	bst.Insert(5, 1);
	bst.Insert(3, 1);
	bst.Insert(4, 1);
	bst.Insert(1, 1);
	bst.Insert(7, 1);
	bst.Insert(8, 1);
	bst.Insert(2, 1);
	bst.Insert(6, 1);
	bst.Insert(0, 1);
	bst.Insert(9, 1);

	bst.InOrder();

	cout << "? " << bst.Find(1)->_key<< endl;
	cout << "? " << bst.Find(8)->_key<< endl;
	cout << "? " << bst.Find(22)<< endl;


	bst.Remove(1);
	bst.Remove(2);
	bst.Remove(3);
	bst.Remove(4);
	bst.Remove(5);
	bst.Remove(6);
	bst.Remove(7);
	bst.Remove(8);
	bst.Remove(9);
	bst.Remove(0);

	if(bst.Empty())
		cout << "此二叉搜索树为空" << endl;
	bst.InOrder();
}

void TestBSTree_R()  //递归
{
	BSTree<int, int> bst;

	bst.Insert_R(5, 1);
	bst.Insert_R(3, 1);
	bst.Insert_R(4, 1);
	bst.Insert_R(1, 1);
	bst.Insert_R(7, 1);
	bst.Insert_R(8, 1);
	bst.Insert_R(2, 1);
	bst.Insert_R(6, 1);
	bst.Insert_R(0, 1);
	bst.Insert_R(9, 1);

	bst.InOrder();

	cout << "? " << bst.Find(1)->_key << endl;
	cout << "? " << bst.Find(8)->_key << endl;
	cout << "? " << bst.Find(22) << endl;

	/*
	bst.Remove_R(1);
	bst.Remove_R(2);
	bst.Remove_R(3);
	bst.Remove_R(4);
	*/
	bst.Remove_R(5);
	bst.Remove_R(6);
	bst.Remove_R(7);
	bst.Remove_R(8);
	bst.Remove_R(9);
	bst.Remove_R(0);

	if(bst.Empty())
		cout << "此二叉搜索树为空" << endl;
	bst.InOrder();
}


void TestBSTree_string()  // int string
{
	BSTree<int, string> bst;
	bst.Insert(5, "zhou");
	bst.Insert(3, "sun");
	bst.Insert(4, "li");
	bst.Insert(1, "zhao");
	bst.Insert(7, "zheng");
	bst.Insert(8, "wang");
	bst.Insert(2, "qian");
	bst.Insert(6, "wu");
	bst.Insert(0, "baijiaxing");
	bst.Insert(9, "feng");

	bst.InOrder();

	cout << "? " << bst.Find(1)->_key << endl;
	cout << "? " << bst.Find(8)->_key << endl;
	cout << "? " << bst.Find(22) << endl;

	//bst.Remove(0);
	//bst.Remove(1);
	//bst.Remove(2);
	//bst.Remove(3);
	//bst.Remove(4);
	bst.Remove(5);
	bst.Remove(6);
	bst.Remove(7);
	bst.Remove(8);
	bst.Remove(9);


	if(bst.Empty())
		cout << "此二叉搜索树为空" << endl;
	bst.InOrder();
}

文章标题:【二叉树】二叉搜索树
网页网址:https://www.cdcxhl.com/article8/ijciop.html

成都网站建设公司_创新互联,为您提供动态网站网站设计公司定制网站网站排名微信公众号商城网站

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

网站优化排名