06.01 树及其结点的定义

树的定义 树是由 n 个结点组成的。当 \(n=0\) 时为空树。 - 在非空树中，只有一个根节点 (root)。如图 A 结点 - 当 \(n>1\) 时，也就是根节点还有结点，而多出来的结点本身也是一棵树；D 是一棵树，单看 G、H、I 也是一棵树。如下图所示： - - - 子树互不相交，也就是 D 没有连接 E

结点分类 结点拥有的子树是结点的度 (Degree) 度为 0 的结点成为叶/终端节点 (Leaf)；不为 0 时称为分支/内部结点 树的度是树内各节点的度的最大值

结点间关系 根是结点的双亲； 带有子树的子结点是结点的孩子； 同层的结点互称为堂兄弟； 节点的祖先：从根到该节点所经分支上的所有节点；H 的祖先是：ABD

结点的层次(Level)：从根开始为第一层，直到终端结点

最大层次称为树的深度 (Depth)