[数据结构与算法] 【数据结构】二叉搜索树(BSTree)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【数据结构】二叉搜索树(BSTree) -> 正文阅读

[数据结构与算法]【数据结构】二叉搜索树(BSTree)

二叉搜索树的概念

二叉搜索树又称为二叉排序树，是具有以下性质的二叉树：

若它的左子树不为空，则左子树上的所有结点的值都小于根结点的值
若它的右子树不为空，则右子树上的所有结点的值都大于根结点的值

在这里插入图片描述

上面两种形态的树都属于二叉搜索树

第一种情况，二叉搜索树趋近于完全二叉树，查找的时间复杂度最好，趋近于O(logN);

第二种情况，结点都在右子树上，二叉搜索树查找的时间复杂度就退化为O(N)

二叉搜索树的实现

结点类的实现

二叉搜索树的结点有三个成员变量

左子树指针
右子树指针
值

	template<class K>
struct BSTreeNode {
	BSTreeNode <K>* _left;
	BSTreeNode <K>* _right;
	K _key;

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

结构和遍历

二叉搜索树的结构很简单，只需要一个_root，也就是根结点的指针

我们要看二叉搜索树是否创建成功，可以利用它的性质，也就是二叉排序树的性质，当一个二叉搜索树中序遍历时，它遍历的数据是有序的

template<class K>
class BSTree {
    typedef BSTreeNode<K> Node;
public:    
	//中序遍历，遍历完是有序序列
	void InOlder() {
		_InOlder(_root);
		std::cout << std::endl;
	}

private:
	void _InOlder(Node* root) {
		if (root == nullptr)
			return;

		_InOlder(root->_left);
		std::cout << root->_key << " ";
		_InOlder(root->_right);
	}
private:
	Node* _root;

};

构造和拷贝构造

二叉搜索树的构造很简单，只需要把成员_root的值初始化就行

BSTree()
	:_root(nullptr)
{}

二叉搜索树的拷贝构造需要深拷贝，把结点一个一个拷贝给要构造的树

//调用子函数完成递归拷贝
Node* _Copy(Node* root) {
	if (root == nullptr) {
		return nullptr;
	}

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

	return copyNode;
}

BSTree(const BSTree<K>& cp) {
	_root = _Copy(cp._root);
}

赋值运算符重载

就是把一个已经有的树赋值给另一个树，也要进行深拷贝

有两种写法，传统写法和现代写法

传统写法

BSTree<K>& operator=(BSTree<K>& op) {
    //防止自己给自己赋值
	if(&op != this){
        _root = _Copy(op._root);
    }
    return *this;
}

现代写法

现代写法就是把外面需要给这个对象赋值的对象以传值的形式传进来，也就是把对象的信息拷贝构造到临时变量中

然后把这个临时变量对象的_root内容和this对象的_root内容进行交换，this对象的_root里面指向的就是临时对象拷贝好的树的地址

然后直接返回this对象，临时对象会在函数作用域结束时自动析构，也就是原来this对象_root里面指向的内容就会被释放，不会造成内存泄漏

BSTree<K>& operator=(BSTree<K> op){
    std::swap(_root, op._root);
    return *this;
}

析构和销毁

树的销毁也需要递归释放，一个结点一个结点进行释放，用后续遍历的方式进行结点指针的释放

//调用子函数进行递归释放
void _Destroy(Node* root) {
	if (root == nullptr) {
		return;
	}

	_Destroy(root->_left);
	_Destroy(root->_right);

	delete root;
}

~BSTree(){
	_Destroy(_root);
	_root = nullptr;
}

插入结点

二叉搜索树的插入分为两种情况

树为空，创建一个结点，直接链接到根节点
树不为空，按照二叉搜索树的性质找到插入的位置，再创建结点插入链接

树不为空的情况下，用要插入数据和结点的值进行对比，如果要插入的值小于结点的值，就到结点的左子树找插入位置，如果要插入的值大于结点的值，就到结点的右子树找，找到空就是要插入的位置，如果找到结点值和要插入值相等的情况，则插入失败

比如要把51插入到刚刚第一种情况的二叉搜索树中

在这里插入图片描述

非递归实现

bool Insert(const K& key){
    //如果节点为空，直接插入到根节点
    if(_root == nullptr){
        _root = new Node(key);
        return true;
    }
    
    Node* parent = nullptr;
    Node* cur = _root;
    
    //如果当前节点不为空，继续寻找
    while(cur){
        if(cur->_key > key){
            parent = cur;
            cur = cur-> _left;
        }
        else if(cur->_key < key){
            parent = cur;
            cur = cur-> _right;
        }
        else{
            //走到这里，说明要插入的值在树内已经存在，插入失败
            return false;
        }
    }
    //指针走到空时找到插入位置
    
    //构造一个新节点赋给cur
    cur = new Node(key);
    
    //这时需要判断插入位置在父节点的左节点还是父节点的右节点
    
    if(parent-> _key > key){
        parent-> _left = cur;
    }
    else{
        parent-> _right = cur;
    }
    
    return true;
}

递归实现

递归实现中，需要调用子函数完成传参，传入的第一个参数Node*& root，是直接传入了树根节点的引用，在递归调用时，也是传递的当前节点的地址，所以在找到节点进行插入时，是直接对原树进行插入，不是对临时变量的插入，所以不用保存父亲节点的地址来进行链接，在插入的时候就已经链接好了

//调用子函数递归插入
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 InsertR(const K& key) {
	return _InsertR(_root,key);
}

查找节点

按照搜索树的性质，分为几种情况

要查找的树为空，返回nullptr
若key值小于当前节点的值，则在当前节点的左子树中查找
若key值大于当前节点的值，则在当前节点的右子树中查找
若key值等于当前节点的值，则查找成功，返回当前节点的地址

比如在上面的树中查找72

在这里插入图片描述

非递归实现

Node* Find(const K& key) {
	//记录当前节点位置
	Node* cur = _root;

	while (cur) {
		if (cur->_key < key) {
			cur = cur->_left;
		}
		else if (cur->_key > key) {
			cur = cur->_left;
		}
		else {
			//找到了
			return cur;
		}
	}

	//没找到，到了空位置
	return nullptr;
}

递归实现

Node* _FindR(Node* root, const K& key) {
	if (root == nullptr) {
		return nullptr;
	}
	if (root->_key < key) {
		return _FindR(root->_right, key);
	}
	else if (root->_key > key) {
		return _FindR(root->_left, key);
	}
	else {
		return root;
	}
}
Node* FindR(const K& key) {
	return _FindR(key);
}

删除节点

删除节点分为四种情况

要删除的节点左子树为空，右子树不为空
要删除的节点右子树为空，左子树不为空
要删除的节点左右子树都为空
要删除的节点左右子树都不为空

要删除这个节点，首先要找到这个节点，按照上面Find的方法找到要删除的节点

不管哪种情况，要保证删除操作后仍保持二叉搜索树的特性

对这四种情况分别进行讨论

要删除的节点左子树为空，右子树不为空

判断删除的节点是不是根节点，如果要删除的节点是根节点，根节点的左子树为空，那么就需要更新根节点的位置到根节点的右孩子节点，然后释放根节点

在这里插入图片描述

如果要删除节点不是根节点，而且左子树为空，那么只需要把要删除节点的父亲节点指向要删除节点的右节点，然后释放要删除节点

比如要删除的节点是50

在这里插入图片描述

要删除的节点右子树为空，左子树不为空

这种情况的处理方法和前面类似，只需要换个方向

要删除节点的左右子树都为空

这种情况可以归到前两种情况中

要删除节点的左右子树都不为空(重点)

要删除结点的左右子树都不为空，那么删除了这个节点，想要保证这个树依旧是二叉搜索树，就有些困难了，所以这种情况，我们采用替换删除法

要想在删除掉这个结点后树依然保持二叉搜索树的特性，就要找到要删除节点的左子树中的最大结点或者右子树中的最小结点，然后把要删除结点的值和这两个值中的某一个值进行交换，然后再释放掉当前节点，就能完成删除操作

在要删除结点的右子树去找右子树的最左结点，把右子树的最左结点的值和要删除结点的值进行交换，然后释放掉右子树的最左结点

一般情况下，右子树的最左结点被删除后，最左结点的父结点的左结点指针就会指向删除节点的右孩子

在这里插入图片描述

就比如删除51，65的左结点指针就会指向51的右子树

但是有一种特殊情况，那就是要删除结点的右子树的最左结点就是它本身，这时最左结点的父节点的右结点指针指向删除节点的右孩子

在这里插入图片描述

删除91，65的右结点指针就会指向91的右子树

非递归实现

bool Erase(const K& key) {
	//先找到要删除的节点
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur) {
		if (cur->_key > key) {
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_key < key) {
			parent = cur;
			cur = cur->_right;
		}
		else {
			//找到了要删除的节点
			//分情况
			//1，要删除节点的左为空，右不为空
			if (cur->_left == nullptr) {
				//如果要删除的节点是根节点，就更新根节点的位置，再删除
				if (cur == _root) {
					_root = cur->_right;
				}
				else {
					if (parent->_left == cur) {
						parent->_left = cur->_right;
					}
					else {
						parent->_right = cur->_right;
					}
				}						
				delete cur;
				return true;
			}
			//2，要删除节点的右为空，左不为空
			else if (cur->_right == nullptr) {
				//如果要删除的节点是根节点，就更新根节点的位置，再删除
				if (cur == _root) {
					_root = cur->_left;
				}
				else {
					if (parent->_left == cur) {
						parent->_left = cur->_left;
					}
					else {
						parent->_right = cur->_left;
					}
				}		
				delete cur;
				return true;
			}
			//3，要删除节点的左右都为空
			//左右都为空的情况可以归到前两种情况处理


			//4，要删除节点的左右都不为空，替换删除
			//	 把要删除节点的左子树的最大节点或者右子树的最小节点的值赋值给要删除节点
			//   然后删除掉左子树的最大节点或者右子树的最小节点
			else {
				//替换删除

				//1，找到左子树的最大值或者右子树的最小值
						
				Node* minParent = cur;
				Node* minRight = cur->_right;
						
				while (minRight->_left) {
					minParent = minRight;
					minRight = minRight->_left;
				}
						
				//此时minRight就是要替换的节点
				//赋值给要删除的节点
				cur->_key = minRight->_key;
						
				//删除节点的右节点托管给父亲
						
				//分为两种情况
				//1.cur的right就是替换节点，也就是说cur->_left->left为空
				if (minRight == minParent->_left) {
					minParent->_left = minRight->_right;
				}
				else {	
					minParent->_right = minRight->_right;
				}
						
				delete minRight;
				return true;
			}	
		}
	}
	//没找到要删除的节点
	return false;
}

递归实现

实现思路：

若当前树为空，则删除失败，返回false
若要删除的key小于当前结点的值，则问题转化为删除当前节点的左子树中值为key的结点
若要删除的key大于当前结点的值，则问题转化为删除当前节点的右子树中值为key的结点
若要删除的key等于当前结点的值，则根据左右子树是否为空，进行处理

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* tmp = root;
			root = root->_right;
			delete tmp;
		}
		else if (root->_right == nullptr) {
			Node* tmp = root;
			root = root->_left;
			delete tmp;
		}
		else {
			Node* minRight = root->_right;

			while (minRight->_left) {
				minRight = minRight->_left;
			}

			K min = minRight->_key;

			_EraseR(root->_right, min);

			root->_key = min;
		}
		return true;
	}
}

bool EraseR(const K& key) {
	return _EraseR(_root, key);
}

二叉搜索树的应用

K模型

K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：以单词集合中的每个单词作为key，构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

上面的二叉树的实现就是K模型

KV模型

KV模型每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对

比如：英汉词典就是英文与中文的对应关系，即<word, Chinese>就构成一种键值对

? 统计数组中元素出现个数

把上面的树进行改造，可以得到KV模型的二叉搜索树

KV模型的二叉搜索树

namespace ns_KV {
	template<class K, class V>
	struct BSTreeNode {
		BSTreeNode <K, V>* _left;
		BSTreeNode <K, V>* _right;
		K _key;
		V _value;
		BSTreeNode(const K& key = K(), const V& value = V())
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}
	};

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

		BSTree(const BSTree<K, V>& cp) {
			_root = _Copy(cp._root);
		}

		BSTree<K, V>& operator=(BSTree<K, V> t) {
			swap(_root, t._root);
			return *this;
		}

		~BSTree() {
			_Destroy(_root);
			_root = nullptr;
		}

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

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

		Node* _FindR(Node* root, const K& key) {
			if (root == nullptr) {
				return nullptr;
			}
			if (root->_key < key) {
				return _FindR(root->_right, key);
			}
			else if (root->_key > key) {
				return _FindR(root->_left, key);
			}
			else {
				return root;
			}
		}

		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* tmp = root;
					root = root->_right;
					delete tmp;
				}
				else if (root->_right == nullptr) {
					Node* tmp = root;
					root = root->_left;
					delete tmp;
				}
				else {
					Node* minRight = root->_right;

					while (minRight->_left) {
						minRight = minRight->_left;
					}

					K kmin = minRight->_key;
					V vmin = minRight->_value;
					_EraseR(root->_right, kmin);

					root->_key = kmin;
					root->_value = vmin;
				}
				return true;
			}
		}


		Node* _Copy(Node* root) {
			if (root == nullptr) {
				return nullptr;
			}

			Node* copyNode = new Node(root->_key, root->_value);
			copyNode->_left = _Copy(root->_left);
			copyNode->_right = _Copy(root->_right);

			return copyNode;
		}

		void _Destroy(Node* root) {
			if (root == nullptr) {
				return;
			}

			_Destroy(root->_left);
			_Destroy(root->_right);

			delete root;
		}
	public:
		bool InsertR(const K& key, const V& value) {
			return _InsertR(_root, key, value);
		}

		Node* FindR(const K& key) {
			return _FindR(_root, key);
		}

		bool EraseR(const K& key) {
			return _EraseR(_root, key);
		}

		void InOlder() {
			_InOlder(_root);
			std::cout << std::endl;
		}


	private:
		void _InOlder(Node* root) {
			if (root == nullptr)
				return;

			_InOlder(root->_left);
			std::cout << root->_key << ":" << root->_value <<std::endl;
			_InOlder(root->_right);
		}

	private:
		Node* _root;
	};
}

基于二叉搜索树KV模型的英汉互译小程序

以<单词, 中文含义>为键值对，构建一棵二叉搜索树。二叉搜索树需要进行比较，键值对比较时只比较key
查询英文单词时，只需给出英文单词就可以快速找到与其对应的中文含义

void TestKVBSTree1() {
	ns_KV::BSTree<string, string> dict;

	dict.InsertR("cat", "猫猫");
	dict.InsertR("star", "星星");
	dict.InsertR("moon", "月亮");

	string str;
	while (cin >> str) {
		ns_KV::BSTreeNode<string, string>* ret = dict.FindR(str);
		if (ret == nullptr) {
			cout << "单词未录入词库" << endl;
		}
		else {
			cout << ret->_key << "翻译:" << ret->_value << endl;
		}
	}
}

在这里插入图片描述

统计数组中元素出现个数

对数组中的每一个元素进行Find操作，判断返回值
如果树中没有出现这个元素，就把这个元素键值对的value赋值为1
如果树种有这个元素，就把这个元素键值对的value++

void TestKVBSTree2() {
	string arr[] = { "猫", "狗", "猫", "狗", "猫", "猫", "猫", "猫", "青蛙", "青蛙", "青蛙"};
	ns_KV::BSTree<string, int> countTree;

	for (const auto& str : arr) {
		ns_KV::BSTreeNode<string, int>* ret = countTree.FindR(str);

		if (ret == nullptr) {
			//说明str第一次出现，则插入<str, 1>
			countTree.InsertR(str, 1);
		}
		else {
			ret->_value++;
		}
	}
	countTree.InOlder();
}