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

四、二叉树应用

1.表达式树

  • 基本运算对象作为叶结点的数据
  • 运算符作为分支结点的数据,其两棵树是它的运算对象,可以是基本运算对象,也可以是作为运算对象的两个表达式
  • 例如表达式3 * (2 + 5):
    ['*', [3, [], []], ['+', [2, [], []], [5, [], []]]]
    简化为:['*', 3, ['+', 2, 5]]
  • 上述简化的表达式由两种结构组成:
    • 如果是表,就是运算符作用于运算对象的复合表达式
    • 否则就是基本表达式,即数或者变量
    • 上述两条用于解析表达式的结构,实现对表达式的处理
    • 算术表达式是特殊情况,其基本表达式都是数
a.程序实现
def make_sum(a, b):
    return ['+', a, b]
def make_prod(a, b):
    return ['*', a, b]
def make_diff(a, b):
    return ['-', a, b]
def make_div(a, b):
    return ['/', a, b]
  • isinstance(a, list)判断是否为基本表达式
  • isinstance(x, Number)判断是否为数,需要导入Number

2.X表达式求值

  • 对表达式里的数和变量,其值就是它们自身
  • 其他表达式,要根据运算符的情况处理
  • 如一个运算符的两个运算对象都是数,那就可以求出一个数值
  • 特殊情况,如加数为0,乘数是0或1,可部分求值化简

3.优先队列

  • 是一种常用的缓存结构,与栈和队列类似
  • 特点是存入的每项数据附有一个优先级
  • 保证任何时候访问或弹出的总是当时优先级最高的元素
a.实现的效率问题
  • 若存在多个最优先元素
    • 若要求这些元素的先进先出,则只能做出效率较低的实现
    • 若只要求保证是最优先元素中的一个,则存在效率更高的实现
b.实际应用
  • 各项工作的计划开始时间
  • 一个大项目中各种工作任务的急迫程度
  • 银行客户的诚信评估,用于决定优先贷款,等等
c.操作
  • 创建,判断空
  • 插入元素,访问和删除优先队列里的元素
d.基于线性表技术
  • 存在两种实现方案:
    • 存入时保证元素按优先顺序排列
    • 元素直接存到表的尾端,取用时检索最优先元素
  • 分析后选择第一种
    • 加入新元素时,确定正确插入位置
    • 为保证O(1)的弹出操作,最优先元素应该出现在尾端
    • 注意:插入元素只能用insert(或其他类似操作),不能用元素位移,因为list超下标范围的赋值会出错
程序实现:
  • 先定义一个类:
    class PriQue(object):
    def __init__(self, lst=[]):
        self.elems = sorted(lst)
  • 插入元素操作:假设元素可用<=比较,把较小看作优先
    def enqueue(self, e):
    i = len(self.elems) - 1
    while i >= 0:
        if self.elems[i] <= e:
            i -= 1
        else:
            break
    self.elems.insert(i+1, e)
  • 其他操作:

    def is_empty(self):
        return self.elems == []
    
    def peek(self):
        if self.is_empty():
            raise PriQueueError("in top")
        return self.elems[len(self.elems)-1]
    
    def dequeue(self):
        if self.is_empty():
            raise PriQueueError("in top")
        return self.elems.pop()
    
    class PriQueueError(ValueError):
        pass
  • 操作效率分析
    • 插入是O(n),其他都是O(1)
    • 如果采用第二种,插入式O(1),检查和弹出都是O(n)
e.树形结构实现
  • 由于使用线性表时元素按线性顺序排列元素,因此不可避免插入元素需要O(n)
  • 基于树形结构,插入时就不必重复检索同一优先级其他元素
  • 树形结构实现需要解决:在反复插入和删除元素中,如何始终保证结构的有效性
  • 采用树形结构实现优先队列的一种有效技术称为堆

4.堆

  • 结构上是一棵在结点里存储数据的完全二叉树
  • 元素按数据优先关系排序,这种堆序保证任一结的数据不大于其子结点的数据
  • 注意:堆序要求按结点子孙序,数据从小到大递增
a.堆特点
  • 堆中最优先元素位于堆顶,O(1)操作获取
  • 位于树中不同路径上的元素,这里不关心其顺序关系
b.堆的分类
  • 小元素在上的称为小顶堆
  • 大元素在上的称为大顶堆
c.实现特点
  • 一棵完全二叉树可以很自然而且信息完全地存入一个连续的线性结构,因此堆也可以,仅使用下标就能方便访问树中一个结点的父结点或子结点
  • 去掉一个堆的最后元素,剩下的仍是堆
  • 去掉堆顶,其余元素形成两个堆
  • 上面两个堆加一个元素作为根,得到一棵完全二叉树但未必是堆
  • 堆最后加上一个元素,整个结构是一棵完全二叉树但未必是堆
d.实现问题
  • 加入一个元素,怎样将加入后得到的完全二叉树转变为堆
  • 弹出元素后,任何将剩下的元素重新做成堆
e.向上筛选和向下筛选
  • 向上筛选:在堆H的最后加入一个元素e后,通过一次向上筛选,使整个完全二叉树重新恢复为一个堆
    • 不断用e与其父结点的数据比较,如果e较小就交换两个元素位置。直至e的父结点的数据小于等于e时停止
  • 向下筛选:设两个堆B,C加根元素e构成一棵完全二叉树,通过一次向下筛选把它们做成堆
    • 用e与B、C的根比较,最小者作为整个堆的顶。若e不是最小,最小的必为B(或C)的顶元素。下面考虑把e放入去掉堆顶的B(或C):
      • 某次比较中e最小,以它为顶的局部树成堆了,整个结构也成堆
      • e落到底,这时它自身就是一个堆,整个结构也成堆
f.具体实现
  • 加入元素:从堆的最后加入元素,做一次向上筛选
  • 弹出元素:弹出堆顶元素后,从堆最后取一个元素放在堆顶,做一次向下筛选
优先队列的堆实现程序
class PrioQueue:
    def __init__(self, elist = []):
        self.elems = elist
        if elist != []:
            self.buildheap()

    def is_empty(self):
        return len(self.elems) == 0

    def peek(self):
        if self.is_empty():
            raise PrioQueueError("in top")
        return self.elems[0]

    def enqueue(self, e):
        self.elems.append(None)
        self.siftup(e, len(self.elems)-1)

    def siftup(self, e, last):
        elems, i, j = self.elems, last, (last-1)//2
        while i > 0 and e < elems[j]:
            elems[i] = elems[j]
            i, j = j, (j-1)//2
        elems[i] = e

    def dequeue(self):
        if self.is_empty():
            raise PrioQueueError("in top")
        elems = self.elems
        e0 = elems[0]; e = elems.pop()
        if len(elems) > 0:
            self.siftdown(e, 0, len(elems))
        return e0

    def siftdown(self, e, begin, end):
        elems, i, j = self.elems, begin, begin*2+1
        while j < end:
            if j+1 < end and elems[j+1] < elems[j]:
            # elems[j]为左子结点,elems[j+1]为右子结点
                j += 1
            if e < elems[j]:
            # 若e最小则跳出循环,把e作为父结点,
                break
            elems[i] = elems[j]
            # 若e不是最小,把左右子结点中更小的结点       elems[j]作为父结点,继续用该结点的左右子结点与e比较
            i, j = j, 2*j+1
        elems[i] = e        
g.堆排序

5.优先队列应用

a.离散事件模拟
  • 系统运行中可能发生事件
  • 一个事件在某个时刻发生,有可能导致其他事件在未来发生
b.X海关检查站

五、二叉树的链接实现

  • 考虑二叉树结构本身在python里的实现
    • 定义一个二叉树的结点类和一个二叉树类
    • 一个结点通过链接引用到其子结点,没有子结点用None值

1.结点的类定义

class BitNode(object):

    def __init__(self, dat, left, right):
        self.data = dat
        self.left = left
        self.right = right
  • 构造一颗包含三个结点的二叉树,变量t指向树根结点
    t = BitNode(1, BitNode(2, None, None), BitNode(3, None, None))

2.递归性质

基于BitNode对象构造的二叉树具有递归结构,递归处理非常方便:
1.统计结点个数:

def count_BitNode(t):
    if t is None:
        return 0
    else:
        return 1 + count_BitNode(t.left) + count_BitNode(t.right)

2.对结点中保存的数据进行求和:

def sum_BitNode(t):
    if t is None:
        return 0
    else:
        return t.data + sum_BitNode(t.left) + sum_BitNode(t.right)

递归处理二叉树具有统一的模式:如何处理空树情况,如何分别处理二叉树的左右子树和根,并基于这些得到整个树的处理结果

六、二叉树的遍历

  • 二叉树唯一标识:根结点
    • 从根出发可以找到树里所有信息
    • 因此,常用根结点代表一棵二叉树,其左右子树由它们的根结点代表

1.遍历

  • 任何存储数据的汇集结构,都有遍历元素的问题
    • 遍历二叉树,就是按某种系统方式访问二叉树里的每个结点一次
    • 可基于二叉树的基本操作实现,遍历中可能操作结点里的数据
    • 很多复杂的二叉树操作需要基于遍历实现,例如找父结点

2.遍历方式

  • 两种基本方式:
    • 深度优先遍历,尽可能沿一条路径向前,必要时回溯
    • 宽度优先遍历,在所有路径上齐头并进
a.深度优先遍历处理顺序分类
  • 深度优先遍历要做三件事:遍历左子树,遍历右子树,访问根结点(操作其中数据)。下面分别用L、R、D表示
  • 根据三项工作的不同排列方式,有三种常见遍历(假设总先处理左子树,否则就是6种):
    • 先根序遍历(DLR)
    • 中根序遍历(LDR),也称对称序
    • 后根序遍历(LRD)
  • 由于子树也是二叉树,将各种遍历方式继续用到子树遍历中,就形成了遍历二叉树的统一方法:
    • 遍历中遇到子树为空就结束对它的处理,转去继续做下一步工作
    • 如先根序遇到左子树空就去遍历右子树
  • 如果树种数据(或标识)唯一,通过它可以反射到遍历中经过的结点,这时考虑遍历序列就有意义
    • 先根序遍历得到的结点序列称为先根序列
    • 后根序遍历得到的称为后根序列
    • 对称序遍历得到的称为对称(中根)序列
  • 显然给定一棵二叉树,可以唯一确定其先根序列、后跟序列和对称序列
  • 但给定二叉树的任一种遍历序列,无法唯一确定相应的二叉树,如果知道对称序列和另一遍历序列,则可以。如果知道先根序列和后根序列,是否可以确定?
b.宽度优先遍历
  • 逐层访问二叉树各结点,不能写成一个递归过程
  • 做法:
    • 从根开始逐层访问
    • 每层都从左到右逐个访问
    • 实现算法需要用一个队列缓存
  • 宽度优先遍历又称为按层次顺序遍历,产生的结点序列称为二叉树的层次序列
最后由 oucb 编辑于2016年06月23日 11:48