【6.1】树的定义和基本术语

一、 树和森林

树 (tree) 是包括 n 个结点的有限集合 T(n ≥ 1):

  • 有且仅有一个特定的结点,称为 根 (root)
  • 除根以外的其他结点被分成 m 个 (m ≥ 0) 不相交的 有限集合 T1,T2,…,Tm,而每一个集合又都是树 ,称为 T 的子树 (subtree)
  • 有向有序树:子树的相对次序是重要的
  • 度为 2 的有序树并不是二叉树
  • 第一子结点被删除后,第二子结点自然顶替成为第一

###1.1 树的逻辑结构

包含n个结点的有穷集合 K (n>0),且在 K上 D 定义了一个关系 r,关系 r 满足以下条件:

  • 有且仅有一个结点 k0∈K,它对于关系 r 来说没有 前驱。结点 k0 称作树的根
  • 除结点 k0 外,K中的每个结点对于关系 r 来说都 有且仅有 一个前驱

例如,

结点集合 K={ A,B,C,D,E,F,G,H,I,J }

K 上的关系 r = { <A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<C,H>,<E,I>,<E,J> }

1.2 树的相关术语

结点:

子结点、父结点、最左子结点 :

若 <k,k′> ∈ r,则称 k 是 k′ 的父结点(或称“父母”) ,而 k′ 则是 k 的 子结点 (或“儿子”、“子女”)

兄弟结点前兄弟、后兄弟:

若有序对 <k,k′>及 <k,k′′>∈ r,则称 k′和 k′′互为兄弟

分支结点、叶结点:

  • 没有子树的结点称作 叶结点(或树叶、终端结点)
  • 非终端结点称为 分支结点

两个结点的有序对,称作 边

路径、路径长度

除结点k0外的任何结点 k∈K,都存在一个结点序列 k0,k1,…,ks,使得 k0 就是树根,且 ks=k,其 中有序对 $<ki-1,ki>∈ r (1≤i≤s)$ 。该序列称为从根 到结点 k 的一条路径,其路径长度为 s (包含的边数)

祖先、后代:
  • 若有一条由 k 到达 ks 的路径,则称k 是 ks 的祖先,ks 是 k 的子孙
度数:

一个结点的子树的个数

层数:

根为第 0 层,其他结点的层数等于其父结点的层数加 1

深度:

层数最大的叶结点的层数

高度:

层数最大的叶结点的层数加 1

1.3 树形结构的各种表示法

  • 树形表示法
  • 形式语言表示法
  • 文氏图表示法
  • 凹入表表示法
  • 嵌套括号表示法

树形表示法:

形式语言表示法:

树的逻辑结构是:

结点集合K={A,B,C,D,E,F,G,H,I,J}
K上的关系N={<A,B>,<A,C>,<B,D>, <B,E>,<B,F>,<C,G>,
<C,H>,<E,I>,<E,J>}

文氏图表示法

嵌套括号表示法

(A(B(D)(E(I)(J))(F))(C(G)(H)))

文氏图到嵌套括号表示的转化

凹入表表示法

二、森林与二叉树的等价转换

森林(forest):零棵或多棵 不相交 的 树的集合(通常是有序)

树与森林的对应:

  • 一棵树,删除树根,其子树就组成了森林
  • 加入一个结点作为根,森林就转化成了一棵树

森林与二叉树之间可以相互转化,而 且这种转换是一一对应的

  • 森林的相关操作都可以转换成对二叉树的操作

森林与二叉树如何对应?

森林转化成二叉树的形式定义

有序集合 F = {T1,T2,…,Tn} 是树 T1,T2,…,Tn 组成的森林,递归转换成二叉树B(F):

  • 若F为空,即n=0,则B(F)为空
  • 若 F 非空,即 n > 0,则 B(F) 的根是森林中第一棵树 T1 的根 W1,B(F) 的左子树是树 T1 中根结点 W1的子树森林 F = {T11,…,T1m} 转换成的二叉树B(T11,…,T1m); B(F)的右子树是从森林 F’ = {T2,…,Tn} 转换而成的二叉树

森林转化为二叉树

二叉树转化成森林或树的形式定义

设B是一棵二叉树,root是 B 的根,BL 是 root 的左子树,BR 是 root 的右子树, 则对应于二叉树B的森林或树 F(B) 的形式定义是:

  • 若 B 为空,则 F(B) 是空的森林
  • 若 B 不为空,则 F(B)是一棵树T1加上森林 F(BR), 其中树 T1 的根为 root,root 的子树为 F(BL)

思考:

  1. 树也是森林吗?
  2. 为什么要建立二叉树与森林的对应关系?

三、树的抽象数据类型

四、树的遍历

森林的遍历

遍历森林vs遍历二叉树

  • 先根次序遍历森林
    • 前序法遍历二叉树
  • 后根次序遍历森林
    • 按中序法遍历对应的二叉树
  • 中根遍历?
    • 无法明确规定根在哪两个子结点之间

宽度优先遍历森林

宽度优先遍历

  • 也称广度优先遍历
  • 或称层次遍历
  1. 首先依次访问层数为0的结点
  2. 然后依次访问层数为1的结点
  3. 直到访问完最下一层的所有结点

广度优先遍历森林

思考

  1. 能否直接用二叉树前序遍历框架来编写森林的先根遍历?
  2. 能否直接用二叉树中序遍历框架来编写森林的后根遍历?
  3. 森林的非递归深搜框架?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学