tree
兴趣遍地都是，专注和持之以恒才是真正稀缺的。

一、树的定义

树是n(n>=0)个结点的有限子集。n=0时称为空树。在任意一颗非空树中，（1）有且仅有一个特定的称为根的结点。（2）n>1时，其余结点可分为m（m>0）个互不相交的有限集T1，T2,……Tm，其中每一个集合本身又是一棵树，并且称为根的子树。

需要强调的是：

n>0时根结点是唯一的，不可能存在多个根结点。
m>0时，子树的个数没有限制，但它们一定是不相交的。

1、结点分类

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（degree）。度为0的结点称为叶结点（Leaf）或终端节点；度不为0的结点称为非终端结点或分支结点。除根结点外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。如某个树中结点的度的最大值是D结点，度为3，所以树的度也为3。

2、结点间关系

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

3、树的其他相关概念

结点的层次（Level）从根开始定义，根为第一层，根的孩子为第二层。
双亲在同一层的结点互为堂兄弟。
树中结点的最大层次称为树的深度（Depth）或者高度。
如果树中结点的各子树看成从左至右是有次序的，不能互相交换的，则称该树为有序树，否则称为无序树。
森林（Forest）树m（m>=0）棵互不相交的树的合集。

4、线性表与树的对比

线性结构

第一个数据元素：无前驱
最后一个数据元素:无后继
中间元素：一个前驱一个后继

树结构

根结点：无双亲，唯一
-叶结点：无孩子，可以多个
中间结点：一个双亲多个孩子

二、树的抽象数据类型

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是树的非叶结点，则返回它的最左孩子，否则返回空
    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

三、树的存储结构

双亲表示法、孩子表示法、孩子兄弟表示法。

1、双亲表示法

定义

以一组连续空间存储树的结点，同时每个结点中，附设一个指示器指示其双亲结点到链表中的位置。如下图
tree1

data是数据域：存储结点的数据信息。parent是指针域：存储该结点的双亲在数组中的下标。

双亲表示法的结点结构定义代码

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

因为跟结点是没有双亲的，所以，我们约定根结点的位置域为-1。那么树
tree1

的双亲表示法则如下表所示
tree1

这样子的存储结构，可以根据结点的parent很容易找到它的双亲结点，所以时间复杂度为O(1)，当parent为-1时，则表示找到了树的根结点。可如果要知道结点的孩子的话，却是仍要遍历整个结构才行。

改进1：关于孩子结点

因为想知道某个结点孩子的话还是需要遍历整个结构，所以，在这边可以改进一下，增加一个最左孩子的域，
tree1

这样对于有0-1个孩子结点的，就能轻易找到了，对于有两个孩子的，知道了长子是谁，另一个就是次子了。

改进2：关于兄弟结点

可以增加一个右兄弟域来体现兄弟关系，每一个节点如果它存在右兄弟，则记录下右兄弟的下标。如果不存在则赋值为-1，如
tree1

如果节点孩子多，又需要关注双亲，关注结点孩子，关注结点东西，且对时间遍历要求还比较高，还可以把此结构拓展为双亲域，长子域，右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否合适、是否方便，时间复杂度好不好等。

2、孩子表示法

每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。树每个结点的度（孩子的个数）是不同的，有两种方案解决。

指针域的个数就等于树的度。树的度是树各个结点度的最大值。

如果树的各结点的度差异过大，则会造成空间浪费，即很多的指针域是空的。
每个结点的指针域的个数等于该结点的度，取一个位置来存储结点指针域的个数。

这样就克服了第一种方案浪费空间的缺点，但由于各结点的链表是不相同的结构，且要维护结点的度的数值，运算上就多了时间的损耗。

为了遍历整棵树，把每个结点放到一个顺序存储结构数组中是合理的，但结点的度是不确定的，因此，我们再对每个节点的孩子建立一个单链表体现它们的关系。这就是孩子表示法。

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

如图：
tree1

为此需要两种结点结构，一个是孩子链表的孩子结点：
tree1

child是数据域，next是指针域。
一个是表头结点：
tree1
data是数据域，firstchild是头指针域，存储该结点的孩子链表的头指针。

孩子结点表示法的结构定义代码

/*树的孩子表示法结构定义 */
#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;

这样的结构查找某个结点孩子，或者某个结点兄弟，只需要查找这个结点的孩子单链表即可，对于整棵树遍历只需对头结点的数组循环即可。
如果想知道某个结点的双亲就比较麻烦了，需要整棵树遍历才行。也可以把双亲表示法和孩子表示法综合一下，这种方法称为双亲孩子表示法，算是孩子表示法的改进。

3、孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

结点结构如下：

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

typedef struct CSNode{
    TElemType data;
    struct CSNode *firstchild, *rightsib;
}CSNode,*CSTree;

示意图:

需要的情况下，也完全可以再增加一个parent指针域来解决快去查找双亲的问题。