数据结构——树与二叉树

树与树算法

树(tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。 

它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶是朝下的。它具有以下的特点：

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树。

 树的术语：

（1）节点（node）：树的节点由数据元素及其若干分支组成。

（2）树和子树：以根节点为根的树为全树（或树），以其他节点作为根节点的树为子树。

（3）节点的度（degree of node）：一个节点含有的子树的个数称为该节点的度。

（4）树的度：一棵树中，最大的节点的度称为树的度。

（5）叶子节点：度为0的节点就是叶子节点，它位于树最深层，并且树只要非空，就一定存在叶子节点。

（6）孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。

（7）双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。

（8）兄弟节点：具有相同父节点的节点互称为兄弟节点。

（9）节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。

（10）树的高度或深度：树中节点的最大层次。

如下图所示：

 二叉树

每个节点最多含有两个子树的树称为二叉树。如下图中的 a 就是一个二叉树：

二叉树的性质：

二叉树中，第层最多有个结点。  

如果二叉树的深度为 ，那么此二叉树最多有 个结点。  

二叉树中，终端结点数（叶子结点数）为 ，度为 2 的结点数为 ，则 。

二叉树的分类：

满二叉树：如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。如下图：

完全二叉树：如果二叉树中除去最后一层节点为满二叉树，且最后一层的节点依次从左到右分布， 则此二叉树被称为完全二叉树。如下图中a所示：

树的 存储与表示：

顺序存储：将数据结构存储在固定的数组中，然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。

二叉树节点的结构如下图：

 

接下来，我们用代码实现二叉树的封装与创建添加，代码如下：

class Node(object):
    """
    二叉树节点对象封装的类
    """
    def __init__(self, element):
        self.element = element
        self.lchild = None
        self.rchild = None

    def __str__(self):
        return self.element

    def __repr__(self):
        return  self.element

class Tree(object):
    """二叉树的封装"""
    def __init__(self, root=None):
        self.root = root

    def add(self, item):
        """往二叉树里面添加元素"""
        node = Node(item)
        # 如果树是空的,则对根节点赋值
        if not self.root:
            self.root = node
        else:
            # 先找树的根节点, 存储到变量queue中
            queue = []
            queue.append(self.root)
            while queue:
                item = queue.pop(0)
                if not item.lchild:
                    item.lchild = node
                    return
                elif not item.rchild:
                    item.rchild = node
                    return
                else:
                    queue.append(item.lchild)
                    queue.append(item.rchild)

这样，我们就封装好了一个二叉树。

---

二叉树的遍历

遍历是指对树中所有节点的信息的访问，即依次对树中每个节点访问一次且仅访问一次，我们把这种对所有节点的访问称为遍历(traversal) 。

二叉树的遍历模式分为深度优先遍历和广度优先遍历，广度优先遍历也就是层次遍历，深度优先遍历又分为先序遍历、中序遍历和后序遍历，具体如下图所示：

 广度优先遍历

广度优先遍历即层次遍历，如下图所示：

对上图中的二叉树进行层次遍历后，顺序为 1 2 3 4 5 6 7

那么我们用队列的方式去实现二叉树的层次遍历，还是在之前的Tree 类里面定义层次遍历的函数，代码如下：

    def breadth_travel(self):
        """利用队列实现树的层次遍历"""
        if not self.root:
            return
        else:
            queue = []
            queue.append(self.root)
            while queue:
                node = queue.pop(0)
                print(node.element, end='  ')
                if node.lchild:
                    queue.append(node.lchild)
                if node.rchild:
                    queue.append(node.rchild)
            print()

我们对其进行测试，测试代码如下：

if __name__ == '__main__':
    tree = Tree()
    for item in range(7):
        tree.add(item + 1)
    print("创建树成功")
    print("层次遍历")
    tree.breadth_travel()

经测试，输出结果如下：

可见和我们之前进行层次遍历之后的顺序是一样的。

 深度优先遍历

 

先序遍历：（根左右）每遇到一个节点，先访问，然后再遍历其左右子树。

对上图进行先序遍历后的顺序为：1 2 4 5 3 6 7  

下面我们用递归方式实现先序遍历， 仍然是在之前的Tree 类里面定义先序遍历的函数，代码如下：

    def preorder(self, root):
        """先序遍历: 根左右"""
        if root == None:
            return
        print(root.element, end='  ')
        self.preorder(root.lchild)
        self.preorder(root.rchild)

对其进行测试，测试代码如下：

if __name__ == '__main__':
    tree = Tree()
    for item in range(7):
        tree.add(item + 1)
    print("创建树成功")
    print("先序遍历")
    root = tree.root
    tree.preorder(root)

经测试，输出结果如下，也是和我们之前的顺序一致：

中序遍历：（左根右）第一次经过时不访问根节点，等遍历完左子树之后再访问，然后遍历右子树。

对上图进行中序遍历后的顺序为：4 2 5 1 6 3 7

 下面我们还是用递归方式实现中序遍历， 仍然是在之前的Tree 类里面定义中序遍历的函数，代码如下：

    def inorder(self, root):
        """递归实现中序遍历"""
        if root == None:
            return
        self.inorder(root.lchild)
        print(root.element, end='  ')
        self.inorder(root.rchild)

 对其进行测试，测试代码如下：

if __name__ == '__main__':
    tree = Tree()
    for item in range(7):
        tree.add(item + 1)
    print("创建树成功")
    print("中序遍历")
    root = tree.root
    tree.inorder(root)

经测试，输出结果如下，也是和我们之前的顺序一致：

后序遍历：（左右后）第一次和第二次经过时都不访问，等遍历完该节点的左右子树之后，最后访问该节点。

对上图进行后序遍历后的顺序为：4 5 2 6 7 3 1

下面我们还是用递归方式实现后序遍历， 仍然是在之前的Tree 类里面定义后序遍历的函数，代码如下：

    def lastorder(self, root):
        """递归实现后序遍历"""
        if root == None:
            return
        self.lastorder(root.lchild)
        self.lastorder(root.rchild)
        print(root.element, end='  ')

 对其进行测试，测试代码如下：

if __name__ == '__main__':
    tree = Tree()
    for item in range(7):
        tree.add(item + 1)
    print("创建树成功")
    print("后序遍历")
    root = tree.root
    tree.lastorder(root)

经测试，输出结果如下，也是和我们之前的顺序一致：

 

 

求二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结 形成树的一条路径，最长路径的长度为树的深度。

代码如下：

    def depth(self, root):
        """求二叉树的深度"""
        if root == None:
            return  0
        lcount = self.depth(root.lchild) + 1  # 树左侧的深度
        rcount = self.depth(root.rchild) + 1
        return  lcount if lcount > rcount else rcount

---

二叉排序树 

什么是二叉排序树呢？ 

二叉排序树要么是空二叉树，要么具有如下特点： 

• 二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
• 二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
• 二叉排序树的左右子树也要求都是二叉排序树。

例如下图的二叉树就是一个二叉排序树：

二叉排序树的操作

查找：对比节点的值和关键字，相等则表明找到了；小了则往节点的左子树去找，大了则往右子树去找，这么递归下去，最后返回布尔值或找到的节点。

插入：从根节点开始逐个与关键字进行对比，小了去左边，大了去右边，碰到子树为空的情况就将新的节点链接。

删除：如果要删除的节点是叶子，直接删；如果只有左子树或只有右子树，则删除节点后，将子树链接到父节点即可；如果同时有左右子树，则可以将二叉排序树进行中序遍历，取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。 

我们先根据二叉排序树的特点，进行二叉排序树的封装与创建添加元素，代码如下：

class Node(object):
    """二叉树节点对象的封装"""
    def __init__(self, element):
        self.element = element
        self.lchild = None
        self.rchild = None

    def __str__(self):
        return '<Node:%d>' % (self.element)

class BinarySortTree(object):
    """二叉排序树的封装"""
    def __init__(self):
        self.root = None

    def is_empty(self):
        return self.root is None

    def add(self, item):
        """
        树里面插入元素
            1. 先判断树是否为空， 直接让根结点指向新的节点
            2. 如果不为空:
                从根结点开始访问， 判断一下item和节点的大小;
                    如果大于节点元素， 往右孩子节点添加；
                    如果小于节点元素， 往左孩子节点添加；
        """
        node = Node(item)
        if self.root is None:
            self.root = node
        bt = self.root
        while True:
            rootItem = bt.element
            # 如果添加的元素是否大于根结点元素：
            if item > rootItem:
                # 如果根结点的右子树为空， 直接添加节点到右子树即可；
                if bt.rchild is None:
                    bt.rchild = node
                # 如果根结点的右子树不为空， 将右子树节点作为新的根结点， 循环继续判断;；
                bt = bt.rchild
            elif item < rootItem:
                if bt.lchild is None:
                    bt.lchild = node
                bt = bt.lchild
            # 如果插入的元素和根结点相等， 不做操作;
            else:
                return

对封装的二叉排序树进行测试，之前写过层次遍历的代码，这里就不写了，还是直接用前面的层次遍历函数去遍历添加的元素，测试代码如下：

if __name__ == '__main__':
    sortedTree = BinarySortTree()
    nums = [45, 12, 53, 3, 37, 100, 24, 52, 61, 90, 78]
    for num in nums:
        sortedTree.add(num)
    sortedTree.breadth_travel()

结果如下：

下面是查找指定元素的代码，还是在之前的BinarySortTree 类里面创建查找函数，代码如下：

    def search(self, root, key):
        """
        搜索指定元素是否在树里面
            key: 用户搜索的元素
        """
        if root is None:
            return False
        # 如果找到节点元素和用户搜索的值相等， 直接返回节点对象
        if root.element == key:
            return root
        # 如果找到节点元素大于用户搜索的值， 直接返回节点对象
        elif root.element > key:
            return self.search(root.lchild, key)
        else:
            return self.search(root.rchild, key)

二叉排序树中删除节点

对于一个二叉排序树，删除其中指定节点，会有以下三种可能：

1. 如果要删除的节点是叶子，直接删；
2. 如果只有左子树或只有右子树，则删除节点后，将子树链接到父节点即可；
3. 如果同时有左右子树，(两种方式)则可以将二叉排序树进行中序遍历，取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。

针对第三种可能，具体有两种方法可以实现：

方法一：令结点 p 的左子树为其双亲结点的左子树；结点 p 的右子树为其自身直接前驱结点的右子树 ，如下图：

方法二： 用结点 p 的直接前驱（或直接后继）来代替结点 p，同时在二叉排序树中对其直接前驱（或直接后继）做删除操作。在对左图进行中序遍历时，得到的结点 p 的直接前驱结点为结点 s，所以直接用结点 s 覆盖结点 p，如下图所示：

下面我们用代码实现二叉排序树的删除指定元素，因为在删除元素时要知道要删除节点的父节点，因此，先创建一个输出指定节点的父节点的函数，代码如下：

    def searchDetail(self, root, parent, key):
        """
        搜索指定元素是否在树里面, 如果有，则返回3个值:
            1. Bool: 是否找到该元素;
            2. node: 找到元素对应的节点
            3. parent: 找到的元素对应的父节点;
        """
        if root is None:
            return False, root, parent
        # 如果找到节点元素和用户搜索的值相等， 直接返回节点对象
        if root.element == key:
            return True, root, parent
        # 如果找到节点元素大于用户搜索的值， 直接返回节点对象
        elif root.element > key:
            return self.searchDetail(root.lchild, root, key)
        else:
            return self.searchDetail(root.rchild, root, key)

接下来就写删除指定元素的代码，我们分别针对不同情况写代码：

1.如果要删除的节点是叶子，直接删。代码如下：

        if node.lchild is None and node.rchild is None:
            # 判断删除的节点是父节点左孩子还是右孩子
            if parent.lchild == node:
                parent.lchild = None
            else:
                parent.rchild = None

2.如果只有左子树或只有右子树，则删除节点后，将子树链接到父节点即可。代码如下：

        # 如果只有左子树
        if node.lchild is not None and node.rchild is None:
            # 如果node是parent的左子树：
            if parent.lchild == node:
                parent.lchild = node.lchild
            else:
                parent.rchild = node.lchild
        # 如果只有右子树
        if node.rchild is not None and node.lchild is None:
            # 如果node是parent的左子树：
            if parent.lchild == node:
                parent.lchild = node.rchild
            else:
                parent.rchild = node.rchild

3.如果同时有左右子树，则可以将二叉排序树进行中序遍历，取将要被删除的节 点的前驱或者后继节点替代这个被删除的节点的位置。我们用第一种方法，代码如下：

       # 如果有左右子树
        # 方法一: 令结点 node 的左子树为其双亲结点的左子树；结点 node的右子树为其自身直接前驱结点的右子树
        if node.lchild is not None and node.rchild is not None:
            # 如何找到node的直接前驱节点, 找到后， 将直接前驱节点的右子树指向node的右子树;
            # 当前节点左子树的最右节点
            # 分类讨论， 删除的是父节点的左孩子还是右孩子
            if parent.lchild == node:
                parent.lchild = node.lchild
            else:
                parent.rchild = node.lchild
            prevNode = node.lchild
            while prevNode.rchild:
                prevNode = prevNode.rchild
            # prev指的是node节点的直接前驱(中序遍历时，node节点前面的节点)
            prevNode.rchild = node.rchild

把以上三种情况的代码写入下面的函数中去，删除指定元素的函数就写好了：

    def delete(self, key):
        # 查找删除元素对应的节点, isExists是否找到该节点元素， node是找到的节点对象， parent：元素节点的父节点
        isExists, node, parent = self.searchDetail(self.root, None, key)

        if not isExists:
            print("要删除的元素%d不存在" % (key))
            return

        # 如果深处的是根节点， 不处理
        if node == self.root:
            print("不能删除根结点")
            return

我们对其进行测试，测试代码如下：

针对情况一：

if __name__ == '__main__':
    sortedTree = BinarySortTree()
    nums = [45, 12, 53, 3, 37, 100, 24, 52, 61, 90, 78]
    for num in nums:
        sortedTree.add(num)
    sortedTree.breadth_travel()
    sortedTree.delete(24)
    sortedTree.breadth_travel()

针对情况二：

if __name__ == '__main__':
    sortedTree = BinarySortTree()
    nums = [45, 12, 53, 3, 37, 100, 24, 52, 61, 90, 78]
    for num in nums:
        sortedTree.add(num)
    sortedTree.breadth_travel()
    sortedTree.delete(100)
    sortedTree.breadth_travel()

针对情况三：

if __name__ == '__main__':
    sortedTree = BinarySortTree()
    nums = [45, 12, 53, 3, 37, 100, 24, 52, 61, 90, 78]
    for num in nums:
        sortedTree.add(num)
    sortedTree.breadth_travel()
    sortedTree.delete(12)
    sortedTree.breadth_travel()

删除指定元素后，三种情况的输出分别如下：

情况一：

情况二：

情况三：

---

平衡二叉树

为了弥补二叉排序树构造时产生影响算法效率的因素，需要对二叉排序树做“平衡化”处理，使其成为一棵平衡二叉树。

平衡二叉树，又称为 AVL 树。遵循以下两个特点的二叉树：

• 每棵子树中的左子树和右子树的深度差不能超过 1；
• 二叉树中每棵子树都要求是平衡二叉树。

其实就是在二叉树的基础上，若树中每棵子树都满足其左子树和右子树的深度差都不超过 1，则这棵二叉树就是平衡二叉树。 

平衡因子：每个结点都有其各自的平衡因子，表示的就是其左子树深度同右子树深度的差。 

平衡二叉树中各结点平衡因子的取值只可能是：0、1 和 -1。

如下图中的 a 为一个平衡二叉树：

 

平衡二叉树调整的规律

1. 单向右旋平衡处理

 

2. 单向左旋平衡处理

3. 双向旋转（先左后右）平衡处理

4. 双向旋转（先右后左）平衡处理

应用：平衡二叉树可应用于搜索算法中，进行查找操作的时间复杂度为O(logn)。