二叉搜索树和二叉查找树,二叉树 二叉搜索树区别
Yyds干货库存
在写之前，今天先说一个比较简单的话题，可以算是二叉树的进阶，不过里面的内容我们已经讲过了，主要是为后面的稀有二叉树做准备。我们先来看看今天的内容。
搜索二叉树是我们学习下面AVL树和红黑树的基础，今天的这个比较简单。
什么是搜索二叉树？这也可以称为二叉查找树。反正名字不重要，关键是它的条件。二叉查找树也称为二叉排序树。它可以是空树，也可以是二叉树，具有以下属性：
如果它的左子树不为空，则左子树中所有节点的值都小于根节点的值。如果它的右子树不为空，则右子树中所有节点的值都大于根节点的值。它的左右子树分别是二分搜索法树。可以说，一个二叉查找树的中间树节点中的值是不相等的，但是当然，我们也可以存储相等的值，所以它变成了另一棵树。这个后面讨论。
搜索树的时间复杂度。如果你看一下这个名字，你会发现二叉查找树绝对是搜索的主要内容。在这里，让我们看看他们如何寻找。
我们得到一个值，并将其与根节点进行比较。如果比它大，我们就在右边的子树中寻找。如果比它小，我们就在左子树里找。如果相等，我们会找到它。这是二分搜索法的过程。
那么我想问一下，它的时间复杂度是多少？我们看看，这不就是搜索树的高度吗？应该是O(lgN)吧？记住，这是搜索二叉树最大的错误。它的时间复杂度是O(N)，主要是因为这棵树太正常了。如果是不正常的树，你会发现的。
如果你是细心的朋友，你会发现二叉查找树的中序遍历是一个升序排列，这也是二叉查找树的特点。
实现二叉查找树我们先实现一个简单的二叉查找树，先看看它的底层，然后更好的理解它的应用。
准备节点相当简单。一般来说，想要这些节点的都是用struct来声明和定义类。在这里，我们也使用模板，但没什么好说的。
模板类T
struct BSTreeNOde
{
公共：
BSTreeNOde(const T x=T())
:左(nullptr)
，右(nullptr)
，_key(x)
{
}
BSTreeNOde * left
BSTreeNOde * right
T _ key
};
现在我们可以开始实施二叉查找树了。我们发现只需要准备一个成员变量来存储根节点。
模板类T
b级树
{
公共：
typedef BSTreeNOde T节点；//这个名字有点长
公共：
BSTree()
:_root(nullptr)
{}
私人：
Node * _ root
};
中序遍历我们先来一个中序遍历，主要是验证插入和删除。
先说说吧。下面这段代码可以吗？
void inorder(节点*根)
{
if (root==nullptr)
返回；
inorder(根左)；
cout root-_ key“”；
inorder(根右)；
}
看起来不错，里面也是经过深思熟虑的。不幸的是，有一个问题。我们如何在类外调用这个函数？我们不能得到根节点，除非你写另一个函数来得到根节点。
这里，我们需要将这个函数封装在一个层中，以便更好地使用，下面是可能的。
公共：
void顺序()
{
_ in order r(_ root)；
}
私人：
void _inorderR(节点*根)
{
if (root==nullptr)
返回；
_inorderR(根-左)；
cout root-_ key“”；
_inorderR(根右)；
}从这里开始插入数据可能会很困难，我们要考虑的事情要多一点。
这里面有一个难点，就是我们找到了一个可以插入的播放位置，如何确定父节点，所以我们需要找到一个节点来记录这里的父节点，这样就可以了。
布尔插入(常量值)
{
//第一次插入
if (_root==nullptr)
{
_root=新节点(val)；
返回true
}
Node * parent=nullptr
Node * cur=_ root
而(cur！=nullptr)
{
if (val cur- _key)
{
parent=cur
cur=cur-右；
}
else if (val cur- _key)
{
parent=cur
cur=cur-left；
}
其他
{
//这里我们不允许插入相同的值
返回false
}
}
//确定某个插入的左子树或右子树
if (parent- _key值)
parent- right=新节点(val)；
其他
parent- left=新节点(val)；
返回true
}
我们先验证一下，看插入是否成功。
int main()
{
BSTree int b
int a[]={ 8，3，1，10，6，4，7，14，13 }；
int SZ=sizeof(a)/sizeof(int)；
for(int I=0；我SZ；我)
{
b .插入(a[I])；
}
b . in order()；
cout endl
//插入相同的
b .插入(8)；
b . in order()；
返回0；
}
递归版本。递归版本应该很难理解，准确的说递归版本很难。这里先解释一下，你会发现这里引用的好处。
公共：
布尔插入器(常量值)
{
return _insertR(_root，val)；
}
私人：
bool _insertR(Node* root，const T val)
{
if (root==nullptr)
{
root=新节点(val)；
}
//
if (val root- _key)
_insertR(root- right，val)；
else if (val root- _key)
_insertR(左根，val)；
其他
返回false
返回true
}
我来解释一下这个函数，主要是这个递归函数。
首先我们来看一个最简单的案例。当我们第一次插入数据时，我们需要修改_root。递归函数里面是有根的，但是不用担心，要知道，我们传入的是参数的别名，所以可以在这里直接修改。
所以现在就有了下面这个问题。让我们在其他地方插入数据。我们来看看流程。
我们递归直到我们的编译器发现root是空的，这样就可以直接赋值了，因为root是引用，这个引用也是确定的；无论我们插入左子树还是右子树。
我们也在这里验证一下。
int main()
{
BSTree int b
int a[]={ 8，3，1，10，6，4，7，14，13 }；
int SZ=sizeof(a)/sizeof(int)；
for(int I=0；我SZ；我)
{
b . insertr(a[I])；
}
b . in order()；
返回0；
}
删除数据删除数据是最难的部分。先啃这块骨头吧。删除数据分为以下四种情况，其中一种可以归入其他两种中的任何一种。
记住，即使删除了节点，这个二叉树也应该是一个二叉查找树。
删除没有左右子树的节点删除没有左右子树的节点删除没有左右子树的节点删除有左右子树的节点。第四种情况比较难，第一种可以归纳为以下两种情况中的任意一种。这里，我们断定没有左子树。先解决前三种情况吧。
我们需要一个节点来记录要删除的节点的父节点。
布尔擦除(常量值)
{
if (_root==nullptr)
返回false
Node * parent=nullptr
Node * cur=_ root
而(cur！=nullptr)
{
if (val cur- _key)
{
parent=cur
cur=cur-右；
}
else if (val cur- _key)
{
parent=cur
cur=cur-left；
}
//找到要删除的节点。
其他
{
//左子树为空或者左子树和右子树都为空
if (cur- left==nullptr)
{
}
//cur one right为空
else if (cur- right==nullptr)
{
}
//左子树和右子树都是空的
其他
{
}
}
}
返回false
}
没有左子树或没有左子树和右子树。
//cur，left，right，left为空或者都为空
if (cur- left==nullptr)
{
//首先判断被删除的节点是头节点，这样parent=nullptr
if (cur==_root)
{
_ root=cur-left；
删除cur
返回true
}
//确定要删除的节点是父节点的左子树还是右子树。
if (cur==parent- left)
{
//这里的idea不能为空。你不确定cur是否有右子树。
parent-left=cur-right；
}
其他
{
parent-right=cur-right；
}
删除cur
返回true
}有右子树没有左子树。
else if (cur- right==nullptr)
{
//还是要判断的
if (cur==_root)
{
_ root=cur-right；
删除cur
返回true
}
if (cur==parent- left)
{
parent-left=cur-right；
}
其他
{
parent-right=cur-right；
}
删除cur
返回true
}
左子树和右子树都有，这是二叉查找树最难的情况。我们需要现象来删除这个节点。这里有两种方法
在要删除的节点的左子树中找到值最大的节点，交换节点的值将其删除，在要删除的节点的右子树中找到值最小的节点，交换节点的值将其删除这样我们就可以删除我们想要的值了。这里我们寻找右边节点中的最小值。
其他
{
Node * minParent=cur
node * minRight=cur-right；
while(微右-左)
{
minParent=minRight
min right=min right-left；
}
//交换或者直接覆盖
std:swap(minRight- _key，cur-_ key)；
//删除它所在的节点
if (minParent- left==minRight)
{
min parent-left=min right-right；
}
其他
{
min parent-right=min right-right；
}
删除minRight
}
至此，我们已经写了删除。先测试一下，然后再说递归版。
int main()
{
BSTree int b
int a[]={ 8，3，1，10，6，4，7，14，13 }；
int SZ=sizeof(a)/sizeof(int)；
for(int I=0；我SZ；我)
{
b . insertr(a[I])；
}
b . in order()；
for (int e : a)
{
b .擦除(e)；
}
b . in order()；
返回0；
}
这里递归也是一个难点。像前面的递归一样，使用所有的引用。这里有三种情况，但前提是需要找到被删除的节点。
公共：
布尔橡皮擦(常量值)
{
_eraseR(_root，val)；
}
私人：
bool _eraseR(Node* root，const T val)
{
}这里面还有四种情况。直接说吧，都挺简单的。这里之所以可以直接给root赋值，是因为我们传入的是一个引用，是父节点的左或右子树，并且只能唯一确定。
bool _eraseR(Node* root，const T val)
{
if (root==nullptr)
{
返回false
}
if (root- _key值)
{
_eraseR(root- left，val)；
}
else if (root- _key val)
{
_eraseR(root- right，val)；
}
//找到了
其他
{
//也有四种情况。
if (root- left==nullptr)
{
Node * cur=root
root=root-right；
删除cur
}
else if (root- right==nullptr)
{
Node * cur=root
root=root-left；
删除cur
}
其他
{
node * minRight=root-right；
while (minRight- left！=nullptr)
{
min right=min right-left；
}
//这是好事。
swap(root- _key，minRight-_ key)；
//这里递归删除。要知道val现在所在的节点一定是没有左子树的。
return _eraseR(root- right，val)；
}
返回true
}
返回false
}
我们也来验证一下。
int main()
{
BSTree int b
int a[]={ 8，3，1，10，6，4，7，14，13 }；
int SZ=sizeof(a)/sizeof(int)；
for(int I=0；我SZ；我)
{
b . insertr(a[I])；
}
b . in order()；
for (int e : a)
{
b .橡皮擦(e)；
b . in order()；
cout endl
}
b . in order()；
返回0；
}
这里很容易找到数据，这里就不啰嗦了，直接上代码。
节点*查找(常量键)
{
if (_root==nullptr)
返回nullptr
Node * cur=_ root
while (cur)
{
if(按键当前键)
{
cur=cur-右；
}
else if (key cur- _key)
{
cur=cur-left；
}
其他
{
返回cur
}
}
返回nullptr
}
这样写的话，就有问题了。我们得到了指针，这意味着我们可以修改节点中的值。会比较麻烦，因为你不确定修改后的值是否还构成搜索二叉树。
让我们在这里改变节点的值，并用const修饰它。
模板类T
struct BSTreeNOde
{
公共：
BSTreeNOde(const T x=T())
:左(nullptr)
，右(nullptr)
，_key(x)
{
}
BSTreeNOde * left
BSTreeNOde * right
const T _ key
};
但是还有一个问题。想想吧。当我们删除数据时，我们交换节点的值，这就导致了另一个问题，因为const修改的常数是不能修改的。在这里，我不会给出解决的代码，只说思路。我们还是用const来修改交换节点的值，当然也要合理改变它们的原点。
递归编写public:
Node* findR(常量T键)
{
return _findR(_root，key)；
}
私人：
Node* _findR(Node* root，const T key)
{
if (root==nullptr)
返回nullptr
if(密钥根- _key)
return _findR(root- right，key)；
else if(密钥根- _key)
return _findR(root- left，key)；
其他
返回根目录；
}完善二叉树搜索树。我们可以写下它的拷贝结构和其他功能。这张脸挺简单的，说实话我们也不怎么用。
复制结构。我们可以完善代码。
私人：
节点*复制树(节点*根)
{
if (root==nullptr)
{
返回nullptr
}
Node* copyNode=新节点(root-_ key)；
copy node-left=copy tree(root-left)；
copy node-right=copy tree(root-right)；
返回copyNode
}
公共：
BSTree(常数BSTree T b)
:_root(nullptr)
{
_ root=copy tree(b . _ root)；
}
私有析构函数：
void DestoryTree(节点*根)
{
if (root==nullptr)
返回；
DestoryTree(根-左)；
DestoryTree(根-右)；
删除根；
}
公共：
~BSTree()
{
DestoryTree(_ root)；
_ root=nullptr
} operator=BSTree T operator=(BSTree b)
{
swap(_root，b . _ root)；
返回* this
}
在这里测试一下吧，没什么好谈的。
int main()
{
BSTree int b1
int a[]={ 8，3，1，10，6，4，7，14，13 }；
int SZ=sizeof(a)/sizeof(int)；
for(int I=0；我SZ；我)
{
B1 . insertr(a[I])；
}
BSTree int B2(B1)；//复制构造
BSTree int b3
b3=b1//运算符=
B2 . in order()；
cout endl
B3 . in order()；
cout endl
返回0；
}
相对于其他应用，我想在这里说一下它的应用。
K model K model是指只使用键作为键，结构中只需要存储键，键就是需要搜索的值。我们的英语词典很好，我们可以将英语词典中的单词放在二叉查找树中，这样我们就可以检查一个单词的拼写是否正确。上面我们实现了这个模型，后面的设定也是这个模型。
KV模型的每一个key key都有其对应的值，即key和值的键-值对。这种方法在现实生活中很常见：比如一本英汉词典就是英语和汉语的对应关系，通过英语可以快速找到对应的汉语。英语单词和它对应的中文单词(中文)构成了一个键-值对。下面的地图使用了这个模型。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。