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

一、复杂数据结构

  • 非线性,元素之间的关系不是一对一的,存在更复杂的关系
  • n个元素的数据结构,元素间的最远距离不是n,可能小得多

1.问题

  • 可以表示数据之间更复杂的关系
  • 数据的组织方式有更多选择
  • 可能存在更多不同的实现方法

2.处理方法可能变得复杂

  • 需要借助一些辅助数据结构,例如栈和队列

二、树形结构

  • 树形结构也是由结点(树形结构中的逻辑单元,可用于保存数据)和结点的联系构成

1.特征

  • 每个节点都只有一个前驱(与线性结构一样)
  • 一个结点可以有多个后继(不同于线性结构)
  • 从一个树形结构的任意两个结点出发,通过后继关系可达的结点集合,相互之间或者互不相交,或者有子集关系
  • 树形结构可以表示许多常见的层次性关系,层次结构

2.树的实例

  • 家族关系
  • 机构的结构关系
  • 例如:一个机构的分层结构
    • 假设机构A有两个分部B,C;B和C分别有下级结构D,E,F和G,H;而且E有两个小组I,J
    • 通过结点集合N和关系R,就是一个树形结构:
      N={A,B,C,D,E,F,G,H,I,J}
      R={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<C,H>,<E,I>,<E,J>}

3.树的表示

  • 基本图示法,树根总画在最上面
  • 文氏图,也称韦恩图
  • 嵌套括号表示法

4.树的定义

  • 树是具有递归性质的结构,所以树的定义也是递归的
  • 一棵树是n(n>=0)个结点的有限集T(可为空),T非空时满足:
    • 有且仅有一个特殊的称为根的结点r
    • 根结点外的其余结点划分为m(m>=0)个互不相交的非空有限集T1,T2...Tm,每个集合各位一颗非空树,称为r的子树(subtree)
  • 要求子树都非空,使子树的个数能有明确定义
    • 结点个数为0的树称为空树
    • 一棵树可以只有根但没有子树(m=0),这是一颗单结点的树,只包含一个根结点

5.相关概念

  • 根据是否认为子树的排列顺序有意义,可以分为有序树和无序树两种概念
  • 父结点与子结点(相对定义
    • 一棵树的根结点称为该树的子树的根结点的父结点
    • 子树的根是树根的子结点

  • 从父结点到子结点的连线(有方向)
  • 兄弟结点
    父结点相同的结点互为兄弟结点
  • 树叶、分支结点
    没有子结点的结点称为树叶,树中的其余结点称为分支结点(分支结点可以只有一个分支)
  • 祖先和子孙
    基于父结点/子结点关系和传递性,可以确定相应的传递关系,称为祖先关系或子孙关系。这两个关系决定一个结点的祖先结点,或子孙结点
  • 度数
    一个结点的子结点个数称为该结点的度数,显然树叶的度数为0,一棵树的度数就是其里面度数最大的结点的度数
  • 路径、路径长度
    • 从一个祖先结点到其子孙结点的一系列边称为树中的一条路径,从树的根到树种任一个结点都有路径,且路径唯一
    • 路径中边的条数称为路径长度,认为每个结点到自身有长0的路径
  • 结点的层数
    • 树根到结点的路径长度是该结点的层数
    • 结点都有层数,根所在的层为0
  • 高度(或深度)
    • 树的高度或深度是树中结点的最大层数(最长路径的长度)加1
    • 是树的整体性质,空树高度为0,只有根结点的树高度为1
  • 结点的顺序(仅在考虑有序树时有意义)
  • 树林
    m(m>=0)棵互不相交的树的集合
  • 一棵非空树是一个二元组Tree=(r,F),其中
    • r是树的根结点
    • F是m(m>=0)棵子树构成的树林
    • F=(T1,T2...T1)。其中T1称为根r的第i棵子树(有序树情况。对于无序树F是一个集合,F={T1,T2...T1})
  • 注意树与树林的关系
    • 树由根域子树树林构成
    • 树林由一集树组成
    • 树和树林可以相互递归定义

三、二叉树

  • 特点是与每个结点关联的子结点至多有两个(可为0,1,2)
  • 每个结点的子结点关联有位置关系

1.定义

  • 二叉树是结点的有限集合,该集合或为空集,或由一个根元素和两棵不相交的二叉树组成(递归定义)
  • 二叉树的两棵子树分别称作它的左子树和右子树

2.特点

  • 一个结点至多有两棵子树
  • 子树有左右之分(因此二叉树与树有不同结构,不是树的特殊情况)

3.基本形态

  • 空二叉树、只有根结点、只有左子树、只有右子树、左右子树都不空
  • 由于分左右子树,即使只有一棵子树也要明确说明是左还是右,画二叉树时要明确地把子树画在左边或右边

4.概念

  • 可沿用树的许多概念
  • 满二叉树:树中每个分支结点(非叶结点)都有两棵非空子树
  • 完全二叉树:除最下两层外,其余结点度数都是2,如果最下一层的结点不满,则所有空位都在右边,左边没有空位
a.扩充二叉树
  • 原二叉树的最小结点扩充,使原树中所有结点的度数都变成2
  • 扩充二叉树新增结点(称其为外部结点)的个数比原树结点(称其为内部结点)的个数多1
    • 如果原树只有一个结点,结论显然成立
    • 如果原树包含根结点r和左右子树
  • 扩充二叉树性质(其中n是内部结点的个数):E=l+2n
    • E是扩充二叉树的外部路径长度:扩充二叉树里从根到各外部结点的路径长度之和
    • l是扩充二叉树的内部路径:扩充二叉树从根到各内部结点的路径长度之和

5.性质

  • 非空二叉树第i层上至多有2i个结点(i>=0)
  • 高度为k的二叉树至多有2k-1个结点(k>=0)
  • 对任何非空二叉树T,若其叶结点个数为n0,度数为2的结点个数为n2,则n0=n2+1
  • n个结点的完全二叉树的高度k=[log2(n+1)]
  • 满二叉树里叶结点比分支节点多一个
  • 如果n个结点的完全二叉树按层次按从左到右的顺序从0开始编号,对任一结点i(0<=i<=n-1)都有:
    • 序号0的结点是根;对于i>0,其父结点是(i-1)/2
    • 2*i+1<=n,其左子结点序号为2*i+1;否则它无左子结点
    • 2*2+1<=n,其右子结点序号为2*i+2;否则它无右子结点
  • 完全二叉树的一个重要性质:
    • 不需要另外保存其他信息,直接根据元素的下标就可以找到一个结点的子结点或者父结点(并确定二叉树结构)
    • 使其可以方便地存入一系列连续位置
    • 一般二叉树不能方便地映射到线性结构,完全二叉树到线性结构有定义非常自然的双向映射,可以方便地从其线性结构恢复完全二叉树
  • 对于n个结点的二叉树:
    • 如果足够丰满整齐,树中最长路径的长度将为O(logn)
    • 如果比较畸形,最长路径的长度可能为O(n)

6.操作

  • 创建二叉树
  • 一棵二叉树或为空,或是两棵已有二叉树和要存在树根结点的一项数据,构造起的根结点代表构造出的二叉树:BiTree(dat,left,right)
  • 判断树空:is_empty(bitree)
  • 访问操作:
    • 访问二叉树的根结点数据元素:data()
    • 取得一棵二叉树的左右子树:right()left()

7.实现

  • 考虑list实现,也可用于实现一般的树
a.采用如下设计
  • 空树用[]表示
  • 非空二叉树用包含三个元素的表[d,l,r]表示。其中d为存在根结点的元素,lr是两棵子树
  • 显然,这种设计是一种递归结构,也就是前面的嵌套括号表示
b.程序实现
def BiTree(data,left,right)
    return [data,left,right]

def is_empty(bitree):
    return bitree == []

def root(bitree):
    return bitree[0]

def letfch(bitree):
    return bitree[1]

def rightch(bitree):
    return bitree[2]

def set_root(bitree, data):
    bitree[0] = data

def set_left(bitree, left):
    bitree[1] = left

def set_right(bitree, right):
    bitree[2] = right
最后由 oucb 编辑于2016年06月23日 11:12