树

树 #

树的相关概念 #

子树: 除了根节点外，每个子节点都可以分为多个不相交的子树。
(图二)孩子与双亲: 若一个结点有子树，那么该结点称为子树根的"双亲"，子树的根是该结点的"孩子"。在图一中，B、H是A的孩子，A是B、H的双亲。
兄弟: 具有相同双亲的节点互为兄弟，例如B与H互为兄弟。节点的度: 一个节点拥有子树的数目。例如A的度为2，B的度为1，C的度为3.
叶子: 没有子树，也即是度为0的节点。
分支节点: 除了叶子节点之外的节点，也即是度不为0的节点。
内部节点: 除了根节点之外的分支节点。
层次: 根节点为第一层，其余节点的层次等于其双亲节点的层次加1.
树的高度: 也称为树的深度，树中节点的最大层次。
有序树: 树中节点各子树之间的次序是重要的，不可以随意交换位置。
无序树: 树种节点各子树之间的次序是不重要的。可以随意交换位置。森林: 0或多棵互不相交的树的集合。例如图二中的两棵树为森林。