数据结构之树

1.树的基本概念

1.树的定义

树是由n(n>=0)个结点（或元素）组成的有限集合（记为T）。

如果n=0,它是一棵空树，这是树的特例。

如果n>0，这个结点中有且仅有一个结点作为树的根结点，简称为根。其余结点可分为m个互不相交的有限集T1,T2......Tm，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。

2.树的逻辑表示方法

（1）.树形表示法：用一个圆圈表示一个结点，圆圈内的符号代表该结点的数据信息，结点之间的关系通过分支线标识，其方向隐含着从上向下，即分支线的上方结点是下方结点的前驱结点，下方结点是上方结点的后继结点。

（2）文氏表示法：每棵树对应一个圆圈，圆圈内包含根结点和子树的圆圈，同一个根结点的各子树的圆圈不能相交。

（3）凹入表示法

（4）括号表示法

3.树的基本术语

（1）结点的度与树的度：树中某个结点的子树的个数称为该结点的度，书中所有节点的度中最大值称为树的度，通常将度为m的数称为m次树。

（2）分支结点与叶子结点：树中度不为0的结点称为分支结点，度为0的结点称为叶子结点。对于度为1的结点，其分支树为1，被称为单分支结点。对于度为2的结点，其分支树为2，被称为双分支结点。以此类推。

（4）路径与路径长度：从结点i到结点j的一条路径，路径长度等于从i到j经过的所有结点数减1.

（5）孩子结点，双亲结点和兄弟结点：在一棵树中，每个结点的后继结点称为该结点的孩子结点，相应的，该节点被称为孩子结点的双亲结点，具有同一个双亲结点的孩子互为兄弟结点。

（6）结点层次与树的高度：结点层次或结点深度是一根结点为第一层，孩子结点为第二层，以此类推，树中结点的最大层次称为树的高度或树的深度。

（7）有序数和无序树：树中各结点按照一定的次序从左到右安排，且相对次序不能随意变化，则称为有序数，否则为无序树。

（8）森林：m棵互不相交的数的集合称为森林。

4.树的性质

1.树中的结点数等于所有结点的度数之和加1.

2.度为m的树中第i层上最多有m^(i-1)个结点。

3.高度为h的m次树最多有（m^h-1）/(m-1)个结点。（该结果由等比数列求和可得）

4.具有n个结点的m次树的最小高度为。

5.树的存储结构

1.双亲存储结构

：是一种顺序存储结构，用一组连续空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置。

typedef struct
{ELemType data;    //存放结点的值int parent;       //存放双亲的位置
}PTree[MaxSize];      //PTree双亲存储结构类型

缺点：该方法找一个结点的双亲结点十分容易，但是找其孩子结点时需要遍历整个存储结构。

2.孩子链存储结构

typedef struct
{ELemType data;                 //结点的值struct node* sons[MaxSons];    //指向孩子结点
}TSonNode;                         //孩子链存储结构中的结点类型

缺点：查找某个结点的双亲结点需要遍历树，当树的度较大时存在较多的空指针域，浪费空间。

3.孩子兄弟存储结构

typedef struct tnode
{ELemType data;              //结点的值struct tnode* hp;           //指向兄弟struct tnode* vp;           //指向孩子结点
}TSBNode;                       //孩子兄弟存储结构的结点类型

缺点： 查找一个结点的双亲结点需要遍历树。