氏图到嵌套括号表示的转化 树的定义 从最外依次将示集合 的方福转化牺号对 ■树是包括n个结点的有限集合T(n1),使得 有一个特别标出的称作根的蜡点 除根以外的其它结点被分成m个m20不相交的靠合T o⊙@o⊙@ T2,…,Tm,而且这些集合的每一个又都是树。树T1 T2,…,Tm称作这个根的子树 ■这个定义是递归的,我们用子树来定义树:只包 (A(BDOE(OF(C(GHD 结点的树必然仅由根组成,包含n>1个结 点的树借助于少于n个结点的树来定义 北大啦 机新有,食 大息单 有,盛 树结构中的概念(1) 树结构中的概念(2) 着<k,k>∈N,则称k是k!的父结点(或称“父 母),而k′则是k的子结点(或“儿子”、“子女”) 没有子树的结点称作树叶或终端结点 着有序对<k,k′>及<k,k">∈N,则称k’和k 为兄弟 非终端结点称为分支结点 :若有一条由k到达k的陪径,则称k是k3的祖先,k是k 一个结点的子树的个数称为度数 的子孙 树形结构中,两个结点的有序对,称作连接这两结点的 根结点的层数为0,其它任何结点的层数 等于它的父结点的层数加1 北大位 张 新有,究 张铭鷾 叔有,印鱼究 树结构中的概念(3) 512森林与二叉树的等价转换 有序树在树T中如果子树T1,T2,…, 森林( forest)森林是零棵或多 Tm的相对次序是重要的,则称树T为有向 棵不相交的树的集合(通常是有 序集合)。 有序树,简称有序树。 删去树根,树就变成森林 在有序树中可以称T1是根的第一棵子树,T2 加上一个结点作树根,森林就变 是根的第二棵子树,等等 成树 物歌抗 新有,食邮岛究 张铭·票有,气即必究3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 文氏图到嵌套括号表示的转化 A B C D E I J G H F (A(B(D)(E(I)(J)) (C (F)) (G)(H))) 从最外层依次将表示集合 的方框转化成括号对 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 树的定义 „ 树是包括n个结点的有限集合T（n≥1），使得： „ 有一个特别标出的称作根的结点 „ 除根以外的其它结点被分成m个(m≥0)不相交的集合T1， T2，…，Tm，而且这些集合的每一个又都是树。 树T1， T2，…，Tm称作这个根的子树 „ 这个定义是递归的，我们用子树来定义树：只包 含一个结点的树必然仅由根组成，包含n>1个结 点的树借助于少于n个结点的树来定义 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 树结构中的概念(1) „ 若<k，k′>∈N，则称k是k′的父结点（或称“父 母”），而k′则是k的 子结点(或“儿子”、“子女”) „ 若有序对<k，k′>及<k，k″>∈N，则称k′和k″ 互为兄弟 „ 若有一条由 k到达ks的路径，则称k是ks的祖先，ks是k 的子孙 „ 树形结构中，两个结点的有序对，称作连接这两结点的 一条边 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 树结构中的概念(2) „ 没有子树的结点称作树叶或终端结点 „ 非终端结点称为分支结点 „ 一个结点的子树的个数称为度数 „ 根结点的层数为0，其它任何结点的层数 等于它的父结点的层数加1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 树结构中的概念(3) „ 有序树 在树T中如果子树T1，T2，…， Tm的相对次序是重要的，则称树T为有向 有序树，简称有序树。 „ 在有序树中可以称T1是根的第一棵子树，T2 是根的第二棵子树，等等 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 5.1.2 森林与二叉树的等价转换 „ 森林(forest) 森林是零棵或多 棵不相交的树的集合(通常是有 序集合)。 „ 删去树根，树就变成森林 „ 加上一个结点作树根，森林就变 成树