懵逼二叉树
懵逼树上懵逼果,
懵逼树下你和我。
一人一颗懵逼果,
一起学二分搜索。
数组、栈、队列、链表都是线性结构,树则是另外一种极其重要的数据结构。
树的种类有很多种,我们先从简单的 二分搜索树 开始树的学习。
二分查找法定义
是一种在有序数组中查找某一特定元素的搜索算法。 搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束; 如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。 如果在某一步骤数组为空,则代表找不到。 这种搜索算法每一次比较都使搜索范围缩小一半。
动画演示
动画说明
注意:二分查找的前提是数列必须是有序的。
二叉查找树也可叫做二分查找树。 它不仅可以查找数据,还可以高效地插入、删除数据。 特点:每个节点的key值大于左子节点,小于右子节点。 注意它不一定是完全的二叉树。
class Node {
E e;
Node left; // 左孩子
Node right; // 右孩子
}
二叉查找树有两个属性:
通过这两个属性,可以推断出以下结论:
通过以下方式的进行添加元素与删除元素的操作,可以保留二叉查找树的完整性。
我们通过两组添加元素,三组删除元素,一组查找元素的操作来理解二叉查找树的属性性质。
核心思想:从根节点开始找插入的位置,满足二叉搜索树的特性,比左子节点大,比右子节点小.
步骤:
null
那么就插入到这个节点。null
,那么和当前节点比较,如果小于节点就往左子树放,如果大于节点就往右子树放。添加元素 1
添加元素 4
步骤:
删除元素 28
删除元素 8
删除元素 9
查找元素 12
可以看出,使用二叉查找树可以实现高效搜索。
但是如果树接近形成直线,那么搜索效率将极其差,变成了线性搜索。
因此二叉查找树就需要进行改进为平衡二叉树,比较常见的 Balanced Binary Tree有:
遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。二叉树的遍历有三种:
§§