甜橘子，专注成都网站制作网站设计与营销型网站建设与优化
QQ :532337155
电话：028-86922220
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:1.2.二叉搜索树的实现若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
成都创新互联公司主要从事网站制作、网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务浦口,十多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792
注：
1.搜索二叉树数据的查找效率为O(N)，当搜索二叉树接近完全时，数据的查找效率较高，接近
2.当使用中序遍历遍历搜索二叉树时，遍历出来的数据是增序的。
二叉搜索树普通实现版本
BinarySearchTree.h文件：
#pragma once
templatestruct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
templateclass BSTree
{
typedef BSTreeNodeNode;
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=(BSTreet)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
DestoryTree(_root);
_root = nullptr;
}
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->_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)
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)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key< key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key >key)
{
parent = cur;
cur = cur->_left;
}
else
{
// 一个孩子--左为空 or 右为空
// 两个孩子 -- 替换法
if (cur->_left == nullptr)
{
//if (parent == nullptr)
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
//if (parent == nullptr)
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else // 两个孩子都不为空
{
// 右子树的最小节点替代
Node* minParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minParent = minRight;
minRight = minRight->_left;
}
swap(minRight->_key, cur->_key);
//cur->_key = minRight->_key;
if (minParent->_left == minRight)
{
minParent->_left = minRight->_right;
}
else
{
minParent->_right = minRight->_right;
}
delete minRight;
}
return true;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout<< endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout<< root->_key<< " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
void TestBSTree1()
{
BSTreet;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t.Insert(e);
}
t.InOrder();
t.Insert(16);
t.Insert(9);
t.InOrder();
}
void TestBSTree2()
{
BSTreet;
int a[] = { 8, 7, 9, 12, 5, 19, 20, 30,7,12 };
for (auto e : a)
{
t.Insert(e);
}
t.InOrder();
}
void TestBSTree3()
{
BSTreet;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t.Insert(e);
}
t.InOrder();
t.Erase(3);
t.Erase(8);
t.InOrder();
t.Erase(14);
t.Erase(7);
t.InOrder();
for (auto e : a)
{
t.Erase(e);
}
t.InOrder();
}
void TestBSTree4()
{
BSTreet;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t.Insert(e);
}
t.InOrder();
BSTreecopy = t;
copy.InOrder();
} test.cpp文件：
#define _CRT_SECURE_NO_WARNINGS 1
#includeusing namespace std;
#include "BinarySearchTree.h"
int main()
{
TestBSTree3();
return 0;
} 注：
1. 二叉搜索树的查找介绍 a.从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。 b.最多查找高度次，走到到空，还没找到，这个值不存在。 2. 二叉搜索树的插入介绍 插入的具体过程如下： a.树为空，则直接新增节点，赋值给root指针 b.树不空，按二叉搜索树性质查找插入位置，插入新节点 具体思路为：定义两个指针parent和cur，cur查找插入位置，parent记录cur上一个位置，当cur找到插入位置时（cur为空时），开辟节点给cur并和parent进行链接。
注：
（1）搜索二叉树一般不允许插入和里面数据相同的数据，会造成冗余。
（2）搜索二叉树数据插入的顺序不同，树的形状一般也不同，当以近似有序的数据顺序依次插入，那么二叉树的形状近似一个链表，搜索的时间复杂度接近O(N)
3. 二叉搜索树的删除介绍
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况： a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下： 情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除 情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除 情况d：在删除结点的左子树中寻找大值结点（左子树中序下的最后一个结点），或者删除结点的右子树中寻找最小值结点（右子树中序下的第一个结点），用左子树大值结点的值或右子树最小值结点的值填补到被删除节点中，再来处理左子树大值结点或右子树最小值结点的删除问题--替换法删除
情况b和情况c的实现代码（情况a融合在情况b中）如果如下图一所示，那么是有BUG的，如下图二所示的搜索树要删除根节点，此时parent指针指向空指针，parent->left或者parent->right会访问空指针，程序报错。解决方法是让搜索树的_root成员变量指向根结点的那个孩子结点即可，如下图三所示。
情况d的代码实现如果如下图一所示，那么是错误的，因为Swap交换之后该树不再是一个搜索二叉树，交换之后再递归调用Erase函数删除key是找不到key值结点并返回false的，所以我们应该手动去删除。
我们利用minRight指针找到右子树最小值结点，minParent指针指向minRight指针指向结点的父节点，然后将minRight指针指向结点的值（右子树最小值）赋值给cur指针指向的结点值，minParent指针指向结点的_left指针和minRight指针指向结点的_right指针链接（此时一定是minParent指针指向结点的_left指针指向minRight指针指向的结点，minRight指针指向结点的_left指针一定是NULL，_right指针可能为空可能指向其他结点，所以要删除minRight指针指向结点直接将minParent指针指向结点的_left指针指向minRight指针指向结点的_right指针指向的地址，然后释放minRight指针指向结点即可），释放minRight指针指向的结点，如下图三所示。
上面图三所示的代码是有BUG的，因为有可能删除结点的右子树的根就是最小结点，如下图一所示，要删除值为8的结点（根节点），此时该节点右子树的根（值为10的结点）就是最小结点。开始minRight指向值为10的结点，while循环判断条件为假不进入循环，minRight最终指向值为10的结点，也就是右子树的最小结点，而minParent指针为空，minParent指针应该为值为8的结点，所以应该用cur对minParent指针初始化。并且此时minParent指针指向结点的_right指针和minRight指针指向结点的_right指针链接（此时一定是minParent指针指向结点的_right指针指向minRight指针指向的结点，minRight指针指向结点的_left指针一定是NULL，_right指针可能为空可能指向其他结点，所以要删除minRight指针指向结点直接将minParent指针指向结点的_right指针指向minRight指针指向结点的_right指针指向的地址，然后释放minRight指针指向结点即可），释放minRight指针指向的结点。代码中，因为最后minRight指针指向结点既有可能是minParent指针指向结点的左节点也有可能是minParent指针指向结点的右节点，因此需要进行判断，如下图二所示。
4.搜索二叉树上面这种结构允许增删查功能，不允许改，修改一个节点的数值那么这个树很可能不再是搜索二叉树。
5.搜索二叉树的拷贝构造函数和赋值运算符重载函数需要进行深拷贝，这里深拷贝不能复用insert插入函数，因为插入的顺序不同搜索二叉树也不同。我们写一个CopyTree函数来递归创建一个相同的树，如下图一所示，然后搜索二叉树的拷贝构造函数复用CopyTree函数即可，如下图二所示
如果写了构造函数，那么系统自动生成的默认构造函数就不会再自动生成了，拷贝构造函数也是构造函数，如果我们写了拷贝构造函数，系统自动生成的默认构造函数不再生成，我们需要自己去显式的写构造函数。在c++11中，可以使用default关键字强制编译器自己生成默认构造函数，如下图所示
搜索二叉树的赋值运算符重载函数可以复用拷贝构造函数来进行现代写法的代码实现，如下图所示
搜索二叉树的析构函数，我们写一个DestoryTree函数来销毁释放树，如下图一所示，然后二叉树的析构函数复用DestoryTree函数即可，如下图二所示
二叉搜索树递归实现版本
BinarySearchTree.h文件：
#pragma once
template//struct BinarySearchTreeNode
struct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
templateclass BSTree
{
typedef BSTreeNodeNode;
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=(BSTreet)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
DestoryTree(_root);
_root = nullptr;
}
void InOrder()
{
_InOrder(_root);
cout<< endl;
}
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 _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);
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;
}
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;
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout<< root->_key<< " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
void TestBSTree1()
{
BSTreet;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t.InsertR(e);
}
t.InOrder();
t.InsertR(9);
BSTreecopy = t;
copy.InOrder();
}
void TestBSTree2()
{
BSTreet;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t.InsertR(e);
}
t.InOrder();
t.EraseR(3);
t.EraseR(8);
t.InOrder();
t.EraseR(14);
t.EraseR(7);
t.InOrder();
for (auto e : a)
{
t.EraseR(e);
}
t.InOrder();
} test.cpp文件：
#define _CRT_SECURE_NO_WARNINGS 1
#includeusing namespace std;
#include "BinarySearchTree.h"
int main()
{
TestBSTree2();
return 0;
} 注：
1.搜索二叉树插入函数的递归实现，用要插入的值和根结点值进行比较，如果要插入的值大于根结点值，则转换成根节点的右子树插入该值，如果要插入的值小于根结点值，则转换成根节点的左子树插入该值，要删除的值等于根结点值则返回false（搜索二叉树内不允许有相同数值的结点），如果根节点为空，则创建一个值为要插入值的结点，然后和父亲结点进行链接即可，但是如何和父亲结点进行链接呢？
方法一：可以给_InsertR函数加一个parent指针参数，如下图所示，每次调用_InsertR函数的时候除了将root的左子树和右子树传过去也将root传过去，那么每次parent指针指向的都是本次root结点的父结点，最后如果根节点为空，则创建一个值为要插入值的结点，然后和parent指针指向的结点进行链接即可。
方法二：可以给_InsertR函数的root参数加上引用，如下图所示，这样如果根节点为空时，则创建一个值为要插入值的结点，将结点指针赋值给root，因为这里root是上一层父节点的_left或_right的引用，那么赋值的时候就已经和父结点进行了链接。
因为方法二的实现更加简洁，我们使用方法二的思路来实现递归版本的插入函数，如下图所示
2.如下图所示是搜索二叉树删除函数的递归实现，用要删除入的值和根结点值进行比较，如果要删除的值大于根结点值，则转换成根节点的右子树删除该值，如果要删除的值小于根结点值，则转换成根节点的左子树删除该值，如果要删除的值等于根结点值，则和普通搜索二叉树删除函数一样，需要分三种情况（要删除的结点无孩子结点的情况融合在要删除的结点只有左孩子结点的情况内）
（1）要删除的结点只有左孩子结点，递归找到要删除的结点，此时root指向要删除的结点，那么需要将root指针指向结点的_left指针指向结点和root指针指向结点的父节点进行链接，然后释放root指针指向的结点，这里直接将root->_left赋值给root就可以完成除释放结点以外的其他工作，因为这里root是上一层父节点的_left或_right的引用，那么赋值的时候就已经将root指针指向结点的_left指针指向结点和root的父结点进行了链接。 （2）要删除的结点只有右孩子结点，递归找到要删除的结点，此时root指向要删除的结点，那么需要将root指针指向结点的_right指针指向结点和root指针指向结点的父节点进行链接，然后释放root指针指向的结点，这里直接将root->_right赋值给root就可以完成除释放结点以外的其他工作，因为这里root是上一层父节点的_left或_right的引用，那么赋值的时候就已经将root指针指向结点的_right指针指向结点和root的父结点进行了链接。 （3）要删除的结点有左、右孩子结点，与普通搜索二叉树那里一样，递归找到要删除的结点，此时root指向要删除的结点，使用minRight指针找到要删除结点的右子树最小值结点（找左子树大值结点也行，这里以右子树最小值结点为例），将minRight指针指向的右子树最小值结点的值与root指向的要删除结点的值交换，然后释放minRight指针指向的结点即可。释放minRight指针指向的结点有两种方式。一种方式和普通搜索二叉树那里一样，使用minParent指针来找到要删除结点右子树最小值结点的父节点，将该父节点和右子树最小值结点的子节点进行链接然后释放minRight指针指向的右子树最小值结点。另一种方式是调用递归删除函数，删除root指向的要删除结点右子树中的要删除的值（因为原本要删除结点的右子树最小值结点交换后此时存的值是要删除的值）（交换后root指向的要删除结点右子树依然是一颗搜索树）
注：先使用del指针将root指针的内容保存起来，那么del指针和root指针此时指向相同的结点，最后要释放root指针指向结点的时候，此时root指针已经被修改，delete del就释放了原root指针指向的结点
1.3.二叉搜索树的应用1.K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。#pragma once #includenamespace key { 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; 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; } void InOrder() { _InOrder(_root); cout<< endl; } 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 _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); 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; } 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; } } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout<< root->_key<< " "; _InOrder(root->_right); } private: Node* _root = nullptr; }; void TestBSTree1() { BSTree t; int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; for (auto e : a) { t.InsertR(e); } t.InOrder(); t.InsertR(9); BSTree copy = t; copy.InOrder(); } void TestBSTree2() { BSTree t; int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; for (auto e : a) { t.InsertR(e); } t.InOrder(); t.EraseR(3); t.EraseR(8); t.InOrder(); t.EraseR(14); t.EraseR(7); t.InOrder(); for (auto e : a) { t.EraseR(e); } t.InOrder(); } }
4.代码while (cin >>str)和代码while (scanf() != EOF)的功能相同，都是持续输入输出内容。当scanf函数读取控制台数据时遇到文件结束/文件读取失败标志EOF时会返回EOF；string类里面重载的operator>>流提取函数返回的是cin，如下图一所示，cin是istream类的对象。
ios类中有两个函数c++98中的operator void* ()和c++11中的operator bool()如下图一二所示，这两个函数的功能是判断是否提取到文件结束/文件读取失败标志EOF，提取到EOF则返回真，没有提取到EOF则返回假。
istream类是继承ios类的，因此istream类的对象cin也有operator void* ()和operator bool()两个函数。当cin >>str代码返回cin进行while循环条件判断的时候，c++98中cin对象会进行隐式类型转换，会cin.operator void*调用operator void* ()函数，该函数判断是否遇见文件结束/文件读取失败标志EOF，如果是EOF标志就返回空指针，如果不是EOF就返回非空指针；c++11中cin对象会进行隐式类型转换，会cin.operator bool调用operator bool()函数，该函数判断是否遇见文件结束/文件读取失败标志EOF，如果是EOF标志就返回0，如果不是EOF就返回1。
