第二章 树和二叉树

在本篇中, 首先讲述了关于二叉树的相关知识, 第二讲述了关于最优二叉树 (哈夫曼树) 所建立的哈夫曼编码. 第三阐述了树与二叉树的关系与转换

二叉树的存储, 其次讲述了二叉树的四种遍历方式, 以及如何将二叉树进行翻转

二叉树的存储

• 顺序存储: 只适用于完全二叉树
• 链式存储

二叉树的遍历

• 分为先序遍历 (DLR) , 中序遍历 (LDR) ,后序遍历 (LRD) 和层序遍历
• 先序遍历: 依次从上往下访问根节点, 左子树, 右子树, 若二叉树为空返回空操作
• 中序遍历: 依次从上往下访问左子树, 根节点, 右子树, 若二叉树为空返回空操作
• 后序遍历: 依次从上往下访问左子树, 右子树, 根节点, 若二叉树为空返回空操作
• 层序遍历: 若二叉树为空, 则空操作返回; 否则, 从根节点从上而下逐层遍历, 同一层中顺序为从左到右

二叉树的翻转

• 左右翻转那种样子

二叉树的存储, 遍历与翻转的代码实现

点击显/隐图片

待定

点击显/隐代码

class Node(object):
    """二叉树存储: 链式"""

    def __init__(self, key=None, lchild=None, rchild=None):
        self.key, self.lchild, self.rchild = key, lchild, rchild  # 表示数据域, 左子树, 右子树


class BTree(object):
    def __init__(self, root=None):
        """建立二叉树"""
        self.root = root

    def PreOrder(self, root):
        """先序遍历: 依次从上往下访问根节点, 左子树, 右子树, 若二叉树为空返回空操作"""
        if root is not None:
            print(root.key, end=" "); self.PreOrder(root.lchild); self.PreOrder(root.rchild)

    def InOrder(self, root):
        """中序遍历: 依次从上往下访问左子树, 根节点, 右子树, 若二叉树为空返回空操作"""
        if root is not None:
            self.InOrder(root.lchild); print(root.key, end=" "); self.InOrder(root.rchild)

    def PostOrder(self, root):
        """中序遍历: 依次从上往下访问左子树, 右子树, 根节点, 若二叉树为空返回空操作"""
        if root is not None:
            self.PostOrder(root.lchild); self.PostOrder(root.rchild); print(root.key, end=" ")

    def breath_travel(self):
        """层序遍历: 若二叉树为空, 则空操作返回; 否则, 从根节点从上而下逐层遍历, 同一层中顺序为从左到右"""
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print(node.key, end=" ")
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)

class Mirror(object):
    """翻转二叉树"""

    def mirror(self, root):
        if not root:
            return
        root.lchild, root.rchild = root.rchild, root.lchild
        self.mirror(root.lchild)
        self.mirror(root.rchild)


if __name__ == "__main__":
    root = Node(1, Node(2, Node(4, Node(8), Node(9)), Node(5, Node(10), Node(11))),
                Node(3, Node(6, Node(12), Node(13)), Node(7, Node(14), Node(15))))
    bt = BTree()
    m = Mirror()
    print("先序遍历: ", bt.PreOrder(root))
    print("中序遍历: ", bt.InOrder(root))
    print("后序遍历: ", bt.PostOrder(root))
    print("层序遍历: ", bt.breath_travel())
    m.mirror(root)
    print("翻转后的中序遍历", bt.InOrder(root))

由遍历序列创建二叉树

• 可分为 “知先序中序求后序” , “知中序后序求先序” .

• 例 1 : 由先序, 中序推出后序遍历
  已知二叉树的先序遍历是 ABCDEF , 中序遍历是 CBAEDF , 求后序遍历.

  点击显/隐思路

  先序遍历是先打印根节点, 故可知 A 为根节点;
  中序遍历是先递归左子树, 再打印根节点, 故可知 CB 为左子树节点, EDF为右子树节点.
  左子树判断开始:
  先序遍历是先打印根节点, 再递归左子树, 所以 B 是 A 的左孩子;
  中序遍历是先递归左子树, 再打印根节点, C 在 B 前, 所以 C 是 B 的左孩子;
  左子树告一段落;
  右子树判断开始:
  先序遍历是先递归左子树 BC , 再递归右子树 DEF , 所以 D 是 A 的右孩子;
  中序遍历是先递归左子树, 再打印根节点, 再递归右子树, D 在 EDF 的中间, 所以 E 为 D 的左孩子, F 为 D 的右孩子.
  右子树告一段落.
  现在可以得到: 根节点: A, 根节点左右孩子 BD , B 的左孩子 C , D 的左右孩子 EF.
  后序遍历由此可知: CBEFDA .

• 例 2 : 由中序, 后序推出先序遍历
  已知二叉树的中序遍历是 ABCDEFG , 后序遍历是 BDCAFGE , 求先序遍历.

点击显/隐思路

后序遍历最后一个是根节点, 因此可知 E 为根节点.
中序遍历先递归左子树, 再打印根节点, 再递归右子树, 由此可知 ABCD 为左子树, FG 为右子树.
左子树判断开始:
在后序遍历中, 子树的根节点是在子树的最后一个, 因此 A 为 E 的左孩子
在中序遍历中, 遍历顺序为 (左根右) LDR (LeftDataRight) , 所以 BCD 全为 A 的右孩子.
在后序遍历中, 遍历顺序为LRD, 所以 BD 是 C 的左右孩子.
所以 D 很明显, 是 A 的右孩子.
左子树告一段落;
右子树判断开始:
在后序遍历中, 子树的根节点是在子树的最后一个, 因此 G 为 E 的右孩子.
在后序遍历中, 遍历顺序为 LRD, 所以 F 是 G 的孩子.
在中序遍历中, 遍历顺序为 LDR, 所以 F 是 G 的左孩子.
右子树告一段落.
现在可以得到: 根节点 E , E 的左右孩子 AG , A 的右孩子 D, D 的左右孩子 BC , G 的左孩子 F .
先序遍历由此可知: EACBDGF .

##哈夫曼树
例 3：现有节点a，b，c，d，e，f 6个字符，其权值分别为a（9），b（12），c（6），d（3），e（5），f（15），构建哈夫曼树。

点击显/隐

注：左子树的值小于右子树。
进行排序，值中，最小的是d，e，因此d，e分别为左右子树，权值之和为de（8）
将 de 加入后排序，最小的是 c，de，因此 c，de分别为左右子树，权值之和为 cde（14）
将cde加入后排序，最小的是 a，b，因此 a，b 分别为左右子树，权值之和为ab（21）
将 ab加入后排序，最小的是 cde，f，因此 cde，f分别为左右子树，权值之和为 cdef（29）
只剩下ab，cdef，因此ab，cdef分别为左右子树，权值之和为 abcdef（50）。

例 4：得到上述哈夫曼树的编码。

点击显/隐

从根节点出发，左子树边为0，右子树为1，进行编码。
a：00；b：01；c：100；d：1010；e：1011；f：11.

可以得到1：权值越大，长度越短。
可以得到2：每一个结点都是叶子结点，因此保证了译码的唯一性。