树的基础知识总结

一、树的定义

1.树（Tree）是n（n>=0）个结点的有限集。n= 0时称为空树，在任何一棵非空树中，有且仅有一个根结点，当n>1时，其余结点可分为m个互不相交的有限集，其中每一个集合本身又是一棵树，并称为根的子树。

2、结点的分类

结点拥有的子树个数称为结点的度。度为0的结点称为叶结点或终端结点。度不为0的结点称为分支结点或非终端结点。树的度为树内各结点度的最大值。

3、结点关系

结点的子树的根称为该结点的孩子，该结点称为孩子结点的双亲。同一个双亲的结点称为兄弟

结点的祖先是从根到该结点所经分支上的所有结点。以某结点为跟的子树的任何一个结点都被称为该结点的子孙。

4、树的其他概念

结点的层次从根结点开始，根为第一层，根的孩子为第二层。其双亲在同一层次的结点互为堂兄弟。树中结点的最大层次称为树的深度或高度。

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

二、树的存储结构

树的存储结构分为顺序存储于链式存储两种结构；

1、双亲表示法：

将一组连续空间存储树的结点，每个结点包含一个data数据域和一个指针域指向双亲在数组中的下表；

 1 #define MAX_SIZE 50
 2 typedef int ElemType;
 3 typedef struct PTNode //结点结构
 4 {
 5     int parent;//双亲的下标位置
 6     ElemType data;//结点数据
 7 }PTNode;
 8 
 9 typedef struct PTree //树结构
10 {
11     PTNode node[MAX_SIZE];//结点数组
12     int r,n;//根结点位置和结点数
13 }PTree;

由于根结点没有双亲，所以讲=将根结点的位置域设置为-1.

2、孩子表示法：

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

data

degree

child1

child2

......

childn

 1 #define MAX_SIZE 50
 2 typedef int ElemType;
 3 typedef struct CTNode //孩子结点结构
 4 {
 5     int child;
 6     struct CTNode* next;
 7 }*ChildPtr;
 8 
 9 typedef struct  //表头结构
10 {
11     ChildPtr firsChild;
12     ElemType data;
13 }CTBox;
14 
15 typedef struct//树结构
16 {
17     CTBox nodes[MAX_SIZE];//结点数组
18     int r, n;//根的位置及结点数
19 }CTree;

3、孩子兄弟表示法：

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

1 typedef int ElemType;
2 typedef struct CTNode //孩子兄弟结点结构
3 {
4     struct CTNode *lchild, *rchild;
5     ElemType data;
6 }*CSTree,CSNode;