二叉查找树
1 / 0 / 创建于 4年前 /
HuDu 的个人博客
什么是二叉查找树
二叉查找树（BST）又名二叉查找树、二叉搜索树
- 具备什么特性呢？
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
如图示例：
如要查找为10的节点
- 从根节点开始，因为10>9，找比9大的，右子树，找到13。
- 10<13，找左子树，找到11
- 10<11，找左子树，找到10
这种方式正是二分查找的思想，查找所需的最大次数等同于二叉查找树的高度。
在插入节点的时候也是利用类似的方法，通过一层一层比较大小，找到新节点适合插入的位置。
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号