C++数据结构之搜索二叉树的实现
零.前言
了解搜索二叉树是为了STL中的map和set做铺垫，我们所熟知的AVL树和平衡搜索二叉树也需要搜索二叉树的基础，本文就来建立一棵搜索二叉树。
1.概念
搜索二叉树又称为二叉排序树，它或者是一棵空树，或者具有如下性质：
1.若其左子树不为空，则左子树上所有节点的值都小于根节点的值。
2.若其右子树不为空，则右子树上所有节点的值都大于根节点的值。
3.它的左右子树也分别为二叉搜索树。
2.作用
1.搜索：通过搜索二叉树的性质来进行搜索。
2.排序：二叉搜索树的中序遍历就是将所有数据进行排序。
3.迭代实现
(1)查找
对二叉搜索树的节点进行查找：
1.定义查找节点指针cur
2.比较cur->_k与要查找的节点k的值的大小关系，当_k<k的时候，cur指向该节点的右子树，否则指向左子树。
3.查找成功返回true，失败返回false
bool Find(const K& k)
{
Node* cur = _root;//1.
while (cur)//2.
{
if (cur->_k < k)
{
cur = cur->_right;
}
else if (cur->_k > k)
{
cur = cur->_left;
}
else
{
return true;//3
}
}
return false;//3
}
(2)插入
1.判断根节点指针是否为空。如果为空则直接将该节点插入根节点位置。
2.定义遍历节点cur与其父节点parent。
3.依次判断插入节点的k与当前节点cur的大小决定cur指向当前节点的左或者右节点。并在改变cur指向之前将parent赋值为cur。
如果二叉搜索树中已经有该值，则返回false。
4.当cur为空的时候，建立根据k在cur处建立节点。比较parent的_k与k的大小，判断cur建立在parent的左子树还是右子树。并返回true。
bool InsertNode(const K& k)
{
if (_root == nullptr)
{
_root = new Node(k);
return true;
}//1
Node* cur = _root;
Node* parent = nullptr;//2
while (cur)
{
if (cur->_k < k)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_k > k)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}//3
cur = new Node(k);
if (parent->_k < k)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;//4
}
(3)删除
1.首先通过cur和parent查找该节点。
2.如果cur左为空，判断cur相对于parent的位置，并将cur的右子树赋值到cur相对于parent的位置处。并删除cur。
3.如果cur右为空，判断cur相对于parent的位置，并将cur的左子树赋值到cur相对于parent的位置处。并删除cur。
4.如果cur的左右都不为空：
(1)建立一个新的节点指针min赋值为cur->right作为遍历指针，和其父节点指针minparent赋值为cur。
(2)一直向左遍历直到min->left为空。并交换min与cur的_key。
(3)判断min与minparent的位置关系，并将min的右子树放在该处。
(4)删除min，返回true。若没找到返回false。
bool Erase(const K& k)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_k < k)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_k > k)
{
parent = cur;
cur = cur->_left;
}//1
else
{
if (cur->_left == nullptr)
{
if (parent == nullptr)
{
_root = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
delete cur;
return true;
}
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;
}
delete cur;
return true;
}//2
else
{
Node* min = cur->_right;
Node* minparent = cur;//4.(1)
while(min->_left)
{
minparent = min;
min = min->_left;
}//4.(2)
cur->_k = min->_k;
if (minparent->_left == min)
{
minparent->_left = min->_right;
}
else
{
minparent->_right = min->_right;
}//4.(3)
delete min;
return true;
}
}
}
return false;//4.(4)
}
4.递归实现
(1)查找
1.判空
2.判断root->_k与k的大小，判断递归的方向。
3.如果找到了返回root节点。
Node* _FindR(const K& k)
{
return FindR(_root, k);
}//1
Node* FindR(Node* root, const K& k)
{
if (root == nullptr)
{
return nullptr;
}
if (root->_k > k)
{
return FindR(root->_left, k);
}
else if (root->_k < k)
{
return FindR(root->_right, k);
}//2
else
{
return root;
}//3
}
(2)插入
1.判断节点是否为空，如果为空将该节点插入节点的位置。并返回true
2.判断_k和k的大小，判断递归的方向。
3.如果节点值等于k返回false。
bool InsertR(const K& k)
{
return _InsertR(_root, k);
}
bool _InsertR(Node*& root, const K& k)
{
if (root == nullptr)
{
root = new Node(k);
return true;
}//1
if (root->_k < k)
{
return _InsertR(root->_right, k);
}
else if (root->_k > k)
{
return _InsertR(root->_left, k);
}//2
else
{
return false;
}//3
}
(3)删除
1.如果节点为空则返回false
2.通过_k和k的大小来判断递归方向。
3.找到该节点：
(1)定义del指针赋值为root。
(2)如果root左子树为空，则将root指向该节点的右子树。
(3)如果root右子树为空，则将root指向该节点的左子树。
(4)如果root左右子树都不为空，将min赋值为root->right，并依次向左找，直到min->left为空。并交换min的k与root的k。 然后递归到右子树来进行删除。
(5)删除原root节点(del)，并返回true。
bool EraseR(const K& k)
{
return _EraseR(_root, k);
}
bool _EraseR(Node*& root, const K& k)
{
if (root == nullptr)
return false;//1
if (root->_k < k)
{
return _EraseR(root->_right, k);
}
else if (root->_k > k)
{
return _EraseR(root->_left, k);
}//2
else
{
Node* del = root;//3.(1)
if (root->_left == nullptr)
{
root = root->_right;
}//3.(2)
else if (root->_right == nullptr)
{
root = root->_left;
}//3.(3)
else
{
Node* min = root->_right;
while (min->_left)
{
min = min->_left;
}
swap(min->_k, root->_k);
// 递归到右子树去删除
return _EraseR(root->_right, k);//3.(4)
}
delete del;
return true;//3.(5)
}
}
5.key/value模型的应用
key/value模型，即在原来k的基础上，每个节点再带有一个value值。有两种主要的应用：
(1)对应查找
利用到了二叉搜索树搜素的性质。
BSTree<string, string> word;
word.InsertNode("man", "男人");
word.InsertNode("woman", "女人");
word.InsertNode("sort", "排序");
word.InsertNode("Earth", "地球");
word.InsertNode("birth", "出生");
word.InsertNode("die", "死亡");
string str;
while (cin >> str)
{
BSTreeNode<string, string>* ret = word.Find(str);
if (ret)
{
cout << "对应的中文解释：" << ret->_v << endl;
}
else
{
cout << "无此单词" << endl;
}
}
我们向二叉搜索树中存入英文单词和中文释义，将英文单词作为k来构建二叉搜索树，如果搜索到了则打印中文释义，这样就简单构成了一个字典。
(2)判断出现次数
当我们判断一个数组中各个元素出现的次数的时候，也可以使用到二叉搜索树。
string arr[] = { "a","b","e","e","b","a","n","a","n","a","c","p","d","d","x","s","w","l" };
BSTree<string, int> counttree;
for (auto& str : arr)
{
auto ret = counttree.Find(str);
if (ret != nullptr)
{
(ret->_v)++;
}
else
{
counttree.InsertNode(str, 1);
}
}
counttree._InOrderv();
每一次出现一个元素我们就将它插入二叉搜索树中，并把它的value赋值为1，当第二次遇到这个元素的时候，在二叉搜索树中搜索该元素，人如果可以找到该元素则将该元素的value的值++。最终统计出各个元素出现的次数。
6.总结
对于二叉搜索树的理解对以后学习AVL树和红黑树具有很大的帮助
上一篇：C语言实现小型电子词典
栏 目：C代码
下一篇：C++实现五子棋游戏(注释版)
本文标题：C++数据结构之搜索二叉树的实现
本文地址：http://www.codeinn.net/misctech/212301.html
