程序员二进制排序树的C ++实现

>>>>程序员教程

>>>>程序员培训视频

>>>>程序员考试教科书

1. 二进制排序树的定义: 二进制排序树是空树或满足以下属性的二进制树:

①如果其左子树不为空，则左子树上所有节点的值小于根节点的值;

②如果右子树不为空，则右子树上所有节点的值大于根节点的值；

③左右子树都是二叉排序树.

2. 二进制排序树的特征

根据BST的性质:

[1]在二元排序树中的任何节点x上，左（右）子树中任何节点y（如果有）的关键字必须小于（大于）x的关键字.

[2]在二进制排序树中，每个节点键都是唯一的. 注意: 在实际应用中，不能保证要搜索的数据集中每个元素的关键字彼此不同，因此二进制排序树的定义中BST属性[1]中的“小于”可以更改为“小于或等于”，或者在BST属性[2]中，将“大于”更改为“大于或等于”，甚至可以同时修改两个属性.

[3]以中间顺序遍历树获得的中间顺序是递增顺序.

3. 在二叉排序树上搜索时的平均搜索长度与二叉树的形状有关:

①在最坏的情况下，通过顺序插入一个有序列表的n个节点来生成二进制排序树，然后将所得的二进制排序树转换为深度为n的单个分支树，其平均搜索长度与在单链列表上的顺序搜索，该列表也是（n +1）/ 2.

②在最佳情况下，在生成二进制排序树的过程中，树的形状相对对称，最终结果是二进制排序树，其形式类似于二进制搜索的决策树. 目前，其平均搜索长度约为lgn.

③插入，删除和搜索算法的时间复杂度均为O.

4. 二进制排序树和二进制搜索的比较.

就维护表的顺序而言，二进制排序树不需要移动节点二叉排序树的实现，只需修改指针即可完成插入和删除操作，平均执行时间为O（lgn），这样更有效. 二进制搜索中涉及的有序表是一个向量. 如果有插入和删除节点的操作二叉排序树的实现，则维护表顺序的成本为O（n）. 当有序表是静态查找表时，应将向量用作其存储结构，并使用二进制搜索来实现其搜索操作. 如果动态查找表位于有序表中，则应选择二进制排序树作为其存储结构.

有关更多信息，请访问西塞软件考试学院.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-199144-1.html