递归版本

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

为啥又被称作二叉排序树呢

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

比较简单这里就直接放代码

public:BinarySeaTree_node(const

val):

_val(val),_left(nullptr),_right(nullptr){}K

_val;BST_node*

nullptr)return;Re_Print(node-_left);cout

node-_val

但这些思路只是大概方向其中藏着许多的坑点诺接下来我来带大家对这些易错点进行分析。

parent

val){//首先寻找到指定值,并且记录到parentBST_node*

parent

现在又进入一种特殊情况,1.max_parent就没进入循环2.进入了循环if

(max_parent

maxnode-_left;}else{max_parent-_right

maxnode-_left;}//

node-_left;}else{//处理左右都有孩子的目标//

max_node

完成循环后max_node最多有左孩子然后数据交换我们以目标左侧树为起点//

node-_val);return

先处理左右孩子Distroy_Re(node-_left);Distroy_Re(node-_right);delete

node;node

BST_node(root-_val);new_node-_left

copy(root-_left);new_node-_right

new_node;}

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

给一个单词word判断该单词是否拼写正确具体方式如下以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。

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

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

chinese就构成一种键值对

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

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

最坏情况N

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

那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优那么我们后续章节学习的AVL树和红黑树就可以上场了。

五代码汇总

public:BinarySeaTree_node(const

val):

_val(val),_left(nullptr),_right(nullptr){}K

_val;BST_node*

2.使用default关键字强制生成默认构造BSTree(){}//

BSTree()

BST_node(root-_val);new_node-_left

copy(root-_left);new_node-_right

new_node;}bool

val){//首先寻找到指定值,并且记录到parentBST_node*

parent

现在又进入一种特殊情况,1.max_parent就没进入循环2.进入了循环if

(max_parent

maxnode-_left;}else{max_parent-_right

maxnode-_left;}//

1;}~BSTree(){Distroy_Re(root);root

node,

nullptr)return;Re_Print_table(node-_left);cout

node-_val

;Re_Print_table(node-_right);}BST_node*

node,

node-_left;}else{//处理左右都有孩子的目标//

max_node

完成循环后max_node最多有左孩子然后数据交换我们以目标左侧树为起点//

node-_val);return

先处理左右孩子Distroy_Re(node-_left);Distroy_Re(node-_right);delete

node;node

本小节就到这里了感谢小伙伴的浏览如果有什么建议欢迎在评论区评论如果给小伙伴带来一些收获请留下你的小赞你的点赞和关注将会成为博主创作的动力