何谓二叉排序树_二叉排序树时间复杂度

何谓二叉排序树_二叉排序树时间复杂度程序员专用复习资料:二叉排序树定义与特点  2013年上半年软考指定教材2013下半年软考培训:在线辅导 面授班23、二叉排序树(BST, Binary SortTree) 的C++实现二叉排序树(Binary Sort Tree)

程序员专用复习资料:二叉排序树定义与特点     2013年上半年软考指定教材   2013下半年软考培训:在线辅导 面授班   23、二叉排序树(BST, Binary SortTree) 的C++实现   二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。   (1)二叉排序树定义:二叉排序树或者是空树,或者是满足如下性质的二叉树:   ①若它的左子树非空,则左子树上所有结点的值均小于根结点的值;   ②若它的右子树非空,则右子树上所有结点的值均大于根结点的值;   ③左、右子树本身又各是一棵二叉排序树。   上述性质简称二叉排序树性质(BST性质),故二叉排序树实际上是满足BST性质的二叉树。   (2)二叉排序树的特点   由BST性质可得:   [1]二叉排序树中任一结点x,其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。   [2]二叉排序树中,各结点关键字是惟一的。 注意:实际应用中,不能保证被查找的数据集中各素的关键字互不相同,所以可将二叉排序树定义中BST性质[1]里的“小于”改为“小于等于”,或将BST性质[2]里的“大于”改为“大于等于”,甚至可同时修改这两个性质。   [3]按中序遍历该树所得到的中序序列是一个递增有序序列。   返回目录:软考程序员专用复习资料   编辑推荐:2013年软考程序员理论知识汇总   2013年软考程序员常考知识点锦集

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/49304.html

(0)
上一篇 2024年 9月 3日 下午9:08
下一篇 2024年 9月 3日

相关推荐

关注微信