搜索二叉树

admin2024-04-03  0

目录

搜索二叉树的概念

二叉搜索树的遍历

二叉搜索树的模拟实现

Find查找函数

 Insert插入函数

 Erase删除函数

case 1:

case 2:

待删除结点左孩子不存在,右孩子存在

 待删除结点左孩子存在,右孩子不存在

case 3:

Erase循环版本实现

中序遍历

析构函数

拷贝构造函数

赋值运算符重载

构造函数


搜索二叉树的概念

搜索二叉树,第1张

二叉搜索树的遍历

搜索二叉树,第2张

搜索二叉树,第3张

搜索二叉树,第4张

二叉搜索树的模拟实现

//结点类的实现
template <class K>
struct BinarySearchTreeNode
{
	typedef BinarySearchTreeNode Node;
	Node* _left;//指向左子树
	Node* _right;//指向右子树
	K _key;//存储当前结点数据

	//开辟新结点需要构造函数
	BinarySearchTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};
template <class K>
class BinarySearchTree
{
	typedef BinarySearchTreeNode<K> Node;
public:
    //...
private:
    Node* _root=nullptr;
};

Find查找函数

bool Find(const K& key)
{
	Node* cur = _root;
	while (cur != nullptr)
	{
		//key大于当前结点处的键值,则去该节点的右子树查找
		if (cur->_key < key)
		{
			cur = cur->_right;
		}
		//若key小于当前结点处的键值,则去该节点的左子树查找
		else if (cur->_key > key)
		{
			cur = cur->_left;
		}
		//查找过程中某个结点数据与key相等,停止查找,返回true;
		else
		{
			return true;
		}
	}
	//cur走空,找不到返回false
	return false;
}

 Insert插入函数

bool Insert(const K& key)
{
	// 空树
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	//非空树
	//parent记录父节点位置
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur != nullptr)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key>key)
		{
			parent = cur;
			cur = cur->_left;
		}
		//为维护搜索二叉树逻辑结构,同一颗树不能出现相等的数值
		else
		{
			return false;
		}
	}
	//cur已经走空,开辟节点,存储数据,建立链接关系
	cur = new Node(key);
	//存储值为key的结点链接到父节点的何处?
	if (parent->_key > key)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	return true;
}

 Erase删除函数

case 1:

搜索二叉树,第5张

case 2:

待删除结点左孩子不存在,右孩子存在

搜索二叉树,第6张

if(cur->_left==nullptr)
{
   parent->_right=cur->_right;
   delete cur;
}

搜索二叉树,第7张

if(cur->_left==nullptr)
{
   parent->_left=cur->_right;
   delete cur;
}
if(cur->_left==nullptr)
{
   if(parent->_key < cur->_key)
   {
      parent->_right=cur->_right;
   }
   if(parent->_key > cur->_key)
   {
      parent->_left=cur->_right;
   }
   delete cur;
}

搜索二叉树,第8张

if(cur->_left==nullptr)
{
   if(cur == _root)
   {
      _root = cur->_right;
      delete cur;
   }
}
if (cur->_left == nullptr)
{
	if (cur == _root)
	{
		_root = cur->_right;
	}
	else
	{
		if (parent->_key < cur->_key)
		{
			parent->_right = cur->_right;
		}
		else
		{
			parent->_left = cur->_right;
		}
	}
	delete cur;
	return true;
}
 待删除结点左孩子存在,右孩子不存在

搜索二叉树,第9张

if(cur->_right == nullptr)
{
   parent->_right=cur->_left;
   delete cur;
}

搜索二叉树,第10张

if(cur->_right==nullptr)
{
   parent->_left=cur->_left;
   delete cur;
}
if(cur->_right==nullptr)
{
   if(parent->_key < cur->_key)
   {
      parent->_right=cur->_left;
   }
   if(parent->_key > cur->_key)
   {
      parent->_left=cur->_left;
   }
   delete cur;
}

搜索二叉树,第11张

if(cur->_right==nullptr)
{
   if(cur == _root)
   {
      _root = cur->_left;
      delete cur;
   }
}
//待删除结点左孩子存在,右孩子不存在
else if (cur->_right == nullptr)
{
	if (cur == _root)
	{
		_root = cur->_left;
	}
	else
	{
		if (parent->_key < cur->_key)
		{
			parent->_right = cur->_left;
		}
		else
		{
			parent->_left = cur->_right;
		}
	}
	delete cur;
	return true;
}

case 3:

搜索二叉树,第12张

//寻找RightMin结点即右子树的最左结点
Node* RightMinParent = cur;
Node* RightMin = cur->_right;
while (RightMin->_left != nullptr)
{
	RightMinParent = RightMin;
	RightMin = RightMin->_left;
}
//找到RightMin结点,替换删除
cur->_key = RightMin->_key;
//链接
if (RightMinParent->_left == RightMin)//RightMin->_left==nullptr
{
	RightMinParent->_left = RightMin->_right;
}
if (RightMinParent->_right == RightMin)
{
	RightMinParent->_right = RightMin->_right;
}
delete RightMin;
return true;

Erase循环版本实现

bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key>key)
{
parent = cur;
cur = cur->_left;
}
//查找到待删除元素所在的结点
else
{
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
	if (parent->_key < cur->_key)
	{
		parent->_right = cur->_right;
	}
	else
	{
		parent->_left = cur->_right;
	}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
	if (cur == _root)
	{
		_root = cur->_left;
	}
	else
	{
		if (parent->_key < cur->_key)
		{
			parent->_right = cur->_left;
		}
		else
		{
			parent->_left = cur->_right;
		}
	}
	delete cur;
	return true;
}
else
{
//寻找RightMin结点即右子树的最左结点
Node* RightMinParent = cur;
Node* RightMin = cur->_right;
while (RightMin->_left != nullptr)
{
	RightMinParent = RightMin;
	RightMin = RightMin->_left;
}
//找到RightMin结点,替换删除
cur->_key = RightMin->_key;
//链接
if (RightMinParent->_left == RightMin)//RightMin->_left==nullptr
{
	RightMinParent->_left = RightMin->_right;
}
if (RightMinParent->_right == RightMin)
{
	RightMinParent->_right = RightMin->_right;
}
delete RightMin;
return true;
}
}
}
return false;
}

中序遍历

//搜索二叉树的中序遍历(左子树-->根-->右子树)
//外部需要将_root传递给root,但是外部无法访问_root
void _InOrder(Node* root)
{
	if (root == nullptr)
	{
		return;
	}
	_InOrder(root->_left);
	cout << root->_key << " ";
	_InOrder(root->_right);
}
void InOrder()
{
    _InOrder(_root);
	cout << endl;
}

析构函数

//首先销毁左子树,其次销毁右子树,最后销毁根结点;
void Destroy(Node* root)
{
	if (root == nullptr)
		return;
	Destroy(root->_left);
	Destroy(root->_right);
	delete root;
}
~BinarySearchTree()
{
	Destroy(_root);
}

拷贝构造函数

BinarySearchTree<int> t1(t);
Node* copy(Node* root)
{
	if (root == nullptr)
	{
		return nullptr;
	}
	Node* NewRoot = new Node(root->_key);
	NewRoot->_left = copy(root->_left);
	NewRoot->_right = copy(root->_right);
	return NewRoot;
}
BinarySearchTree(const BinarySearchTree<K>& t)
{
    _root = copy(t._root);
}

赋值运算符重载

//BinarySearchTree<int> t2 = t1;
BinarySearchTree<K>& operator=(const BinarySearchTree<K>& t)
{
	swap(_root, t._root);
	return *this;
}

构造函数

//构造函数
BinarySearchTree() = default;//强制生成默认构造

搜索二叉树,第13张

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!