一、树

1. 概念

树（Tree）是 n（n ≥ 0）个结点的有限集。

n = 0 时称为空树。

在任意一颗非空树中：

• 有且仅有一个特定的成为根（Root）的结点；
• 当 n > 1 时，其余节点可分为 m（m > 0）个互不相交的有限集 T1、T2、.....、Tm，其中每一个集合本身又是一颗树，并且称为根的子树（SubTree）。如下图：

树和子树

：

• n > 0 时，根结点是唯一的，不可能存在多个根结点。
• m > 0时，子树的个数没有限制，但是他们一定是互不相交的。

2. 树的其他概念

• 结点拥有的子树数量称为结点的度。
• 度为 0 的结点称为叶结点（终端结点）。反之度不位 0 的称为分支结点。
• 整个树的度是树内各个结点度值最大的那个值。
• 结点的子树称为该结点的子节点（孩子结点）。
• 同一个父结点的孩子之间称为兄弟结点。
• 结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。
• 树中结点的最大层次称为树的深度（Depth）或高度。

各个概念关系如下图

概念关系

二、二叉树

1. 概念

二叉树（Binary Tree）是 n（n ≥ 0）个结点的有限集合。该集合或者为空（称为空二叉树），或者由一个根节点和两棵互不相交的，分别称为根节点的左子树和右子树的二叉树组成。如下图

二叉树

2. 特点

• 每个结点最多有两棵子树，所以二叉树中不存在大于 2 的结点。

• 左子树和右子树是有顺序的，顺序不能任意改变。

• 即使树中某个结点只有一个子树，也要区分左右。

3. 特殊二叉树

• 斜树

所有结点只有左子树的二叉树叫左斜树，反之右斜树

• 满二叉树

叶子只能出现在最下层
非叶子结点的度一定是 2
在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多
如下图：

满二叉树

• 完全二叉树

叶子结点只能出现在最下两层
最下层的叶子一定集中在左部连续位置
倒数二层，若有叶子结点，一定都在有部连续位置
如果结点度为 1，则该结点只能右左孩子，不存在只有右孩子的情况
同样结点数的二叉树，完全二叉树的深度最小
下图是层序编号

完全二叉树和非完全二叉树

4. 二叉树的性质

• 在二叉树的第 i 层上至多有 2^{i - 1} 个结点（i ≥ 1）
  第一层是根结点：2^{1 - 1} = 2 ⁰ = 1
  第二层有两个结点：2^{2 - 1} = 2 ¹ = 2
  第三层有四个结点：2^{3 - 1} = 2 ² = 4

• 深度为 k 的二叉树至多有 2^k - 1 个结点（k ≥ 1）
  如果有第一层：至多 1 = 2¹ - 1
  如果有第二层：至多 1 + 2 = 3 = 2² - 1
  如果有第三层：至多 1 + 2 + 4 = 7 = 2³ - 1

• 对任何一棵二叉树 T，如果其终端结点数（叶子结点数）为 n₀，度为 2 的结点数为 n₂，则 n₀ = n₂ + 1
  

  

• 具有 n 个结点的完全二叉树的深度为 log₂n + 1

• 如果对一棵有 n 个结点的完全二叉树（深度为 log₂n + 1）的结点按层序编号，对任意结点 i（1 ≤ i ≤ n）有：

  1. 如果 i = 1，则结点 i 是二叉树的根，无双亲；
     如果 i > 1，则其双亲是结点 i / 2;
     例如：i = 1 时是根节点。i > 1 时，i = 7，它的双亲 7 / 2 = 3；（对比下图）

  2. 如果 2i > n，则结点 i 无左孩子（结点 i 为叶子结点）；
     否则其左孩子是结点 2i；
     例如：下图 n = 10，i = 6；2 * 6 = 12 超过了 10，所以结点 6 无左孩子，它是叶子结点。
     i = 5; 2 * 5 = 10 正好是 10，所以它的左孩子是结点10；（对比下图）

  3. 如果 2i + 1 > n，则结点 i 无右孩子；
     否则其右孩子是结点 2i + 1；
     例如：i = 5；2 * 5 + 1 = 11，大于结点总数 10，所以它无右孩子。
     i = 3； 2 * 3 + 1 =7 小于 10，所以它的右孩子是结点 7。（对比下图）

5. 二叉链表存储结构

二叉树每个结点最多有两个孩子，所以链表结构为一个数据域和两个指针域，称为二叉链表

链表存储结构

Python 二叉链表的结点结构代码。

class TreeNode(object):

    def __init__(self, val, lchild=None, rchild=None):
        self.val = val
        self.lchild = lchild
        self.rchild = rchild

    def __repr__(self):
        return "{val: %s, l: %s, r: %s}" % (self.val, self.lchild, self.rchild)

存储方式如下图：

存储方式

6. Python 实现二叉树的创建和遍历

二叉树的遍历是指从根结点开始，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

其实就是在遍历过程中 print 结点值的时机。

• 创建二叉树

创建出来的就是上图的样子，“#” 井号代表这个结点的左子树或右子树为空。

class Tree(object):

    def create(self, t_list, node=None, i=0):
        if i < len(t_list):
            if t_list[i] == '#':  # '#'号表示这个子树为空
                return None
            else:
                node = TreeNode(t_list[i])
                node.lchild = self.create(t_list, node.lchild, 2 * i + 1)
                node.rchild = self.create(t_list, node.rchild, 2 * i + 2)
                return node
        return node

t = Tree()
tree = t.create(['A', 'B', 'C', 'D', '#', 'E', 'F', 'G', 'H', '#', '#', '#', 'I'])

• 前序遍历

先访问根结点，然后前序遍历左子树，在前序遍历右子树。如下图：

前序遍历

class Tree(object):

    def create(self, t_list, node=None, i=0):
        if i < len(t_list):
            if t_list[i] == '#':  # '#'号表示这个子树为空
                return None
            else:
                node = TreeNode(t_list[i])
                node.lchild = self.create(t_list, node.lchild, 2 * i + 1)
                node.rchild = self.create(t_list, node.rchild, 2 * i + 2)
                return node
        return node

    # 前序遍历
    def before_traversal(self, tree):
        if tree is None:
            return None
        print tree.val
        self.before_traversal(tree.lchild)
        self.before_traversal(tree.rchild)

t = Tree()
tree = t.create(['A', 'B', 'C', 'D', '#', 'E', 'F', 'G', 'H', '#', '#', '#', 'I'])
t.before_traversal(tree)

# 结果如下
# A
# B
# D
# G
# H
# C
# E
# I
# F

• 中序遍历

从根结点开始（这里不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如下图：

中序遍历

class Tree(object):

    def create(self, t_list, node=None, i=0):
        if i < len(t_list):
            if t_list[i] == '#':
                return None
            else:
                node = TreeNode(t_list[i])
                node.lchild = self.create(t_list, node.lchild, 2 * i + 1)
                node.rchild = self.create(t_list, node.rchild, 2 * i + 2)
                return node
        return node

    # 中序遍历
    def center_traversal(self, tree):
        if tree is None:
            return None
        self.center_traversal(tree.lchild)
        print tree.val
        self.center_traversal(tree.rchild)

t = Tree()
tree = t.create(['A', 'B', 'C', 'D', '#', 'E', 'F', 'G', 'H', '#', '#', '#', 'I'])
t.center_traversal(tree)

# 结果如下
# G
# D
# H
# B
# A
# E
# I
# C
# F

• 后序遍历

从左到右先叶子后结点的方式遍历访问左子树，最后是访问根结点。如下图：

后序遍历

class Tree(object):

    def create(self, t_list, node=None, i=0):
        if i < len(t_list):
            if t_list[i] == '#':
                return None
            else:
                node = TreeNode(t_list[i])
                node.lchild = self.create(t_list, node.lchild, 2 * i + 1)
                node.rchild = self.create(t_list, node.rchild, 2 * i + 2)
                return node
        return node

    # 后序遍历
    def after_traversal(self, tree):
        if tree is None:
            return None
        self.after_traversal(tree.lchild)
        self.after_traversal(tree.rchild)
        print tree.val

t = Tree()
tree = t.create(['A', 'B', 'C', 'D', '#', 'E', 'F', 'G', 'H', '#', '#', '#', 'I'])
t.after_traversal(tree)

# 结果如下
# G
# H
# D
# B
# I
# E
# F
# C
# A

• 层序遍历

从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按照从左到右的顺序对结点逐个访问。
层序遍历就是创建树时候传的那个 - -！
如下图：

层序遍历

三、二叉排序树（二叉查找树）

1. 性质

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

• 它的左，右子树也分别为二叉排序树；

2. 二叉排序树的查找

class TreeNode(object):

    def __init__(self, val, lchild=None, rchild=None):
        self.val = val
        self.lchild = lchild
        self.rchild = rchild
        self.ltag = None
        self.rtag = None

    def __repr__(self):
        return "{val: %s, l: %s, r: %s, ltag: %s, rtag: %s}" % (self.val, self.lchild, self.rchild, self.ltag, self.rtag)


class Tree(object):

    def __init__(self, root=None):
        self.root = root
        self.search_node_seat = None
        self.pre = TreeNode(-1)
        self.thread = 1

    def create(self, t_list, node=None, i=0):
        if i < len(t_list):
            if t_list[i] == '#':
                return None
            else:
                node = TreeNode(t_list[i])
                node.lchild = self.create(t_list, node.lchild, 2 * i + 1)
                node.rchild = self.create(t_list, node.rchild, 2 * i + 2)
                return node
        return node

    def search(self, tree, key, last_node=None):
        # 是否为叶子结点
        if not tree:
            # 如果没有搜索到返回最后一个节点
            self.search_node_seat = last_node
            return False
        elif key == tree.val:
            # p 是搜索到结点后，结点的位置
            self.search_node_seat = tree
            return True
        elif key < tree.val:
            return self.search(tree.lchild, key, tree)
        else:
            return self.search(tree.rchild, key, tree)


t = Tree()
tree = t.create([62, 58, 88, 47, '#', 73, 99, 35, 51, '#', '#', '#', '#', 93, '#', '#', 37])
print t.search(tree, 51)
print t.search_node_seat

说明一下判断
第一个判断是判断结点是不是最后一个。最后一个 tree 肯定是 none。
第二个判断是判断要搜索的 key 是不是当前结点的 val。
第三个判断是判断 key 是在结点的左边还是右边。如果 key 大于当前节点 val 则继续搜索右边的子树。反之搜索左边的子树。
search_node_seat 在下面的插入中会用到。

3. 二叉排序树的插入

还需要搜索中的那些函数和类。在 Tree 类中添加下面方法。

    def insert(self, tree, key):
        if self.search(tree, key) is True:
            return False

        new_node = TreeNode(None)
        new_node.val = key
        if self.search_node_seat is None:
            tree = new_node
        elif key < self.search_node_seat.val:
            self.search_node_seat.lchild = new_node
        else:
            self.search_node_seat.rchild = new_node
        return Tre


tree = Tree().TreeNode(62)
tree_list = [88, 58, 47, 35, 73, 51, 99, 37, 93]
for i in tree_list:
    t.insert(tree, i)
print tree

过程：
先搜索一下树中是否存在结点。如果存在直接退出。

创建一个新的结点，把要插入的值赋值给新结点。

然后获取搜索时候的哪个 search_node_seat 变量。这个变量有两个情况。
① 搜索到结点，这个变量就是搜索到的哪个结点的 Node 对象。
② 没有搜索到想要的值，那么这个变量就是最后的哪个结点对象。

最后比较一下搜索后的最后一个结点的 val 比要插入的大还是小，大就放右边，小就放左边。

WX20200210-101811@2x.png

4. 二叉搜索树删除

1. 第一种情况

要删除的结点只有左子树或右子树，这种情况只需要将被删除结点的子树与被删除结点的父结点重新连接即可。如下图

image.png

2. 第二种情况

要删除的结点有两个子树。
如图中 58 结点只有一个左子树，可以将 47 的左子树 35 直接与 58 结点相连。
如果 58 结点有右子树，那么 47 结点的右子树需要重新插入树。重新插入会大幅度改变树的结构，有可能会增加高度等。

解决办法：可以尝试从 47 结点的左子树和右子树中筛选出一个结点来代替 47 结点。
如何筛选：找出和 47 最接近的两个即可。可以看到 37 结点和 48 结点是最接近的。
可以如下图

image.png

下面代码获取的是比 47 结点小的结点，所以先获取 47 结点左子树，然后获取 47 结点左子树的右子树，一直向右到底。

    def delete(self, tree, node):
        self.search(tree, node)
        # 查找到要被删除的结点
        delete_node = self.search_node_seat
        # 判断结点左右树 是否只存在一个，如果存在一个，被删除的结点子树直接和父树连接
        if delete_node.rchild is None:
            delete_node = delete_node.lchild
        elif delete_node.lchild is None:
            delete_node = delete_node.rchild
        else:
            # 左右树都存在
            s = delete_node.lchild
            q = delete_node
            # 查找比被删除结点小且最接近的结点，用来替换被删除结点
            # 比他小的是左子树，更近进的是左子树的右子树。所以是左走然后右走到头
            while s.rchild:
                q = s
                s = s.rchild
            delete_node.val = s.val
            if q != delete_node:
                q.rchild = s.lchild
            else:
                q.lchild = s.lchild
        return tree

t = Tree()
tree = TreeNode(62)
i = [88, 58, 47, 35, 73, 51, 99, 37, 93, 29, 36, 49, 56, 48, 50]

for a in i:
    t.insert(tree, a)
# print tree
t.delete(tree, 47)

三个变量变化过程如下图：
第一张图：因为查找比被删除结点 47 小且最接近的结点，用来替换被删除结点。所以 while 从 35 结点的右子树开始循环。
第二张图：从 35 结点右子树开始一直向右到底，拿到最接近 47 结点的结点。此时就是 37 结点。然后用 37 结点的值替换 47 节点的值。
第三张图：35 结点连接 37 节点的左子树。

为什么要判断 q != delete_node ：

• 当 q != delete_node 时：说明 s 变量肯定在 35 结点的右子树里面。35 结点的右子树里面的结点的值肯定比 35 大，所以 q.rchild 去连接其他节点。
• 当 q == delete_node 时：如果当 35 结点没有右子树。那么变量 q、delete_node 都会指向 47 结点。s 变量会指向 35 结点。35 结点就是最佳替换选择。所以 47 和 35 替换以后需要重新连接 35 结点的左子树。

判断里面为什么都是连接左子树。因为我要找到 35 结点右子树最后一个结点，这个结点肯定没有右子树了，存在子树也只会是左子树。因为如果有右子树，那说明它不是最右面的最后一个结点。

删除流程