Question

树的概述

• 树是 n 个结点的有限集。n=O 时称为空树，在任意一棵非空树中:有且仅有一个特定的称为根(Root) 的结点:
• 当 n> 1 时，其 余结点可分为 m(m>O) 个互不相交的有限集 T1 T2、 ......Tm, 其中每一个集合本身又是一棵树，并且称为根的子树。
• 子树的个数没有限制，但它们一定是互不相交的

• 树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。
• 度为 0 的结点称为叶结点(Leaf) 或终端结点;
• 度不为 0 的结点称为非终端结点或分支结点 。
• 除根结点之外，分支结点也称为内部结点。树的度，是树内各结点的度的最大值 。

因为这棵树结点的度的最大值是结点 D 的度，为 3,所以树的度也为 3

树的存储结构

双亲表示法

• 我们人可能因为种种原因，没有孩子，但无论是谁都不可能是从石头里蹦出来的，所以是人一定会有父母。树这种结构也不例外，除了根 结点外，其余每个结点，它不一定有孩子，但是一定有且仅有一个双亲。

• 假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位，也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里

由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1,这也就意味着，我们所有的结点都存 有包双亲的位置。

这样的存储结构，我们可以根据结点的 parent 指针很容易找到色的双亲结点，所 用的时间复杂度为 0(1),直到 parent 为一 1 时，表示找到了树结点的根。