二叉查找树
概念
二叉查找树，又称为二叉排序树、二叉搜索树。
二叉查找树有以下几个特性
若左子树不空，则左子树上所有结点的值均小于它的根结点的值
若右子树不空，则右子树上所有结点的值均大于或...
二叉查找树
概念
二叉查找树，又称为二叉排序树、二叉搜索树。
二叉查找树有以下几个特性
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
- 左右子树也分别为二叉查找树
操作
查找
根据二叉查找树的特性，我们可以知道在查找某个元素时
- 先找到根节点，如果根节点为空，直接返回
- 先比较它与根节点，相等就返回
- 如果它比根节点小，就从根的左子树里进行递归查找
- 如果它比根节点大，就从根的右子树里进行递归查找
可以看出来这本质就是一个二分查找，查找性能决定于二叉树的高度
插入
在二叉查找树中插入元素，主要分两步：查找，插入
- 先查找有没有这个元素，有就不用插入，直接返回
- 没有就插入到之前查到好的位置
删除
和插入相同，也是主要分两步：查找，删除
- 如果要删除的节点正好是叶子节点，就直接删除
- 如果该节点只有左孩子或者右孩子，直接把这个孩子已放到要删除的位置就好了
- 如果两个孩子，就需要选择一个合适的孩子节点作为新的根节点，该节点称为继承节点
选择新的根节点有两种方式
- 右子树里找到最左边的节点
- 左子树里找到最右边的节点
面试题
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向
只要将这棵树中序遍历后就是将二叉树节点排序，遍历到一个节点就将该节点的左指针指向上一个遍历的节点，并将上一个遍历的节点的右指针指向现在正在遍历的节点，那么当我们遍历完整棵树后，我们的双向链表也改好
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：mysql事务隔离级别详解和实战 下一篇：gevent：异步理论与实战[转]
