7-8根树及其应用
7-8 根树及其应用
根树 1、有向树 定义7-8.1如果一个有向图在不考虑边的方向时 是一棵树,那么,该有向图称为有向树。 He
一、根树 1、有向树 定义7-8.1 如果一个有向图在不考虑边的方向时 是一棵树，那么，该有向图称为 有向树
2、根树 定义7-8.2一棵有向树,如果恰有一个 结点的入度为0,其余所有结点的入度都为1, 则称为根树( Rooted tree)。入度为0的结点称 为T的树根。出度为0的结点称为树叶,出度 不为0的结点称为分支点或内点。 根树的画法有:树根在下,向上生长; 树根在上,向下生长
2、根树 定义7-8.2 一棵有向树,如果恰有一个 结点的入度为0，其余所有结点的入度都为1, 则称为根树(rooted tree)。入度为0的结点称 为T的树根。出度为0的结点称为树叶，出度 不为0的结点称为分支点或内点。 根树的画法有：树根在下，向上生长； 树根在上，向下生长
习惯把有向树的根画在最上方,边的箭头全指 向下,则可以省略全部箭头,树根到一个结点的有 向通路的长度称为该点的层数。所有结点的最大层 数称为树高。 8 10 U10
习惯把有向树的根画在最上方，边的箭头全指 向下，则可以省略全部箭头，树根到一个结点的有 向通路的长度称为该点的层数。所有结点的最大层 数称为树高
3、子树 定义7-83:任一结点v及其后代导出的子图 称为根树的子树。 定义783根树包含一个或多个结点,这些结 点中的某一个称为根,其他所有结点被分成有限个 子根树
3、子树 定义7-8.3：任一结点v及其后代导出的子图 称为根树的子树。 定义7-8.3 根树包含一个或多个结点,这些结 点中的某一个称为根,其他所有结点被分成有限个 子根树