【数据结构】二叉搜索树

【数据结构】二叉搜索树

码农世界 2024-05-23 前端 78 次浏览 0个评论

二叉搜索树是一棵很有启发意义的树，AVL树红黑树都是由他来的。

目录

  • 二叉搜索树的概念：
  • BSTree的实现：
    • 插入：
    • 删除：
    • 递归版的插入与删除：
    • 完整源码：
    • 总结：

      二叉搜索树的概念：

      二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

      • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
      • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
      • 它的左右子树也分别为二叉搜索树

        BSTree的实现：

        其实他的实现真的很简单，我们先来看节点的定义与私有变量：

        节点：

        template
struct BinarySearchTreeNode
{
	BinarySearchTreeNode(int key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
	typedef BinarySearchTreeNode BSTNode;
	BSTNode* _left;
	BSTNode* _right;
	K _key;
};

        BSTree的私有变量：

        private:
	Node* _root = nullptr;

        插入：

        注意：我们不允许插入相同的数字！

        整体逻辑是先找到插入的位置，但要注意一下要记录父亲的位置，否则找到时cur为空，没法链接了~

        	bool Insert(const K& key)
	{
		Node* newnode = new Node(key);
		if (_root == nullptr)
		{
			_root = newnode;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		// 插入操作
		if (parent->_key < key)
		{
			parent->_right = newnode;
		}
		else
		{
			parent->_left = newnode;
		}
		return true;
	}

        删除：

        删除有一点繁琐，需要将各种情况考虑到位。

        • a. 要删除的结点无孩子结点
        • b. 要删除的结点只有左孩子结点
        • c. 要删除的结点只有右孩子结点
        • d. 要删除的结点有左、右孩子结点

          那我们针对这几种情况各需要进行怎样的处理呢？

          首先a情况是可以归类为b与c，因为叶子节点也符合嘛

          那我们现在看看如何处理~

          Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
	if (cur->_key < key)
	{
		parent = cur;
		cur = cur->_right;
	}
	else if (cur->_key > key)
	{
		parent = cur;
		cur = cur->_left;
	}
	else
	{
		// erase
		// ...删除操作
}

          情况a：

          情况b与c（因为都只有一个孩子，所以放在一起讨论了）：

          情况a，b，c的代码

          注意：有可能出现单边树的情况，此时需要更新一下root节点的值。

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

          情况d：

          我们选择左子树最大节点作为替换节点

          由于我们还要进行情况b与c（在这里我们不需要进行_root的更新，因为删除的节点肯定不会是_root），所以需要一个父指针指向左子树最大节点的父亲进行链接。

          但是要注意，这里的FMaxLeft要自己灵活控制，下面只是一种方式之一，（比如父指针还是给空，但是我们要进行判断一下。）

          else
{
	Node* MaxLeft = cur->_left;
	Node* FMaxLeft = cur->_left;
	while (MaxLeft->_right)
	{
		FMaxLeft = MaxLeft;
		MaxLeft = MaxLeft->_right;
	}
	cur->_key = MaxLeft->_key;
	del = MaxLeft;
	if (FMaxLeft == MaxLeft)
	{
		cur->_left = nullptr;
	}
	else if (FMaxLeft->_left == MaxLeft)
	{
		FMaxLeft->_left = MaxLeft->_left;
	}
	else
	{
		FMaxLeft->_right = MaxLeft->_left;
	}
}

          递归版的插入与删除：

          注意这里的引用用的很妙，不需要在记录parent指针了

          	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (root->_key > key)
		{
			return _InsertR(root->_left, key);
		}
		else if(root->_key < key)
		{
			return _InsertR(root->_right, key);
		}
		else
		{
			return false;
		}
	}
	bool _eraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (root->_key > key)
		{
			return _eraseR(root->_left, key);
		}
		else if (root->_key < key)
		{
			return _eraseR(root->_right, key);
		}
		else
		{
			if (root->_left == nullptr)
			{
				Node* del = root;
				root = root->_right;
				delete del;
			}
			else if (root->_right == nullptr)
			{
				Node* del = root;
				root = root->_left;
				delete del;
			}
			else
			{
				Node*& MaxLeft = root->_left;
				while (MaxLeft->_right)
				{
					MaxLeft = MaxLeft->_right;
				}
				swap(root->_key, MaxLeft->_key);
				_eraseR(MaxLeft, key);
			}
			return true;
		}
		return false;
	}

          从递归这里我们可以看到很好的利用的引用的特性，不需要额外使用多余的对象去进行记录。

          完整源码：

          源码附带了析构，拷贝等函数（比较简单就没有写在上边），更加完整

          #pragma once
#include 
using namespace std;
template
struct BinarySearchTreeNode
{
	BinarySearchTreeNode(int key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
	typedef BinarySearchTreeNode BSTNode;
	BSTNode* _left;
	BSTNode* _right;
	K _key;
};
template
class BinarySearchTree
{
private:
	typedef BinarySearchTreeNode Node;
public:
	BinarySearchTree()
	{}
	~BinarySearchTree()
	{
		destory(_root);
	}
	BinarySearchTree(const BinarySearchTree& BSTree)
	{
		_root = copy(BSTree._root);
	}
	bool Insert(const K& key)
	{
		Node* newnode = new Node(key);
		if (_root == nullptr)
		{
			_root = newnode;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		// 插入操作
		if (parent->_key < key)
		{
			parent->_right = newnode;
		}
		else
		{
			parent->_left = newnode;
		}
		return true;
	}
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}
	void InOrder()
	{
		_InOrder(_root);
	}
	bool eraseR(const K& key)
	{
		return _eraseR(_root, key);
	}
	bool erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				// erase
				Node* del = cur;
				if (cur->_left == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
					}
				}
				else if(cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}
				}
				else
				{
					Node* MaxLeft = cur->_left;
					Node* FMaxLeft = nullptr;
					while (MaxLeft->_right)
					{
						FMaxLeft = MaxLeft;
						MaxLeft = MaxLeft->_right;
					}
					cur->_key = MaxLeft->_key;
					del = MaxLeft;
					if (FMaxLeft == nullptr)
					{
						cur->_left = nullptr;
					}
					else if (FMaxLeft->_left == MaxLeft)
					{
						FMaxLeft->_left = MaxLeft->_left;
					}
					else
					{
						FMaxLeft->_right = MaxLeft->_left;
					}
				}
				delete del;
				return true;
			}
		}
		return false;
	}
private:
	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (root->_key > key)
		{
			return _InsertR(root->_left, key);
		}
		else if(root->_key < key)
		{
			return _InsertR(root->_right, key);
		}
		else
		{
			return false;
		}
	}
	bool _eraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (root->_key > key)
		{
			return _eraseR(root->_left, key);
		}
		else if (root->_key < key)
		{
			return _eraseR(root->_right, key);
		}
		else
		{
			if (root->_left == nullptr)
			{
				Node* del = root;
				root = root->_right;
				delete del;
			}
			else if (root->_right == nullptr)
			{
				Node* del = root;
				root = root->_left;
				delete del;
			}
			else
			{
				Node*& MaxLeft = root->_left;
				while (MaxLeft->_right)
				{
					MaxLeft = MaxLeft->_right;
				}
				swap(root->_key, MaxLeft->_key);
				_eraseR(MaxLeft, key);
			}
			return true;
		}
	}
	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;
	}
	void destory(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		Node* left = root->_left;
		Node* right = root->_right;
		delete root;
		destory(left);
		destory(right);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	Node* _root = nullptr;
};

          总结：

          BSTree还是很简单的，但还是要注意细节的把控，尤其是删除的地方，要画图仔细分析一下。

          有问题的话欢迎进行讨论哦~

转载请注明来自码农世界，本文标题：《【数据结构】二叉搜索树》

百度分享代码，如果开启HTTPS请参考李洋个人博客
37815篇文章 站点 微博
每一天，每一秒，你所做的决定都会改变你的人生！

发表评论

快捷回复：

评论列表 （暂无评论，78人围观）参与讨论

还没有评论，来说两句吧...

Top