数据结构与算法--二叉树

2020-12-28  本文已影响0人  zhujunhua

关于“树”,还有三个比较相似的概念:高度(Height)、深度(Depth)、层(Level)。它们的定义是这样的:


树的高度/深度/层.png
树的高度/深度/层.png

“高度”这个概念,其实就是从下往上度量,比如我们要度量第 10 层楼的高度、第 13 层楼的高度,起点都是地面。所以,树这种数据结构的高度也是一样,从最底层开始计数,并且计数的起点是 0。
“深度”这个概念在生活中是从上往下度量的,比如水中鱼的深度,是从水平面开始度量的。所以,树这种数据结构的深度也是类似的,从根结点开始度量,并且计数起点也是 0。
“层数”跟深度的计算类似,不过,计数起点是 1,也就是说根节点位于第 1 层。

二叉树(Binary Tree)

二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子节点右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只有左子节点,有的节点只有右子节点。

叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点,这种二叉树就叫做满二叉树
叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大,这种二叉树叫做完全二叉树。 (在满二叉树的基础上, 移除最后一层的右侧n个节点, 剩下的就是完全二叉树)

二叉树的存储

想要存储一棵二叉树,我们有两种方法,一种是基于指针或者引用的二叉链式存储法,一种是基于数组的顺序存储法

二叉树的遍历

经典的遍历方法: 前序遍历中序遍历后序遍历
其中,前、中、后序,表示的是节点与它的左右子树节点遍历打印的先后顺序。

二叉树的遍历.png
每个节点最多会被访问两次,所以遍历操作的时间复杂度,跟节点的个数 n 成正比,也就是说二叉树遍历的时间复杂度是 O(n)。

二叉查找树(Binary Search Tree)

二叉查找树最大的特点就是,支持动态数据集合的快速插入、删除、查找操作。
二叉查找树是二叉树中最常用的一种类型,也叫二叉搜索树。顾名思义,二叉查找树是为了实现快速查找而生的。不过,它不仅仅支持快速查找一个数据,还支持快速插入、删除一个数据。
二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值。

1. 二叉查找树的查找操作

我们先取根节点,如果它等于我们要查找的数据,那就返回。如果要查找的数据比根节点的值小,那就在左子树中递归查找;如果要查找的数据比根节点的值大,那就在右子树中递归查找。

2. 二叉查找树的插入操作

二叉查找树的插入过程有点类似查找操作。新插入的数据一般都是在叶子节点上,所以我们只需要从根节点开始,依次比较要插入的数据和节点的大小关系。
如果要插入的数据比节点的数据大,并且节点的右子树为空,就将新数据直接插到右子节点的位置;如果不为空,就再递归遍历右子树,查找插入位置。同理,如果要插入的数据比节点数值小,并且节点的左子树为空,就将新数据插入到左子节点的位置;如果不为空,就再递归遍历左子树,查找插入位置。

3. 二叉查找树的删除操作

针对要删除节点的子节点个数的不同,我们需要分三种情况来处理。

4. 二叉查找树的其他操作

除了插入、删除、查找操作之外,二叉查找树中还可以支持快速地查找最大节点和最小节点、前驱节点和后继节点。
二叉查找树除了支持上面几个操作之外,还有一个重要的特性,就是中序遍历二叉查找树,可以输出有序的数据序列,时间复杂度是 O(n),非常高效。因此,二叉查找树也叫作二叉排序树

支持重复数据的二叉查找树

很多时候,在实际的软件开发中,我们在二叉查找树中存储的,是一个包含很多字段的对象。我们利用对象的某个字段作为键值(key)来构建二叉查找树。我们把对象中的其他字段叫作卫星数据。

重复数据的二叉树存储:

二叉查找树的时间复杂度分析

在二叉查找树中,查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比(O(height))。两个极端情况的时间复杂度分别是 O(n) 和 O(logn),分别对应二叉树退化成链表的情况和完全二叉树。
为了避免时间复杂度的退化,针对二叉查找树,我们又设计了一种更加复杂的树,平衡二叉查找树,时间复杂度可以做到稳定的 O(logn),后续补充。

二叉查找树 对于 散列表 的优势

参考:
极客时间--数据结构与算法之美--23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
极客时间--数据结构与算法之美--24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?

上一篇下一篇

猜你喜欢

热点阅读