树结构中的概念(2) 没有子树的结点称作树叶或终端结点 非终端结点称为分支结点 个结点的子树的个数称为度数 根结点的层数为0,其它任何结点的层数 等于它的父结点的层数加1 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 16
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 树结构中的概念(2) 没有子树的结点称作树叶或终端结点 非终端结点称为分支结点 一个结点的子树的个数称为度数 根结点的层数为0，其它任何结点的层数 等于它的父结点的层数加1
树结构中的概念(3) 有序树在树T中如果子树T,T2,…, T的相对次序是重要的,则称树T为有向 有序树,简称有序树。 在有序树中可以称T1是根的第一棵子树,T2 是根的第二棵子树,等等 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 17
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 树结构中的概念(3) 有序树 在树T中如果子树T1，T2，…， Tm的相对次序是重要的，则称树T为有向 有序树，简称有序树。 在有序树中可以称T1是根的第一棵子树，T2 是根的第二棵子树，等等
512森林与二叉树的等价转换 森林( orest)森林是零棵或多 棵不相交的树的集合(通常是有 序集合)。 删去树根,树就变成森林 加上一个结点作树根,森林就变 成树 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 18
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 5.1.2 森林与二叉树的等价转换 森林(forest) 森林是零棵或多 棵不相交的树的集合(通常是有 序集合)。 删去树根，树就变成森林 加上一个结点作树根，森林就变 成树
森林与二叉树的等价转换(续) 在树或森林与二叉树之间有一个自然 的一一对应的关系。 任何森林都唯一地对应到一棵二叉树;反 过来,任何二叉树也都唯一地对应到一个 森林。 树所对应的二叉树里 结点的左子结点是它在原来树里的第 个丝 子结点 右子结点是它在原来的树里的下一个兄弟 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 19
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 森林与二叉树的等价转换(续) 在树或森林与二叉树之间有一个自然 的一一对应的关系。 任何森林都唯一地对应到一棵二叉树；反 过来，任何二叉树也都唯一地对应到一个 森林。 树所对应的二叉树里 一个结点的左子结点是它在原来树里的第 一个子结点 右子结点是它在原来的树里的下一个兄弟
图示:森林与二叉树 B G K F K 12 G 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 20
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 图示：森林与二叉树 G F D H J T2 E A B1 T11 T12 T1 C K G F H D C A B1 K E J