• 二叉搜索树

    文章目录

    1. 二叉搜索树

    二叉树搜索树又称二叉排序树，它可以为空树。如果不为空树，它本身及其左右子树都要满足左小右大的规则(相对于每一棵树的根而言)。

    优势：查找值非常快，最多查找高度次，时间复杂度为O(n)。其查找顺序与中序遍历相似。

    最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：O(log2 N)
    最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：O(N)

    2. 模拟实现二叉搜索树

    二叉搜索树的模板参数习惯于用K(key的缩写)。这里我们默认不插入重复的值。

    2.1 二叉搜索树非递归版本

    定义cur、parent两个变量，cur遍历寻找插入的位置(cur的值小于key往右边走，反之走左边)，parent记录上一层。cur走到空，new一个插入的节点和parent连接起来，如果插入的值比parent小，就在左边插入，反之，在右边插入。

    image-20220725135713836

    #pragma once

// 二叉搜索树的节点
template
//struct BinarySearchTreeNode
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;

	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

template
class BSTree
{
	typedef BSTreeNode Node;
public:
	bool Insert(const K& key)
	{
        // 空树
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
        // cur寻找插入位置
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		
        // 插入节点
		cur = new Node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}
    
    //const Node* Find(const K& key)
    //key的这种结构不允许改数据，会破坏结构
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}

		return false;
	}

	bool Erase(const K& key);

	void InOrder()
	{
		_InOrder(_root);
	}

private:
    // 内部的子函数，如果不继承可以封装为私有
    // 中序遍历
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114

    2.2 真正的大问题erase

    对于下图的二叉搜索树，7节点是叶子节点，直接删除。14节点只有一个孩子也好删，因为14节点的左右孩子肯定都比10要大，直接删除，让10的右边指向这一个孩子(托孤)。

    3和8节点是不好删除的，因为它们都有两个孩子，3节点的孩子不可能都托孤给8。这个时候就要用替换法删除。

    替换法:以删除的节点为根节点，找到左子树的最大值节点(该节点的右一定为空)或者右子树的最小值节点(该节点的左一定为空)，替换该节点和删除节点的值后，用直接删除或者托孤的方法删除该节点。实际上直接删除也可以看成托孤。

    (1)找右子树的最小节点

    以根节点8为例，找到其右子树的最小节点10，把10的值给8节点，然后删除10节点。因为10节点是右数的最左节点，所以它只可能有一个孩子或者没有孩子，再用托孤的方式去删除。

    (2)找左子树的最大节点

    以根节点8为例，找到其左子树的最大节点7，交换值后，删除7。因为是左子树的最右节点，要么没有孩子，要么只有一个孩子，所以用托孤的方法删除。

    image-20220729074938682

    2.3 erase的实现

    首先用cur查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的节点可能分下面3种情况：
    叶子节点可以看成(1)或者(2)，这里我们看成(2)
    (1)如果要删除的节点只有左孩子，就让父亲指向我的左孩子。
    (2)如果要删除的节点只有右孩子，就让父亲指向我的右孩子。
    (3)如果删除的节点有两个孩子，就用替换法来删除。

    到底是让父亲的左还是右来指向我的孩子呢？

    cur左孩子为空的前提下，如果cur要删除父亲的左孩子，cur的左右孩子肯定都比父亲小。就让父亲的左指向cur的右。如果cur要删除父亲的右孩子，cur的左右孩子肯定都比父亲大，就让父亲的右指向cur的右。

    cur右孩子为空同理。

    image-20220729090316557

    cur左右孩子都不为空就用替换法，我们这里找右子树的最小节点(以cur为根)，因为交换后就变成删除右子树的最小节点，此时该节点左孩子一定为空(因为是最小节点)，继续用托孤的方法删除该节点。

    image-20220729092815630

    bool Erase(const K& key)
{
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
        //删除的值比当前节点的值要大
		if (cur->_key < key)
		{
            // 走之前把cur给父亲，cur往右走
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else //找到了要删除的节点,分情况讨论
            
		{
			// 一个孩子--左为空 or 右为空
			if (cur->_left == nullptr)  // 左为空
			{
				//if (parent == nullptr)
                // 如果根节点的左为空且cur删除根节点
                // parent是空，此时空指针非法访问
                // 让root走到cur的右就达到了删除根节点的目的
				if (cur == _root)
				{
					_root = cur->_right;// 因为cur左为空，根节点走到cur的右
				}
				else
				{
					if (cur == parent->_left)  // cur删除父亲的左孩子
					{
						parent->_left = cur->_right;//cur左为空,父左指向cur右
					}
					else// cur删除父亲的右孩子
					{
						parent->_right = cur->_right;//cur左为空,父右指向cur右
					}
				}
				delete cur;// 删除节点
			}
			else if (cur->_right == nullptr)// 右为空
			{
				//if (parent == nullptr)
				if (cur == _root)// 特殊情况
				{
					_root = cur->_left;// 因为cur右为空，根节点走到cur的左
				}
				else
				{
					if (cur == parent->_left)// cur删除父亲的左孩子
					{
						parent->_left = cur->_left;//cur右为空,父左指向cur左
					}
					else// cur删除父亲的右孩子
					{
						parent->_right = cur->_left;//cur右为空,父右指向cur左
					}
				}

				delete cur;
			}
			else // 两个孩子都不为空
			{
				// 右子树的最小节点替代
				Node* minParent = cur; //minParent不能初始化为空，否则删除8会出错
				Node* minRight = cur->_right;
				while (minRight->_left)
				{
					minParent = minRight;
					minRight = minRight->_left;
				}

				swap(minRight->_key, cur->_key);
				//cur->_key = minRight->_key;
                // minRight的左一定为空
				if (minParent->_left == minRight)
				{
					minParent->_left = minRight->_right;
				}
				else
				{
					minParent->_right = minRight->_right;
				}

				delete minRight;
			}

			return true;
		}
	}
	// 找不到要删除的值，返回
	return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98

    2.4 拷贝构造和析构

    删除二叉树要用后序遍历递归删除，因为析构函数没有参数，不能递归，所以得再套一层。拷贝构造函数用前序递归复制二叉树。赋值运算符重载利用拷贝构造函数来解决。

    image-20220729100808167

    template
class BSTree
{
	typedef BSTreeNode Node;
private:
	void DestoryTree(Node* root)
	{
		if (root == nullptr)
			return;
		
		DestoryTree(root->_left);
		DestoryTree(root->_right);
		delete root;
	}

	Node* CopyTree(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* copyNode = new Node(root->_key);
		copyNode->_left = CopyTree(root->_left);
		copyNode->_right = CopyTree(root->_right);

		return copyNode;
	}
public:
    // 拷贝构造也是构造，写了就不会生成默认构造函数
	// 强制编译器自己生成构造
	// C++11
	BSTree() = default;

	BSTree(const BSTree& t)
	{
		_root = CopyTree(t._root);
	}

	// t1 = t2
	BSTree& operator=(BSTree t)
	{
		swap(_root, t._root);
		return *this;
	}

	~BSTree()
	{
		DestoryTree(_root);
		_root = nullptr;
	}
private:
	Node* _root = nullptr;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    2.5 二叉搜索树递归版本

    FindR转换成最小规模子问题，如果查找值比当前节点的值大，那么就去你右子树里找，如果查找值比当前节点的值小，那么就去你的左子树里找。

    2.5.2 InsertR

    InsertR转换成最小规模子问题，如果插入值比当前节点的值大，那么就去你右子树里插入，如果插入值比当前节点的值小，那么就去你的左子树里插入。root==nullptr就可以创建一个插入值的节点插入了。但是创建的节点是一个局部变量，递归返回时会销毁，如何把该节点和父亲连接起来？

    传指针的引用就可以了。因为指针传指针是值传递，递归时的连接不会改变实际的连接，所以要传引用。

    image-20220729102748749

    2.5.3 EraseR

    EraseR转换成最小规模子问题，如果删除值比当前节点的值大，那么就去你右子树里删除，如果删除值比当前节点的值小，那么就去你的左子树里删除。相等就可以删除了。同样是传指针的引用，删除的逻辑和非递归相似。

    image-20220729110520445

    public:
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}

	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
private:	
	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;

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

	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
			return false;

		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else
		{
			Node* del = root;
			// 删除
			if (root->_left == nullptr)
			{
                // 这里就解决了(根节点左为空删除根节点)的问题
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
                // 找右子树最小节点
				Node* minRight = root->_right;
				while (minRight->_left)
				{
					minRight = minRight->_left;
				}

				swap(root->_key, minRight->_key);

                // 在root的右子树递归删除minRight
                // 因为minRight的左一定为空，递归能找到
				return _EraseR(root->_right, key);
			}

			delete del;
			return true;
		}
	}

	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

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


				// 在root的右子树递归删除minRight
                // 因为minRight的左一定为空，递归能找到
				return _EraseR(root->_right, key);
			}

			delete del;
			return true;
		}
	}

	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
  • 相关阅读:
    python打包成可执行文件app(Mac版)
    成都收录《乡村振兴战略下传统村落文化旅游设计》许少辉八一著作
    如何让你的桌面干净得像一张白纸（详细教程）
    油溶性硫化镉量子点，CdS 量子点，CdS QDS
    C++ Qt开发：使用顺序容器类
    Unity中Shader的GI的间接光实现
    你犯过程序员容易犯的这些错误吗？快来看看！
    [Machine Learning][Part 2]监督学习的实现
    2022年“移动云杯”算力网络应用创新大赛圆满落幕，百万大奖揭晓！
    LCR 144. 翻转二叉树
  • 原文地址：https://blog.csdn.net/iwkxi/article/details/126403248