阅读裘宗燕老师的《数据结构与算法:python语言描述》的课件所记笔记

七、二叉树遍历算法

1.递归形式程序实现

  • 先根序:
    def preorder(t, proc):
    if t is None:
        return
    proc(t.data)
    preorder(t.lleft, proc)
    preorder(t.right, proc)
  • 实例:用括号的前缀形式输出二叉树,空子树输出符号^
    def print_BitNode(t):
    if t is None:
        print("^")
        return
    print("(" + str(t.data))
    print_BitNode(t.left)
    print_BitNode(t.right)
    print(")")

    例如t = BitNode(1, BitNode(2, None, None), BitNode(3, None, None))将会输出(1(2^^)(3^^))

2.宽度优先程序实现

  • 采用宽度优先遍历需要用到一个队列:
    def levelorder(t, proc):
    qu = SQueue()
    qu.enqueue(t)
    while not qu.is_empty():
        n = qu.dequeue()
        if n is None:
            continue
        proc(n.data)
        qu.enqueue(n.left)
        qu.enqueue(n.right)

3.非递归定义

a.先根序
  • 先根序的非递归遍历需要用一个栈保存树尚未访问过的部分
  • 基本想法:
    • 先根序,访问遇到的结点并沿左枝下行,尚未访问的右分支需要记录,将其入栈
    • 与空树时回溯,取出栈中保存的右分支,像一棵树一样遍历它
  • 算法细节:
    • 循环条件:当前树非空(这棵树需要遍历)或栈不空(还存在整棵树的未遍历部分),这时应该继续循环
    • 在向下检查左分支时把经过结点的右分支入栈(也要用一个循环)
    • 弹出栈中元素(一个右子树)回溯,要做的也是遍历一颗二叉树
      def preporder_nonrec(t, proc):
      s = SStack()
      while t is not None or not s.is_empty():
      while t is not None:
          proc(t.data)
          t = t.left
          s.push(t.right)
  • 非递归算法的一个意义是把算法过程完整地暴露出来,便于分析。现在考虑其复杂性:
    • 时间复杂性:每个结点访问一次,一部分子树压入弹出栈一次,整个遍历是O(n)时间
    • 空间复杂性:关键因素是遍历中栈曾经达到的最大深度,栈的深度由二叉树高度决定,最坏情况的空间复杂性是O(n),平均复杂性是O(logn),如果只将非空右子树进栈,有可能减少空间开销
迭代器程序实现
def preorder_iter(t):
    s = SStack()
    while t is not None or not s.is_empty:
        while t is not None:
            yield t.data
            t = t.left
            s.push(t.right)
        t = s.pop()
b.后根序
  • 遍历循环中维持一种不变关系
    • 栈中结点是对二叉树的划分,左边是已遍历过的部分,右边是尚未遍历的部分
    • 栈中每个结点的父结点就是位于它下面那个结点,当前结点的父结点是栈顶
    • 根据本结点是父结点的左子结点或右子结点,可以决定下一步怎么做
    • 在需要从当前结点回溯之前访问这个结点
程序实现
def posorder_nonrec(t, proc):
    s = SStack()
    while t is not None or not s.is_empty():
        while t is not None:
            s.push(t)
            t = t.left if t.left is not None else t.right
        t = s.pop()
        proc(t.data)
        if t is not None and s.top().left == t:
            t = s.top().right
        else:
            t = None
        # 没有左子树或左子树遍历完毕,强迫退栈。而不是没有右子树或右子树遍历完

4.递归和非递归遍历

  • 对递归遍历算法,无论用哪种顺序,对深度为n的畸形树,栈深度都会达到n或n-1
  • 非递归遍历算法的情况可能不同
    • 后根序遍历必须把未遍历的整条路径存入栈,对深度n的树,栈深度都会达到n
    • 对先根序遍历,如果只入栈非空右子树,遍历单枝树(只有左子树)时栈深度都不会大于1,最坏情况大约n/2
    • 中根序与先根序类似

5.二叉树数据结构

  • 直接用结点构造的二叉树具有递归结构,可以很方便地递归处理。但有不统一的地方:
    • 用None表示空树,但None不具有BitNode类型
  • 解决方法是定义一个二叉树类型,以结点树作为其内部表示
a.程序实现
class BiTree(object):

    def __init__(self):
        self._root = None

    def is_empty(self):
        return  self._root == None

    def set_root(self, rootnode):
        self._root = rootnode

    def set_left(self, leftchild):
        self._root.left = leftchild
    def set_right(self, rightchild):
        self._root.right = rightchild

    def root(self):return self._root
    def leftchild(self):return self._root.left
    def rightchild(self):return self._root.right

八、哈夫曼树

  • 是一种二叉树,在信息领域有重要理论和实际价值
  • 考虑带权扩充二叉树的“外部路径长度”。这种二叉树的外部结点(叶结点)标有一个权值,称为该结点的权,表示与该叶有关的某种性质
  • 扩充二叉树的外部路径长度:
    $$E=\sum_{i=1}^ml_i$$
    $l_i$:从根到外部结点i的路径长度
    m:外部结点个数
  • 带权外部路径长度:
    $$WPL=\sum_{i=1}^mw_il_i$$
    $w_i$:外部结点i的权

1.定义

  • 有实数集W={$w_1,w_2,...,w_m$},T是一棵扩充二叉树,包含m个分别以$w_i$(i=1,2,...,m)为权的外部结点,且其带权外部路径长度WPL达到最小,则称T为数据集W的最优二叉树或哈夫曼树
  • 以同一集实数为外部结点权的二叉树,WPL可能不同

2.哈夫曼算法

  • 输入实数集W={$w_1,w_2,...,w_m$}
    • 构造中维护包含m棵二叉树的集合F,开始时F={$T_1,T_2,...,T_M$},其中$T_i$是只把韩权为$w_i$的根结点的单点二叉树
    • 重复如下步骤,直到F中只含一棵树为止
      • 从F中选取两棵权最小的树作为左右子树,构造一棵新的二叉树,设置其根结点权值为两棵子树根结点的权值之和
      • 从F中删除所选的两棵树,把新构造的二叉树加入F
  • 集合W上的哈夫曼树不唯一。如果T是W上的哈夫曼树,交换T的左右子树,依然是。

3.哈夫曼编码

  • 问题:给定基本数据集合:
    D=[$d_1,d_2,...,d_n$] W=[$w_1,w_2,...,w_n$]
    其中D是需要编码的字符集合,W为D中各个字符在实际信息传输中出现的概率。要求为D设计一套二进制编码,使得:1)用此编码存储、传输时的平均开销最小;2)对任意不同$d_i$和$d_j$,$d_i$编码不是$d_j$编码的前缀
  • 上述第二个条件使解码时容易判断是否已得到一个字符的编码
    因为任意字符编码不是另一字符编码的前缀,看到了对应于一个字符的一段编码,就可以确定是该字符
  • 注意:这里考虑的编码优化问题,允许各字符的编码长度不同。
  • 哈夫曼提出的方法是通过构造哈夫曼树实现哈夫曼编码:
    • 以字符$d_1,d_2,...,d_n$作为外部结点的标注,把$w_1,w_2,...,w_n$作为这n个外部结点的权,基于他们构造一棵哈夫曼树
    • 在得到的哈夫曼树中,给所有从一个结点到其左子结点的边标上二进制数字0;到右子结点的边标上1
    • 以从根结点到一个叶结点的路径上的二进制数字序列,作为这个叶结点的字符的编码

九、树

  • 在一般的状态空间搜索问题里,搜索过程中经历的状态(看作结点)和状态之间的联系(看作边)就形成了一棵“树”,称为“搜索树”。搜索过程就是按某种顺序“遍历”这棵树
  • 由于非空的树总有一个根结点,掌握了根结点也就掌握了以它为根的树,人们常把树t与其根结点统一看待

1.树的表示

  • 常用的树表示方法:
    • 子指针表示法,父指针表示法
    • 子表表示法
    • 长子-兄弟表示法(树的二叉树表示法)
  • 实际上,树林和二叉树之间有一种1-1对应关系。在这种对应下
    • 树林可以用二叉树表示
    • 树可以用二叉树的一个子集表示

2.树林与二叉树的对应(转换)

  • 从树、树林转换为二叉树的步骤:
    • 对于相邻的兄弟结点,从左到右,从前一子结点和后一子结点连一条边(对树林,相邻树的根之间也同样连一条边)
    • 对每个非叶结点,只保留从他到最左子结点的边,删去他到其其它子女的边
  • 经过上述转换,每个非叶结点至多发出两条边:
    • 一条到它的第一个子结点,此边看作在二叉树里这个结点到其左子树根结点的边
    • 另一条到他在原来树中的下一个兄弟结点,此边看作在二叉树里该结点到其右子树根结点的边
  • 二叉树转换到树林(树)
    • 如果其结点是父结点的左子树,则将其向右的路径上的各个结点作为其父结点的顺序的各个子结点
    • 去掉原二叉树中各结点到其右子结点的连线

3.结点链接表示法

  • 具体实现如下:
    • 一个树结点用一个存储块表示
    • 在这个存储块里记录树结点本身的信息,还要记录其子树个数
    • 在结点的存储块里保存到它的各子结点的引用
    • 根结点存储块代表整棵树
    • 如果需要,还可以在每个结点里增加一个父结点链接
  • 该方法的好处是直接,缺点是结点存储块的大小由子结点的个数决定,大小不一

4.子表表示法

  • 用一个结点数组(或者线性表),每个结点在数组中有一个位置(下标)
    • 每个结点关联一个子结点表,其中记录子结点的(数组)位置
    • 结点本身的数据存储在数组的相应位置
  • 结点表可以用链接表

5.总结

  • 实际算法和程序中,树的使用不如二叉树广泛
    • 树的结构不规整,结点的子结点个数可能不同,而且没有限制。计算机里表示和处理比较麻烦
    • 表示树结点的存储块大小可能不同,而且可能相差很大,存储管理工作麻烦,时间和空间开销大
    • 需要维护记录结点的子结点个数
    • 动态增减子结点,也会带来更复杂的管理问题
最后由 oucb 编辑于2016年07月01日 14:47