—别有洞天

左子树中所有节点的值小于当前节点的值。

右子树中所有节点的值大于当前节点的值。

左子树和右子树也都是二叉搜索树。

二叉搜索树的中序遍历可以得到一个升序的序列因此它常被用来实现有序集合或映射。

在二叉搜索树中查找、插入和删除操作的时间复杂度通常为O(logn)其中n为树中节点的数量这得益于二叉搜索树的结构和查找方法。

一句话总结二叉搜索树

利用二叉搜索树特性排升序。

一听到二叉树我们通常会想到的是什么递归请细细想想我们二叉搜索树的特点-左边的节点总是比父节点小右边的节点总是比父节点大那么我们对它使用中序遍历会发生什么呢还是上面的那颗二叉树对他进行中序遍历后

中序遍历结果arr{1,3,4,6,7,8,10,13,14};

(╥﹏╥)o.

本文应该是作为作者第一篇用C实现的数据结构也算是一个新的起点吧

与C语言的区别主要还是在于在此使用struct实际上是类可以在定义时就进行初始化利用的就是类的初始化列表的作用这就省去了我们C语言时需要额外定义以及调用的初始化操作。

只能说有了CC语言什么的不认识啦ʅ´◔౪◔ʃ

//节点定义templateclass

Node;public://...诸多的操作private:Node*

_root

思路判断是否为空-是-》直接给根节点赋值-否-进行循环遍历对要插入的值进行“比大小”-大往右小往左遍历直到空为止-比较空位置父节点的大小大插右小插左

Insert(const

看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程如下

情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除

情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除

情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题--替换法删除

而在b、c、d这三种情况中b和c又很相似所以以大类来划分我们实际可以分为两种。

一种是要删除的节点只有一个左孩子或者右孩子另一种是有两个孩子节点。

现在详细介绍这两种情况

当要删节点的左孩子为空时我们只需要将右半边给他的父亲就行当然我们也需要注意以下两点1、如果要删节点是根节点那么我们需要将它的右孩子的地址覆盖原节点。

2、要删节点不是根节点那么我们也需要判断要删节点是它父节点的左孩子还是右孩子左孩子则父节点的左孩子节点指向要删孩子的右孩子右孩子则父节点的右孩子节点指向要删孩子的右孩子。

当要删右孩子时也是同理只是需要注意此时要注意的第二点中要指向的是要删节点是右孩子。

下面上半部分的图为此部分的图解~

当有两个孩子节点时我们则需要用到替换法。

首先我们需要根据以下规则中的一个规则1、找到要删节点的左子树的最大节点。

2、找到要删奇点的右子树的最小节点。

接着交换要删节点和找到的这个节点。

最后删除找到节点的位置这个时候我们就需要返回到上一部分我们只有一个孩子节点时要走的步骤进行相应的操作。

为什么呢因为我们都知道要找最小或者最大只有在最左或者最右。

而此时我们一定满足只有一个孩子节点时的于要求。

下面下半部分的图为此部分的图解这里取右子树的最小~

实现如下

cur-_left;}else//表示已经找到进行删除操作{//左为空的情况if

(cur-_left

parent-_left)//因为左一定为空为父节点的左则将右半边给父即可{parent-_left

cur-_right;}else//同理为父节点的右则将右半边给父{parent-_right

cur-_right;}}delete

cur;}else//左右都不为空{//可以选择找该节点左子树的最大节点最右节点或者右子树的最小节点最左节点//这里找右树的最小节点(最左节点)Node*

parent

subleft-_key);//由于找到的是最左则默认左为空,所以只需将右链接给父节点if

(subleft

subleft-_right;}else{parent-_right

subleft;}return

nullptr)return;_InOrder(root-_left);cout

root-_key

实际上同非递归的原理是相同的不多阐述。

实在不行画递归展开图就理解了~

bool

特别注意接口的对于root的引用这对于后续删除很有作用。

当要删除只有一个孩子节点的节点时同非递归的思想是一样的。

当要删节点有两个孩子节点时在最后面采取的是装换成在子树中去删除同非递归中的找到替换节点转到只有一个孩子的操作是一样的思想。

bool

key);}else//找到了开始删除{//实际上的操作同非递归差不多这里巧妙的对root运用了引用if

(root-_left

以上我们实现的二叉搜索树实际上也被称为K模型而实际上还有一种模型叫做KV模型以下为详细介绍

K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。

比如

在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。

KV模型每一个关键码key都有与之对应的值Value即Key,

英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word,

chinese就构成一种键值对

再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word,

count就构成一种键值对

只是在K模型的基础上加了一个value值对于其它的操作都是相似的以下给出KV模型的整体代码

namespace

subLeft-_right;elseparent-_right

true;}}return

nullptr)return;_InOrder(root-_left);cout

root-_key

endl;_InOrder(root-_right);}private:Node*

_root

_key(key){}};//二叉搜索树templateclass

Kclass

Node;public://插入操作按照左小右大的规则bool

Insert(const

cur-_left;}else//表示已经找到进行删除操作{//左为空的情况if

(cur-_left

parent-_left)//因为左一定为空为父节点的左子树则将右半边给父即可{parent-_left

cur-_right;}else//同理为父节点的右则将右半边给父{parent-_right

cur-_right;}}delete

cur;}else//左右都不为空{//可以选择找该节点左子树的最大节点最右节点或者右子树的最小节点最左节点//这里找右树的最小节点(最左节点)Node*

parent

subleft-_key);//由于找到的是最左则默认左为空,所以只需将右链接给父节点if

(subleft

subleft-_right;}else{parent-_right

subleft;}return

InOrder()//中序遍历即排升序{_InOrder(_root);cout

endl;}bool

C11~BSTree(){Destroy(_root);}BSTree(const

BSTreeK

Copy(root-_left);newRoot-_right

newRoot;}void

nullptr)return;Destroy(root-_left);Destroy(root-_right);delete

root;root

key);}else//找到了开始删除{//实际上的操作同非递归差不多这里巧妙的对root运用了引用if

(root-_left

nullptr)return;_InOrder(root-_left);cout

root-_key

subLeft-_right;elseparent-_right

true;}}return

nullptr)return;_InOrder(root-_left);cout

root-_key

endl;_InOrder(root-_right);}private:Node*

_root