。

若它的右子树不为空#xff0c;则右子树上所有结点的值都大于根结…二叉搜索树的概念

二叉搜索树又称为二叉排序树它或者是一棵空树或者是具有以下性质的二叉树

若它的左子树不为空则左子树上所有结点的值都小于根结点的值。

若它的右子树不为空则右子树上所有结点的值都大于根结点的值。

它的左右子树也分别是二叉搜索树。

由于二叉搜索树中每个结点左子树上所有结点的值都小于该结点的值右子树上所有结点的值都大于该结点的值因此对二叉搜索树进行中序遍历后得到的是升序序列也就不难理解了。

int

a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。

树为空则直接新增节点赋值给root指针

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

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

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

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

结点类

结点类当中包含三个成员变量结点值、左指针、右指针。

结点类当中只需实现一个构造函数即可用于构造指定结点值的结点。

templateclass

default;//指定强制生成默认构造//默认构造BSTree();//拷贝构造BSTree(const

BSTreeK

t);//析构函数~BSTree();//插入key值bool

Insert(const

Copy(root-_left);newRoot-_right

newRoot;

}赋值运算符重载函数的现代写法非常精辟函数在接收右值时并没有使用引用进行接收因为这样可以间接调用BSTree的拷贝构造函数完成拷贝构造。

我们只需将这个拷贝构造出来的对象的二叉搜索树与this对象的二叉搜索树进行交换就相当于完成了赋值操作而拷贝构造出来的对象t会在该赋值运算符重载函数调用结束时自动析构。

析构函数

析构函数完成对象中二叉搜索树结点的释放注意释放时采用后序释放当二叉搜索树中的结点被释放完后将对象当中指向二叉搜索树的指针及时置空即可。

void

{return;}//后序遍历析构Destroy(root-_left);Destroy(root-_right);delete

root;root

根据二叉搜索树的特性我们在二叉搜索树当中查找指定值的结点的方式如下

若树为空树则查找失败返回nullptr。

若key值小于当前结点的值则应该在该结点的左子树当中进行查找。

若key值大于当前结点的值则应该在该结点的右子树当中进行查找。

若key值等于当前结点的值则查找成功返回对应结点的地址。

非递归实现

若待插入结点的值小于根结点的值则需要将结点插入到左子树当中。

若待插入结点的值大于根结点的值则需要将结点插入到右子树当中。

若待插入结点的值等于根结点的值则插入结点失败。

如此进行下去直到找到与待插入结点的值相同的结点判定为插入失败或者最终插入到某叶子结点的左右子树当中即空树当中。

非递归实现

使用非递归方式实现二叉搜索树的插入函数时我们需要定义一个parent指针该指针用于标记待插入结点的父结点。

这样一来当我们找到待插入结点的插入位置时才能很好的将待插入结点与其父结点连接起来。

但是需要注意在连接parent和cur时需要判断应该将cur连接到parent的左边还是右边。

bool

如果_root不为nullptr那么就从根开始遍历找适合的位置Node

*parent

parent跟着cur遍历找到合适的位置充当插入的父亲节点Node

*cur

这里不知道cur最终走到了parent的左边还是右边所以还要进行判断//

keyparent-_key

递归实现二叉搜索树的插入操作也是很简单的但是要特别注意的一点就是递归插入函数的子函数接收参数root时必须采用引用接收因为只有这样我们才能将二叉树当中的各个结点连接起来。

bool

二叉搜索树的删除函数是最难实现的若是在二叉树当中没有找到待删除结点则直接返回false表示删除失败即可但若是找到了待删除结点此时就有以下三种情况

待删除结点的左子树为空待删除结点的左右子树均为空包含在内。

待删除结点的右子树为空。

待删除结点的左右子树均不为空。

下面我们分别对这三种情况进行分析处理

若待删除结点的左子树为空那么当我们在二叉搜索树当中找到该结点后只需先让其父结点指向该结点的右孩子结点然后再将该结点释放便完成了该结点的删除进行删除操作后仍保持二叉搜索树的特性。

若待删除结点的右子树为空那么当我们在二叉搜索树当中找到该结点后只需先让其父结点指向该结点的左孩子结点然后再将该结点释放便完成了该结点的删除进行删除操作后仍保持二叉搜索树的特性。

若待删除结点的左右子树均不为空那么当我们在二叉搜索树当中找到该结点后可以使用替换法进行删除。

可以将让待删除结点左子树当中值最大的结点或是待删除结点右子树当中值最小的结点代替待删除结点被删除下面都以后者为例然后将待删除结点的值改为代替其被删除的结点的值即可。

而代替待删除结点被删除的结点必然左右子树当中至少有一个为空树因此删除该结点的方法与前面说到的情况一和情况二的方法相同。

注意只能是待删除结点左子树当中值最大的结点或是待删除结点右子树当中值最小的结点代替待删除结点被删除因为只有这样才能使得进行删除操作后的二叉树仍保持二叉搜索树的特性。

非递归函数

1.如果要删除的cur左边是nullptr那么我们就进行判断判断cur在parent的左子树还是右子树//

如果是左子树那么就由parent的left指向cur的右子树如果是右子树就由parent的right指向cur的右子树if

(cur-_left

都不为nullptr,替代法用被删除的cur的左子树的最大节点右子树的最大节点替换//

*pminRight

那么左边已经是最小了所以minRight的左子树肯定为空了//

那么可能minRight还有右子树所以需要pinRight来领养if

(pminRight-_left

如果不是比如删除根节点那么就需要将pminRight-_right指向minRight-right(最小值左边一定为NULL。

不需要领养)//minRight是其父结点的右孩子pminRight-_right

minRight;}return

若树为空树则结点删除失败返回false。

若所给key值小于树根结点的值则问题变为删除左子树当中值为key的结点。

若所给key值大于树根结点的值则问题变为删除右子树当中值为key的结点。

若所给key值等于树根结点的值则根据根结点左右子树的存在情况不同进行不同的处理。

bool

root;//开始准备删除root谁上层root-_left/_right的引用if

(root-_right

maxleft-_right;}swap(root-_key,

maxleft-_key);//转换在子树去删除//这里不能传maxleftmaxleft是局部变量return

_EraseR(root-_left,

default;//指定强制生成默认构造//默认构造,构造一个空树//构造树的深拷贝BSTree(const

BSTreeK

*this;//为了支持连续赋值}//现代写法,接收一个t的拷贝,临时对象,然后进行交换BSTreeK

operator(BSTreeK

如果_root不为nullptr那么就从根开始遍历找适合的位置Node

*parent

parent跟着cur遍历找到合适的位置充当插入的父亲节点Node

*cur

这里不知道cur最终走到了parent的左边还是右边所以还要进行判断//

keyparent-_key

1.如果要删除的cur左边是nullptr那么我们就进行判断判断cur在parent的左子树还是右子树//

如果是左子树那么就由parent的left指向cur的右子树如果是右子树就由parent的right指向cur的右子树if

(cur-_left

都不为nullptr,替代法用被删除的cur的左子树的最大节点右子树的最大节点替换//

*pminRight

那么左边已经是最小了所以minRight的左子树肯定为空了//

那么可能minRight还有右子树所以需要pinRight来领养if

(pminRight-_left

如果不是比如删除根节点那么就需要将pminRight-_right指向minRight-right(最小值左边一定为NULL。

不需要领养)//minRight是其父结点的右孩子pminRight-_right

minRight;}return

Copy(root-_left);newRoot-_right

newRoot;}void

{return;}//后序遍历析构Destroy(root-_left);Destroy(root-_right);delete

root;root

root;//开始准备删除root谁上层root-_left/_right的引用if

(root-_right

maxleft-_right;}swap(root-_key,

maxleft-_key);//转换在子树去删除//这里不能传maxleftmaxleft是局部变量return

_EraseR(root-_left,

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

root-_key

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

*_root

{t.Insert(e);}t.Erase(7);t.Erase(14);t.Erase(3);t.Erase(8);t.InOrder();

}void

{t.InsertR(e);}t.EraseR(7);t.EraseR(14);t.EraseR(3);t.EraseR(8);t.EraseR(6);t.InOrder();

}void

{t1.InsertR(e);}t1.InOrder();BSTreeint

t2(t1);t2.InOrder();

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

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

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

该种方式在现实生活中非常常见

比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文**word,chinese**就构成一种键值对

再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数**单词与其出现次数就是就构成一种键值对。

**

#include

2、在则查找到的节点中水果对应的次数//BSTreeNodestring,

int*

{ret-_value;}}countTree.InOrder();

插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。

但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树

最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为LogN

最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N/2

问题如果退化成单支树二叉搜索树的性能就失去了。

那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优答案就是使用AVL树和红黑树