python实现二叉树

首先我们先介绍数的概念。

一、树

树的结点

结点：使用树结构存储的每一个数据元素都被称为“结点”。例如，图 1（A）中，数据元素 A 就是一个结点；

父结点（双亲结点）、子结点和兄弟结点：对于图 1（A）中的结点 A、B、C、D 来说，A 是 B、C、D 结点的父结点（也称为“双亲结点”），而 B、C、D 都是 A 结点的子结点（也称“孩子结点”）。对于 B、C、D 来说，它们都有相同的父结点，所以它们互为兄弟结点。

树根结点（简称“根结点”）：每一个非空树都有且只有一个被称为根的结点。图 1（A）中，结点A就是整棵树的根结点。

叶子结点：如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）。例如图 1（A）中，结点 K、L、F、G、M、I、J 都是这棵树的叶子结点。

结点的度和层次

对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree）。例如，图 1（A）中，根结点 A 下分出了 3 个子树，所以，结点 A 的度为 3。

一棵树的度是树内各结点的度的最大值。图 1（A）表示的树中，各个结点的度的最大值为 3，所以，整棵树的度的值是 3。一棵树的度是树内各结点的度的最大值。图 1（A）表示的树中，各个结点的度的最大值为 3，所以，整棵树的度的值是 3。

结点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。对于图 1（A）来说，A 结点在第一层，B、C、D 为第二层，E、F、G、H、I、J 在第三层，K、L、M 在第四层。

树的种类：

无序树：树中任意节点的子节点之间没有顺序关系，称为无序树
有序树：树中任意节点的子节点之间有顺序关系，称为有序树
- 二叉树：每个节点最多含有两个子树的树称为二叉树
  - 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其他各层的节点数目均已达到最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树称为完全二叉树，其中满二叉树的定义是所有叶子节点都在最底层的完全二叉树
  - 平衡二叉树（AVL树）：当且仅当任何节点的两颗子树的高度差不大于1的二叉树
  - 排序二叉树：当我们遍历树中的节点时，是有序的
- 霍夫曼树：带权路径最短的二叉树称为哈弗曼树或最优二叉树
- B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树

二、二叉树

简单地理解，满足以下两个条件的树就是二叉树：

本身是有序树；
树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

例如，图 1a) 就是一棵二叉树，而图 1b) 则不是。

图 1 二叉树示意图

二叉树的性质：

性质1：在二叉树的第i层上至多有2^(i-1)个节点（i>0）
性质2：深度为k的二叉树至多有2^k-1个节点（k>0）
性质3：对于任意一棵二叉树，如果其叶子结点数为 n0，度为 2 的结点数为 n2，则 n0=n2+1

性质 3 的计算方法为：对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 n1），那么总结点 n=n0+n1+n2。
同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的，即 B=n1+2*n2。所以，n 用另外一种方式表示为 n=n1+2*n2+1。
两种方式得到的 n 值组成一个方程组，就可以得出 n0=n2+1。

性质4：具有n个结点的完全二叉树的深度必为 log2(n+1) （可由性质2倒推）
性质5：对完全二叉树，若从上至下、从左至右编号，则编号为 i 的结点，其左孩子编号必为 2i，其右孩子编号必为 2i+1，其双亲的编号必为 i/2 （根节点除外）

三、树的存储与表示

顺序存储：二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。

普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些节点，将其"拼凑"成完全二叉树即可。如图 1 所示：

链式存储：

如图 1 所示，此为一棵普通的二叉树，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。因此，图 1 对应的链式存储结构如图 2 所示：

图 2 二叉树链式存储结构示意图

由图 2 可知，采用链式存储二叉树时，其节点结构由 3 部分构成（如图 3 所示）：

指向左孩子节点的指针（Lchild）；
节点存储的数据（data）；
指向右孩子节点的指针（Rchild）；

四、二叉树遍历

二叉树的访问次序可以分为四种：

前序遍历
中序遍历
后序遍历
层序遍历

4.1 层序遍历

层次遍历就是按照树的层次自上而下的遍历二叉树。针对图所示二叉树的层次遍历结果为：

ABCDEFGHIJ

4.2 前序遍历

前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。（中 -> 左 -> 右）

针对图所示二叉树的层次遍历结果为：ABDHIEJCFG

4.3 中序遍历

中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。（左 -> 中 -> 右）

针对图所示二叉树的层次遍历结果为：HDIBJEAFCG

4.4 后序遍历

后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。（左 -> 右 -> 中）

针对图所示二叉树的层次遍历结果为：HIDJEBFGCA

以下为二叉树遍历的python实现：

class Node (object):
    """二叉树结点的定义"""
    def __init__(self,item):
        self.elem = item
        self.lchild = None
        self.rchild = None

class Tree(object):
    """二叉树"""
    def __init__(self):
        self.root = None  #根结点

    def add(self,item):
        """添加结点"""
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]   #队列
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

    def breadth_travel(self):
        """利用队列实现树的层次遍历（广度遍历）"""
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem,end=" ")
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

    def preorder(self,node):
        """前序遍历（深度遍历）(中 -> 左 -> 右)"""
        if node is None:
            return
        print(node.elem,end=" ")
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def inorder(self,node):
        """中序遍历（深度遍历）(左 -> 中 -> 右)"""
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.elem, end=" ")  #此处可认为 node.elem 就是我们要处理的结点
        self.inorder(node.rchild)

    def postorder(self,node):
        """后序遍历（深度遍历）(左 -> 右 -> 中)"""
        if node is None:
            return
        self.postorder(node.lchild)
        self.postorder(node.rchild)
        print(node.elem, end=" ")

这时我们就能通过任意一棵二叉树推出来四种遍历结果。我们也能从中序遍历+其他任意一种遍历倒推出来二叉树。（注：不能由前序和后序遍历推出来二叉树）因为中序遍历把左节点和右节点分开了，如果没有中序遍历就无法分开左右节点。

问题一：已知前序遍历和中序遍历，确定一个二叉树。先序：根左右中序：左根右

例题：若一棵二叉树的前序遍历为ABCDEF，中序遍历为CBAEDF，请画出这棵二叉树。
分析：前序遍历第一个输出结点为根结点，故A为根结点。早中序遍历中根结点处于左右子树结点中间，故结点A的左子树中结点有CB，右子树中结点有EDF。
如图3.14所示：

图3.14

按照同样的分析方法，对A的左右子树进行划分，最后得出二叉树的形态如图3.15所示：

图3.15.png

2）已知后序遍历序列和中序遍历序列，确定一棵二叉树。
后序遍历中最后访问的为根结点，因此可以按照上述同样的方法，找到根结点后分成两棵子树，进而继续找到子树的根结点，一步步确定二叉树的形态。

若给出后序和中序，和上面一样的推理方法。