树结构中的概念 若<k,k>∈N,则称k是k的父结点(或称“父 母”),而k则是k的子结点(或“儿子”、“子女”) 若有序对<k,k>及<k,k">∈N,则称k和k"互为 兄弟 若有一条由k到达k的路径,则称k是k的祖先,k是k 的子孙 树形结构中,两个结点的有序对,称作连接这两结点的 条边 北京大学信息学院 版权所有,转载或翻印必究 Page 11
北京大学信息学院 ©版权所有，转载或翻印必究 Page 11 树结构中的概念 ◼ 若<k，k′>∈N，则称k是k′的父结点（或称“父 母”），而k′则是k的 子结点(或“儿子” 、 “子女”) ◼ 若有序对<k，k′>及<k，k″>∈N，则称k′和k″互为 兄弟 ◼ 若有一条由 k到达ks的路径，则称k是ks的祖先，ks是k 的子孙 ◼ 树形结构中，两个结点的有序对，称作连接这两结点的 一条边
树结构中的概念 没有子树的结点称作树叶或终端结点 非终端结点称为分支结点 个结点的子树的个数称为度数 根结点的层数为0,其它任何结点的层数 等于它的父结点结点的层数加1 北京大学信息学院 版权所有,转载或翻印必究 Page 12
北京大学信息学院 ©版权所有，转载或翻印必究 Page 12 树结构中的概念 ◼ 没有子树的结点称作树叶或终端结点 ◼ 非终端结点称为分支结点 ◼ 一个结点的子树的个数称为度数 ◼ 根结点的层数为0，其它任何结点的层数 等于它的父结点结点的层数加1
树结构中的概念 有序树在树T中如果子树T1,T2,…, Tm的相对次序是重要的,则称树T为有向 有序树,简称有序树。 在有序树中可以称T1是根的第一棵子树,T2 是根的第二棵子树,等等 北京大学信息学院 版权所有,转载或翻印必究 Page 13
北京大学信息学院 ©版权所有，转载或翻印必究 Page 13 树结构中的概念 ◼ 有序树 在树T中如果子树T1，T2，…， Tm的相对次序是重要的，则称树T为有向 有序树，简称有序树。 ◼ 在有序树中可以称T1是根的第一棵子树，T2 是根的第二棵子树，等等
森林与树 森林( forest)森林是零棵或多棵不相交的树 的集合(通常是有序集合)。 自然界的树和森林是不同的概念,而数据结构 的树和森林只有微小的差别。删去树根,树就 变成森林。加上一个结点作树根,森林就变成 树 北京大学信息学院 版权所有,转载或翻印必究 Page 14
北京大学信息学院 ©版权所有，转载或翻印必究 Page 14 森林与树 ◼ 森林(forest) 森林是零棵或多棵不相交的树 的集合(通常是有序集合)。 ◼ 自然界的树和森林是不同的概念，而数据结构 的树和森林只有微小的差别。删去树根，树就 变成森林。加上一个结点作树根，森林就变成 树
森林与二叉树的等价转换 在树或森林与二叉树之间有一个自然的一一对应的关系。 任何森林都唯一地对应到一棵二叉树;反过来,任何二叉树也 都唯一地对应到一个森林。 树所对应的二叉树里 个结点的左子结点是它在原来树里的第一个子结点 右子结点是它在原来的树里的下一个兄弟 北京大学信息学院 版权所有,转载或翻印必究 Page 15
北京大学信息学院 ©版权所有，转载或翻印必究 Page 15 森林与二叉树的等价转换 ◼ 在树或森林与二叉树之间有一个自然的一一对应的关系。 ◼ 任何森林都唯一地对应到一棵二叉树；反过来，任何二叉树也 都唯一地对应到一个森林。 ◼ 树所对应的二叉树里 ◼ 一个结点的左子结点是它在原来树里的第一个子结点 ◼ 右子结点是它在原来的树里的下一个兄弟