术语 | 描述 |
---|---|
树的结点 | 由一个数据元素及关联其子树的边所组成。 |
结点的边 | 实体与实体之间的逻辑关系 |
结点的==路径== | 从根结点到该结点所经历的结点和分支的顺序排列。 结点J的路径:A-->C-->G-->J |
路径的长度 | 结点路径中所包含的分支数。例如:结点J的路径长度为3. |
结点的==度== | 该结点所拥有的子树的数目。例如:结点A的度为3,结点B的度为1 |
树的==度== | 树中所有结点度的最大值。 |
叶结点 | 树中度为0的结点,也称为终端结点。 |
分支结点 | 树中度不为0的结点,也称为非终端结点。除叶子结点之外的所有结点都是分支结点。 |
孩子结点 | 结点的子树的根节点,也称为子节点。结点A的孩子结点是BCD |
双亲结点 | 某结点有孩子结点,则该结点称为孩子的双亲结点,也称为父节点。 |
子孙结点 | 该结点所有子树中的任意结点。 |
祖先结点 | 该结点的路径中除此结点之外的所有结点。 |
兄弟结点 | 具有同一个双亲的结点。 |
结点的==层次== | 规定树中根节点的层次为0,其他结点的层次是双亲结点的层次数加1,结点P层次数为4 |
树的==深度== | 树中所有结点的层次数的最大值加1。(a) 深度为1 (b)深度为3 (c)深度为5 |
有序树 | 各节点的所有子树之间从左到右有严格的次序关系,不能交换。 |
无序树 | 树中各节点的所有子树之间没有严格的次序关系。从左到右没有次序之分。 |
森林 | 由m(m>=0)棵互不相交的树所构成的集合 |
有序树
。1)特性1:i层最多结点数 2^i
2)特性2:最多结点个数 2^h-1
3)特性3:叶子结点关系 n_0 = n_2 + 1
4)特性4:深度 ⌊log2n⌋ + 1
5)特性5:判断是否
1)顺序存储结构
2)链式存储结构