搞定算法与数据结构(04):二叉树的遍历、应用及复杂度分析

作者: 王炳明 分类: 算法与数据结构 发布时间: 2021-10-04 10:42 热度:939

查看完整目录 –>《搞定算法与数据结构


二叉树的概念

要说二叉树(Binary Tree)的定义,还不如来一张二叉树的图来得通俗易懂

搞定算法与数据结构(04):二叉树的遍历、应用及复杂度分析

二叉树节点的一些概念:

  • 根节点:没有父节点的节点叫做根节点,一棵树中只有一个根节点
  • 兄弟节点:拥有同一个父节点的两节点,互为兄弟节点
  • 叶子节点:没有子节点的节点叫做叶子节点

二叉树另外一些容易混淆的概念

  • 高度:距离最高层叶子节点的边数
  • 深度:距离根节点的边数
  • 层数:节点的深度+1
  • 树的高度:根节点的高度

搞定算法与数据结构(04):二叉树的遍历、应用及复杂度分析

二叉树的一些分类

  • 普通二叉树
  • 二叉搜索树:若二叉树每个节点的左子节点都比自己小,而右节点都比自己大,那它就是一个二叉搜索树。
  • 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。
  • 完全二叉树:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

搞定算法与数据结构(04):二叉树的遍历、应用及复杂度分析

实现二叉树深度遍历

二叉树的深度遍历有三种方式:

  • 先序遍历:指最先遍历节点本身,再遍历节点的左子树,最后遍历右子树的遍历方法;
  • 中序遍历:指最先遍历节点的左子树,再遍历节点本身,最后遍历右子树的遍历方法,对于二叉搜索树,中序遍历可以对二叉树进行排序,时间复杂度为 O(n),非常高效。
  • 后序遍历:指最先遍历节点的左子树,再遍历右子树,最后遍历节点本身的一种遍历方法。

最快的方式是使用递归思想,以中序遍历为例:

  • 递推公式:F(node) = F(node.left) + node.value + F(node.right)
  • 终止条件:node None

使用 Python 来实现的话,几行代码就能够实现。

但在实现之前,先要构造一个二叉树的数据结构

class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

然后往里塞入数据

a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
d = TreeNode(4)
e = TreeNode(5)
f = TreeNode(6)
g = TreeNode(7)

a.left = b
a.right = c
b.left = d
b.right = e
c.left = f
c.right = g

用一张图来表示的话,就是这样

搞定算法与数据结构(04):二叉树的遍历、应用及复杂度分析

那么中序遍历的代码该怎么写呢?呐,这这么简单

# 中序打印二叉树(递归)
def in_order_traverse(node):
    if node is None:
        return None
    in_order_traverse(node.left)
    print(node.val)
    in_order_traverse(node.right)

相对应的先序遍历和后序遍历,只是调整一下顺序而已

# 先序打印二叉树(递归)
def pre_order_traverse(node):
    if not node:
        return None
    print(node.val)
    pre_order_traverse(node.left)
    pre_order_traverse(node.right)

# 后序打印二叉树(递归)
def post_order_traverse(node):
    if node is None:
        return None
    post_order_traverse(node.left)
    post_order_traverse(node.right)
    print(node.val)

实现二叉树广度遍历

按层遍历二叉树,这实际上就是广度优先算法,遵循一个先进先出的规律,因此不要使用递归和栈了,最好改用队列来实现。

from queue import Queue

# 按层打印二叉树(递归)
def layer_order_traverse(node):
    if node is None:
        return None

    queue = Queue()
    queue.put(node)

    while True:
        n = queue.get()
        if not n:
            break

        print(n.val)
        if n.left is not None:
            queue.put(n.left)

        if node.right is not None:
            queue.put(n.right)

二叉搜索树的操作

无论哪一种数据结构,都是为了存储数据,方便用户或程序操作,操作的方式主要有:

  • 查找某个值
  • 插入某个值
  • 删除某个值

而这些操作的完成,都要基于一个特殊的二叉树类型:二叉搜索树

二叉搜索树,顾名思义是专为搜索而优化的一种特殊结构的树。

二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值。

搞定算法与数据结构(04):二叉树的遍历、应用及复杂度分析

查找某值

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

另外搜索二叉树,还有其他的查找玩法:

  • 查找最大节点:直接向右遍历到底
  • 查找最小节点:直接向左遍历到底
  • 找出前驱节点
  • 找出后继节点

其中前驱和后继节点需要说明一下:

  • 前驱节点:比当前节点小的一堆节点里,值最大的那个节点
  • 后继节点:比当前节点大的一堆节点里,值最小的那个节点

那么如何找到这些节点呢?

前驱节点

  1. 若一个节点,有左子树,那么该节点的前驱节点是左子树中向右遍历到底,值最大的那个节点。比如 5 的前驱节点是 4。
  2. 若一个节点,没有左子树,并且它是父节点的左节点,那么前驱节点,需要沿着父节点往上寻找。比如 2 的前驱节点是 1。
  3. 若一个节点,没有左子树,并且它是父节点的右节点,那么前驱节点,就是其父节点。比如 4 的前驱节点是 3

后继节点

  1. 若一个节点,有右子树,那么该节点的后继节点是右子树中向左遍历到底,值最小的那个节点。比如 7 的后继节点是 8 。
  2. 若一个节点,没有右子树,并且它是父节点的左节点,那么后继节点,就是其父节点。比如 8 的后继节点是 9。
  3. 若一个节点,没有右子树,并且它是父节点的右节点,那么后继节点,需要沿着父节点往上寻找。比如 4 的后继节点是 5。

搞定算法与数据结构(04):二叉树的遍历、应用及复杂度分析

插入某值

新插入的数据一般都是在叶子节点上,所以我们只需要从根节点开始,依次比较要插入的数据和节点的大小关系。

如果要插入的数据比节点的数据大,并且节点的右子树为空,就将新数据直接插到右子节点的位置;如果不为空,就再递归遍历右子树,查找插入位置。同理,如果要插入的数据比节点数值小,并且节点的左子树为空,就将新数据插入到左子节点的位置;如果不为空,就再递归遍历左子树,查找插入位置。

删除某值

二叉查找树的查找、插入操作都比较简单易懂,但是它的删除操作就比较复杂了 。针对要删除节点的子节点个数的不同,我们需要分三种情况来处理。

第一种情况是,如果要删除的节点没有子节点,我们只需要直接将父节点中,指向要删除节点的指针置为 null。比如图中的删除节点 55。

第二种情况是,如果要删除的节点只有一个子节点(只有左子节点或者右子节点),我们只需要更新父节点中,指向要删除节点的指针,让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。

第三种情况是,如果要删除的节点有两个子节点,这就比较复杂了。我们需要找到这个节点的右子树中的最小节点,把它替换到要删除的节点上。然后再删除掉这个最小节点,因为最小节点肯定没有左子节点(如果有左子结点,那就不是最小节点了),所以,我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。

搞定算法与数据结构(04):二叉树的遍历、应用及复杂度分析

二叉搜索树的应用

上面的例子中,二叉树节点存储的都是数值,而实际上,节点存储的可能是一个对象,而节点之间比较的依据是对象的某个字段。

还有一个问题就是,若往一个搜索二叉树中插入一个数值,并且该值已经在二叉树中已经存在,那该怎么办呢?

此时,一般有两种方案:

方案一:节点存储不再是单一的数据,而是一个存储多个数据的数据结构,比如链表、数组。

方案二:节点仍然只存一个数据,若碰到一个节点与插入的数据相等,就当做大于处理。

搞定算法与数据结构(04):二叉树的遍历、应用及复杂度分析

二叉搜索树的复杂度分析

二叉搜索树,其实也有多种形态:

  • 极度不平衡:退化成链表,如下图中第一个示例,时间复杂度为 O(n)
  • 普通二叉搜索树:如下图中第二个示例,时间复杂度为 O(L),L 为树的层数
  • 完全二叉搜索树:如下图中第三个示例,时间复杂度为 O(L),L 为树的层数

搞定算法与数据结构(04):二叉树的遍历、应用及复杂度分析

由于普通二叉树,不太好根据节点数 n 计算出 树的高度,因此这边以完全二叉树为例,进行时间复杂度的计算

假设完全二叉树的节点数为 n,树的层数为 L,高度为 H,那么

L = H + 1
n >= 1 + 2^1 + 2^2 + ... + 2^(L-1) + 1
n <= 1 + 2^1 + 2^2 + ... + 2^L

根据等比数列的求和公式

img

求得 log_2^{n+1} <= L <= log_2^n + 1

因此平衡二叉搜索树的时间复杂度为 O(L) = O(logn)

二叉树对比散列表

  1. 散列表虽然查找的平均时间复杂度为 O(1),但这仅仅是在没有散列冲突的情况下才能有如此效率,因此并不稳定。而平衡二叉搜索树的查找效率是非常稳定的,为 O(nlogn)。由于散列冲突的存在,散列表查询的常数不一定会比 O(logn) 快,并且还要加上散列函数的计算耗时。
  2. 散列表数据的存储是无序的,如果要排序的话,二叉树的效率非常高,为 O(n)
  3. 散列表的设计比较复杂,需要考虑的东西比较高,比如散列函数如何设计,散列冲突如何解决,扩容、缩容等等

文章有帮助,请作者喝杯咖啡?

发表评论