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

---

二叉树的概念

要说二叉树（Binary Tree）的定义，还不如来一张二叉树的图来得通俗易懂

二叉树节点的一些概念：

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

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

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

二叉树的一些分类

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

实现二叉树深度遍历

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

• 先序遍历：指最先遍历节点本身，再遍历节点的左子树，最后遍历右子树的遍历方法；
• 中序遍历：指最先遍历节点的左子树，再遍历节点本身，最后遍历右子树的遍历方法，对于二叉搜索树，中序遍历可以对二叉树进行排序，时间复杂度为 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

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

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

# 中序打印二叉树（递归）
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)

二叉搜索树的操作

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

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

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

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

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

查找某值

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

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

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

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

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

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

前驱节点

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

后继节点

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

插入某值

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

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

删除某值

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

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

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

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

二叉搜索树的应用

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

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

此时，一般有两种方案：

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

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

二叉搜索树的复杂度分析

二叉搜索树，其实也有多种形态：

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

由于普通二叉树，不太好根据节点数 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

根据等比数列的求和公式

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

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

二叉树对比散列表

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