我们都知道二叉树只有附加上一些特性才具有实用的价值,而本章主要讲解二叉树进阶的内容-二叉搜索树
二叉搜索树(Binary Search Tree)又称二叉排序树,也称作二叉查找树它或者是一棵空树,或者是具有以下性质的二叉树
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,为O(log n)(理想状态下和完全二叉树形似)
注:对于极端状态下,查找、插入为O(n)(形似单链表)
二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如map,set等
template<class K>
struct BSTreeNode
{
//记录左右子树
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
//存值
K _key;
//构造函数
BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool Insert(const K& key);
Node* Find(const K& key);
bool Erase(const K& key);
void InOrder();
private:
void _InOrder(Node* root);
Node* _root = nullptr;
};
注:由于二叉搜索树的特性,所以二叉搜索树不能修改key
BSTree()
:_root(nullptr)
{}
BSTree(const BSTree<K>& t)
{
_root = _Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{
std::swap(_root, t._root);
return *this;
}
~BSTree()
{
_Destory(_root);
}
Node* _Copy(Node* root)
{
//空结点构建
if (root == nullptr)
return nullptr;
//构建当前结点
Node* newnode = new Node(root->_key);
//递归构建左右子树
newnode->_left = _Copy(root->_left);
newnode->_right = _Copy(root->_right);
return newnode;
}
void _Destory(Node*& root)
{
if (root == nullptr)
return;
//后序遍历释放结点
_Destory(root->_left);
_Destory(root->_right);
//释放置空结点
delete root;
root = nullptr;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
Node* FindR(const K& key)
{
return _FindR(_root,key);
}
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)
return nullptr;
if (root->_key == key)
return root;
else if (root->_key > key)
return _FindR(root->_left, key);
else
return _FindR(root->_right, key);
}
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* prev = nullptr;
while (cur)
{
if (cur->_key > key)
{
prev = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
prev = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(key);
//依靠键值比较来决定连接位置(依靠节点地址来判断会误判)
if (prev->_key > key)
{
prev->_left = cur;
}
else
{
prev->_right = cur;
}
return true;
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
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;
}
}
a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点
注:实际情况a可以与情况b或者c合并起来
bool Erase(const K& key)
{
Node* cur = _root;
Node* prev = nullptr;//记录父结点
while (cur)
{
if (cur->_key > key)
{
prev = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
prev = cur;
cur = cur->_right;
}
else//找到了
{
//分情况讨论
if (cur->_left == nullptr)
{
//根节点特殊处理
if (cur == _root)
{
_root = cur->_right;
}
else
{
//判断是左还是右
if (prev->_left == cur)
{
prev->_left = cur->_right;
}
else
{
prev->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (prev->_left == cur)
{
prev->_left = cur->_left;
}
else
{
prev->_right = cur->_left;
}
}
delete cur;
}
else
{
//找到左子树中最大的结点
Node* maxLeft = cur->_left;
while (maxLeft->_right)
{
maxLeft = maxLeft->_right;
}
K max = maxLeft->_key;
//先删再替换
Erase(max);
cur->_key = max;
}
return true;
}
}
return false;
}
bool EraseR(const K& key)
{
return _EraseR(_root, 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
{
//记录当前结点
Node* del = root;
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
//找到右边最小结点
Node* minR = root->_right;
while (minR->_left)
{
minR = minR->_left;
}
//替换值
root->_key = minR->_key;
_EraseR(root->_right, root->_key);
return true;
}
delete del;
return true;
}
}
K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值
以单词集合中的每个单词作为key,构建一棵二叉搜索树在二叉搜索树中,检索该单词是否存在,存在则拼写正确,不存在则拼写错误
每一个关键码key,都有与之对应的值Value,即**<Key, Value>**的键值
<单词,中文含义>为键值对构造二叉搜索树,二叉搜索树需要比较,键值对比较时只比较Key查询英文单词时,只需给出英文单词,就可快速找到与其对应的key
template<class K, class V>
struct BSTNode
{
BSTNode(const K& key = K(), const V& value = V())
: _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value)
{}
BSTNode<T>* _pLeft;
BSTNode<T>* _pRight;
K _key;
V _value
};
template<class K, class V>
class BSTree
{
typedef BSTNode<K, V> Node;
typedef Node* PNode;
public:
BSTree() : _pRoot(nullptr)
{}
~BSTree();
PNode Find(const K& key);
bool Insert(const K& key, const V& value)
{
// ...
PNode pCur = _pRoot;
PNode pParent = nullptr;
while (pCur)
{
pParent = pCur;
if (key < pCur->_key)
pCur = pCur->_pLeft;
else if (key > pCur->_key)
pCur = pCur->_pRight; // 元素已经在树中存在
else
return false;
}
// ...
return true;
}
bool Erase(const K& key)
{
// ...
return true;
}
private:
PNode _pRoot;
};