《大话数据结构》笔记06-树

树的定义

树（Tree）是 $n(n≥0)$ 个结点的有限集。$n=0$ 时称为空树。在任意一棵非空树中：
（1）有且仅有一个特定的称为根（Root）的结点；
（2）当 $n>1$ 时，其余结点可分为 $m(m>0)$ 个互不相交的有限集 $T_1、T_2、......、T_m$，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree），如图所示：

当$m>1$时，子树没有限制，但他们一定不能相交。

结点分类

结点拥有的子树数称为结点的度（Degree）。
度为 0 的结点称为叶节点（Leaf)或终端结点。
度不为 0 的结点称为非终端结点或分支结点。
除根结点之外，分支结点也称为内部结点。
树的度是树内各结点的度的最大值。

上图中这棵树结点的度的最大值是结点 D 的度为 3，所以树的度也为 3。

结点间关系

结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称为兄弟（Sibling）。结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

树的其他相关概念

结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树就在第l+1层。其双亲在同一层的结点互为堂兄弟。显然下图中的D、E、F是堂兄弟，而G、H、I与J也是堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度，当前树的深度为4。

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林（Forest）是 $m（m≥0）$ 棵互不相交的树的集合。

对比线性表与树的结构，它们有很大的不同。

树的抽象数据类型

ADT 树(tree)
Data
    树是由一个根结点和若干棵子树构成。树种结点具有相同数据类型及层次关系。
Operation
    InitTree(*T): 构造空树T。
    DestroyTree(*T): 销毁树T。
    CreateTree(*T, definition):按definition中给出树的定义来构造树。
    ClearTree(*T): 若树T存在，则将树T清为空树。
    TreeEmpty(T): 若T为空树，返回true，否则返回false。
    TreeDepth(T): 返回T的深度。
    Root(T): 返回T的根结点。
    Value(T, cur_e): cur_e是树T中的一个结点，返回此结点的值。
    Assign(T, cur_e, value): 跟树T的结点cur_e赋值为value。
    Parent（T, cur_e): 若cur_e是树T的非根结点，则返回它的双亲，否则返回空。
    LeftChild(T, cur_e): 若cur_e是树T的非根结点，则返回它的最左孩子，否则返回空。
    RightSibling(T, cur_e): 若cur_e有右兄弟，则返回它的右兄弟，否则返回空。
    InsertChild(*t, *p, i, c): 其中p指向树T的某个结点，i为所指结点p的度加上1，非空树c与T不相交，操作结果为插入c为树T中p指结点的第i棵子树。
    DeleteChild(*T, *p, i): 其中p指向树T的某个结点，i为所指结点p的度，操作结果为删除T中p所指结点的第i棵树。
endADT

树的存储结构

双亲表示法

在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。

其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标。
由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1。

/* 树的双亲表示法结点结构定义 */
#define MAX_TREE_SIZE 100
typedef int TElemType; /* 树结点的数据类型，整形 */
typedef struct PTNode /* 结点结构 */
{
    TElemType Data; /* 结点数据 */
    int parent; /* 双亲位置 */
} PTNode;
typedef struct /* 树结构 */
{
    PTNode nodes[MAX_TREE_SIZE]; /* 结点数组 */
    int r, n; /* 根的位置和结点数 */
} PTree;

优点：这样的存储结构，我们可以根据结点的parent指针很容易找到它的双亲结点。
缺点：可如果我们要知道结点的孩子是什么，对不起，请遍历整个结构才行。

改进一下，我们增加一个结点最左边孩子的域，不妨叫它长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1

另外一个问题场景，我们很关注各兄弟之间的关系，双亲表示法无法体现这样的关系，那我们怎么办？嗯，可以增加一个右兄弟域来体现兄弟关系，也就是说，每一个结点如果它存在右兄弟，则记录下右兄弟的下标。同样的，如果右兄弟不存在，则赋值为-1。

但如果结点的孩子很多时，超过了 2 个。我们又关注结点的双亲、又关注结点的孩子、还关注结点的兄弟，而且对时间遍历要求还比较高，那么我们可以把此结构扩展为有双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计是否合理，取决于基于该存储结构的运算是否合适、是否方便，时间复杂度好不好等。

孩子表示法

每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。

孩子表示法:把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中，如图所示。

data 是数据域 存储某个结点的数据信息。
firstchild 是头指针域，存储该节点的孩子链表的头指针。
child 是数据域，用来存储某个结点在表头数组中的下标。
next 是指针域，用来存储指向某个结点的下一个孩子结点的指针。

/* 树的孩子表示法结构定义 */
#define MAX_TREE_SIZE 100
typedef struct CTNode { /* 孩子结点 */
    int child;
    struct CTNode *next;
} *ChildPtr;

typedef struct { /* 表头结构 */
    TElemType data;
    ChildPtr firstchild;
} CTBox;

typedef struct { /* 树结构 */
    CTBox nodes[MAX_TREE_SIZE]; /* 结点数组 */
    int r, n; /* 根的位置和结点数 */
} CTree;

这样的结构对于我们要查询某个结点的某个孩子，或者找某个结点的兄弟，只需要查询这个结点的孩子单链表即可。对于遍历整个树也是很方便的，对于结点的数组循环即可。

也可以把双亲表示法和孩子表示法综合一下，如图

孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向改结点的第一个孩子和此结点的右兄弟。
这种表示法，给查找某个结点的某个孩子带来了方便。

data 是数据域
firstchild 是指针域，存储该结点的第一个孩子结点的存储地址
rightsib 是指针域，存储该结点的右兄弟结点的存储地址。

/* 树的孩子兄弟表示法结构定义 */
typedef struct CSNode {
    TElemType data;
    struct CSNode *firstchild, *rightsib;
} CSNode, *CSTree;