树的定义

树是一种一对多的数据结构。在一任意非空的树中，有且仅有一个根结点，其余结点可分为互不相交的有限集，每个集合本身又是一棵树，称为根的子树。下图的结构子树之间相交了，就不符合树的定义。

结点的分类：
①结点拥有的子树个数称为结点的度。
②度为0的结点称为叶结点或终端结点。
③度不为0的结点称为非终端结点或分支结点，分支结点也称为内部结点。
④树的度是树内各结点的度的最大值。
树的层次，从根结点开始定义，根为第一层，根的孩子为第二层…若某个结点在第n层，则他的孩子结点在第n+1层，其中树的最大层次称为树的深度。

有序树：树中结点的各子树，从左到右是有次序的，不能互换。
森林：n课互不相交的树的集合，对于树中的每个结点而言，子树的集就是森林。
根结点：无双亲，唯一。
叶结点：无孩子，可以有多个。
中间结点：一个双亲，多个孩子。

树的存储结构

有三种表示方法：双亲表示法，孩子表示法，兄弟表示法。

双亲表示法
假设用一组连续的空间存储树的结点，没一个结点中，设一个表示双亲位置的指示器。

data	parent

data树数据域，存储结点信息。parent是指针域，存储双亲在数组中的下标。下面定义结构体：

#define MAXSIZE 100
//结点结构
typedef struct PTNode
{int data;//结点数据int parent;//双亲位置
}PTNode;
//树的结构
typedef struct	
{PTNode nodes[MAXSIZE];//结点数组int r,n;//根的位置，结点数
}

例图1

这种结构，可以根据parent指针找到，该结点的双亲结点，时间复杂度为O(1)，当parent的值为-1时，表示找到了根结点。

当我们要找该结点的孩子结点的时候，我们可以在给这个结构加上一个指向第一个孩子的指针域 firstchild。当我们知道了第一个孩子的位置后，自然可以得到其他孩子的位置。

当我们关注兄弟之间的关系时候，我们可以在加上一个指向右兄弟的指针域rightsib，当一个结点右兄弟，则记录下右兄弟的下标，没有则用-1表示。

孩子表示法
树中每个结点可能有多个子树，可用多重链表，每个节点有多个指针域，每个指针域指向一颗子树的结点。取一个位置存储结点指针域的个数。

对于上面所给例图1的树，用该结构表示
这种结构，节省了空间。但是由于各个结点是不相同的，结合形成一个链表是比较麻烦的，在运算上就会消耗大量的时间。
接下来介绍一种比较完善全面的孩子表示法，把每个结点的孩子结点排列起来，以单链表作为存储结构，n个结点有n个孩子链表，如果是叶子节点则该链表为空，然后把中n个头指针结点组成一个线性表，放进一维数组里面。

孩子结点：

child	next

child是数据域，存放一维数组的下标，next是指针域指向该结点的下一个孩子结点的指针。
表头数组：

data	firstchild

data是数据域存放结点存储的数据信息，firstchild是头指针域，存储该节点的孩子链表。

下面是对这两个结构体的定义

#DEFINE MAXSZIE 1000
typedef struct CTNode//孩子结点
{int child;struct CTNode *next;
}*ChildPtr;
typedef struct //表头结构
{TElemType Data;ChildPtr firstchild;
}CTbox;
typedef struct//树结构
{CTBox nodes[MAXSIZE];int r,n;
}

孩子兄弟表示法
任意一棵树，他的结点的第一个孩子如果存在就是唯一，他的右兄弟如果存在也是唯一。因此可以设置连个指针，指向这个结点的第一个孩子和右兄弟。

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

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