补充二叉搜索树C++版实现(建议看这)和应用

一.实现二叉搜索树

这里再简单介绍一下二叉搜索树: 首先二叉搜索树是一个二叉树,具有的性质为,左子树的结点值比父节点值小,右子树结点值比父节点值大,并且左右子树同样符合这种性质。 实现的二叉树的功能有:增加一个结点,查找一个结点,删除一个结点,和中序遍历。 为什么没有修改一个结点,一般二叉搜索树的结点值不要轻易修改,不然可能不符合二叉搜索树的性质了。但是KV模型可以修改val的值,下面有说明。 为什么要加一个中序遍历:因为二叉搜索树的中序遍历是有序的。

具体细节可以看这篇博客,里面有详细说明如何实现:

这里还再强调一下二叉搜索树的删除:

删除分为四种情况:

左结点和右节点为空,直接删除。注意:只有一个结点的情况

左节点不为空,右节点为空,将左节点连接到当前节点的父节点

左节点为空,右节点不为空,将右节点连接到当前节点的父节点

左右结点都不为空,使用替换法,找到右子树中的最小值,将该值替换掉要删除结点的值。再将右子树的最小值删除。或者找到左子树中的最大值,将该值替换掉要删除结点的值。再将右左子树的最大值删除。

下面是实现代码:

注意:当只有一个节点,删除节点时,直接删除节点皆可,还需要将头节点指控,避免野指针。

//只有一个结点
					if (prev == nullptr){
						delete cur;
						//要将这个置空,不让就会是野指针
						_root = nullptr;
						return true;
					}

删除节点要考虑空树的情况。

#pragma once
#include<iostream>
using namespace std;


//模板不要与实现分开

template<class K>
struct BSTreeNode{
	BSTreeNode(K val)
	:_left(nullptr)
	, _right(nullptr)
	, _val(val)
	{}

	BSTreeNode *_left;
	BSTreeNode *_right;

	K _val;
};

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	//插入
	bool Insert(K val){
		//判断_root
		if (_root == nullptr){
			_root = new Node(val);
			return true;
		}
		Node *cur = _root;
		//找插入位置,一定作为叶节点插入
		Node *prev = nullptr;//记录要插入的结点,就是要插入结点的父节点
		while (cur){
			if (val > cur->_val){
				prev = cur;
				cur = cur->_right;
			}
			else if (val < cur->_val){
				prev = cur;
				cur = cur->_left;
			}
			else{
				cout << "已存在" << endl;
				return false;
			}
		}
		//找到
		cur = new Node(val);
		//判断插入结点的左边还是右边
		if (prev->_val > val){
			prev->_left = cur;
		}
		else if (prev->_val < val){
			prev->_right = cur;
		}
		else{

		}
		return true;
	}

	//找结点
	Node *FindNode(K val){
		if (_root == nullptr){
			cout << "不存在" << endl;
			return nullptr;
		}
		Node *cur = _root;
		while (cur){
			if (val > cur->_val){
				cur = cur->_right;
			}
			else if (val < cur->_val){
				cur = cur->_left;
			}
			else{
				
				return cur;
			}
		}
		cout << "不存在" << endl;
		return nullptr;
	}
	//删除
	bool Erase(K val){
		if (_root == nullptr){
			return false;
		}
		//找结点
		Node *cur = _root;
		Node *prev = nullptr;
		while (cur){
			if (val > cur->_val){
				prev = cur;
				cur = cur->_right;
			}
			else if (val < cur->_val){
				prev = cur;
				cur = cur->_left;
			}
			else{
				//找到
				if (cur->_left == nullptr&&cur->_right == nullptr){
					//只有一个结点
					if (prev == nullptr){
						delete cur;
						//要将这个置空,不让就会是野指针
						_root = nullptr;
						return true;
					}

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

					}
					delete cur;
					return true;
				}
				if (cur->_left&&cur->_right == nullptr){
					if (prev->_left == cur){
						prev->_left = cur->_left;
					}
					else if (prev->_right == cur){
						prev->_right = cur->_left;
					}
					else{

					}
					delete cur;
					return true;
				}
				if (cur->_left==nullptr&&cur->_right){
					if (prev->_left == cur){
						prev->_left = cur->_right;
					}
					else if (prev->_right == cur){
						prev->_right = cur->_right;
					}
					else{

					}
					delete cur;
					return true;
				}
				if (cur->_left&&cur->_right){
					//找右子树最小值
					
					Node *tail = cur;
					tail = tail->_right;
					Node *MinRightParent = cur;
					while (tail->_left){
						MinRightParent = tail;
						tail = tail->_left;
					}
					K MinRight = tail->_val;
					//删除右子树最小值结点,左子树肯定为nullptr
					if (MinRightParent->_left == tail){
						MinRightParent->_left = tail->_right;
					}
					else if (MinRightParent->_right == tail){
						MinRightParent->_right = tail->_right;
					}
					else{

					}
					
					delete tail;
					//值替换
					cur->_val = MinRight;
					
					return true;

				}

				
			}
		}
		//没找到
		return false;
	}


	//中序遍历
	void _InNode(Node *root){
		if (root){
			_InNode(root->_left);
			cout << root->_val;
			_InNode(root->_right);
		}
	}
    //类外调用InNode时传入this指针,不好递归,所以调用_InNode
	void InNode(){
		_InNode(_root);
		cout << endl;
	}

private:
	Node *_root = nullptr;
};

二. 二叉搜索树的应用

2.1 排序

这个排序很简单,一个二叉搜索树,中序遍历后就是有序的。

例如:

2.2 搜索

2.2.1 K模型

K模型:结构体中只有一个有效值Key,即只有Key最为关键码,关键码就是要找的值。主要功能是判断在不在或者正不正确的问题。

例如:给一个单词,判断该单词是否拼写正确。

1.以单词集合的每一个单词构建一颗二叉搜索树

2.再二叉搜索树中查找单词是否存在,找出后,查看单词是否拼写正确。

上面写的结构体中只有一个Key的二叉搜索树就可以应用再K模型里。

2.2.2 KV模型(常用)

KV模型:每一个关键码都会有与之对应的value,即<key,value>键值对。二叉搜索树的构建依然是以key构建,通过查找key来得到需要的信息value。一般这个模型的结构体中有两个有效值key和value。

例如:中英词典,通过中文来找英文。

1.以单词集合中的中文key来构建一颗二叉搜索树。

2.通过中文,再二叉搜索树里查找是否存在,找出后,得到相应的英文value。

代码实现KV模型,实际就是再上面的基础上,结点所里一个值。

#pragma once

#include<iostream>
using namespace std;

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

template<class K,class V>
class KVBSTtree
{
	typedef BSTreeNode<K,V> Node;
public:
	bool Insert(K key, V value){
		if (_root == nullptr){
			_root = new Node(key, value);
			return true;
		}
		Node *cur = _root;
		Node *curparent = nullptr;
		while (cur){
			if (key > cur->_key){
				curparent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key){
				curparent = cur;
				cur = cur->_left;
			}
			else{
				cout << "已存在" << endl;
				return false;
			}
		}
		//找到插入位置
		cur = new Node(key, value);
		//判断插入父亲的左边还是右边
		if (curparent->_key < key){
			curparent->_right = cur;
		}
		else if (curparent->_key>key){
			curparent->_left = cur;
		}
		else{

		}
		return true;

	}

	Node *Find(K key){
		if (_root == nullptr){
			//cout << "没找到" << endl;
			return nullptr;
		}
		Node *cur = _root;
		while (cur){
			if (key > cur->_key){
				cur = cur->_right;
			}
			else if (key < cur->_key){
				cur = cur->_left;
			}
			else{
				return cur;
			}
		}
		//没找到
		return nullptr;
	}

	bool Erase(K key){
		if (_root == nullptr){
			return false;
		}
		Node *curparent = nullptr;
		Node *cur = _root;
		while (cur){
			if (key > cur->_key){
				curparent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key){
				curparent = cur;
				cur = cur->_left;
			}
			else{
				if (cur->_left == nullptr&&cur->_right == nullptr){
					//只有一个节点
					if (curparent == nullptr){
						delete cur;
						_root = nullptr;
						return true;
					}
					
					if (curparent->_left == cur){
						curparent->_left = nullptr;
					}
					else{
						curparent->_right = nullptr;
					}
					//先删除结点再释放,先释放即找不到了
					delete cur;
				}
				else if (cur->_left == nullptr&&cur->_right){
					if (curparent->_left == cur){
						curparent->_left = cur->_right;
					}
					else{
						curparent->_right = cur->_right;
					}
					delete cur;
				}
				else if (cur->_left &&cur->_right == nullptr){
					if (curparent->_left == cur){
						curparent->_left = cur->_left;
					}
					else{
						curparent->_right = cur->_left;
					}
					delete cur;
				}
				else{
					Node *Minparent = cur;
					//找右子树最小值
					Node *tail = cur->_right;
					while (tail->_left){
						Minparent = tail;
						tail=tail->_left;
					}
					K tmpkey = tail->_key;
					V tmpvalue = tail->_value;
					cur->_key = tmpkey;
					cur->_value = tmpvalue;
					//删除右子树最小值
					if (Minparent->_left == tail){
						Minparent->_left = tail->_right;
					}
					else{
						Minparent->_right = tail->_right;
					}
					delete tail;

				}
				return true;


			}
		

		}
		return false;

	}
	void _InNode(Node *root){
		if (root){
			_InNode(root->_left);
			cout << root->_key << "->" << root->_value <<  ;
			_InNode(root->_right);
		}
	}

	void InNode(){
		_InNode(_root);
		cout << endl;
	}

private:
	Node *_root = nullptr;
};

简易实现一个电子词典

给定单词,找到出现次数

 三.二叉搜索树的性能分析

二叉搜索树插入和删除前都必须先查找,查找效率代表了二叉搜索树中的各个操作的效率。

对于二叉搜索树的查找效率和树的高度有关。但是树的高度又和加入集合的数值顺序有关。不同的顺序可以得到不同的二叉搜索树。并且对于有序序列,形成的二叉搜索树会变成一个链状结构,效率大大降低。

如一个集合:int arr[] = { 3, 4, 5, 6, 7, 8, 9 };形成的二叉搜索树为:

查找效率最坏情况为O(n)。

总结: 最好情况下,二叉搜索树为完全二叉树,时间复杂度为O(logN)。 最坏情况,有序,二叉搜索树为单支树,时间复杂度为O(N)。
经验分享 程序员 微信小程序 职场和发展