树和树结构

Published on:
Tags: 数据结构 树
树

树结构的定义和属性#

定义：具有相同特性的n(n>=0)个数据节点组成的一个有穷序列，节点之间存在一对多的关系。

  • 当n等于0时，为空树
  • 当n大于0时，有且仅有一个根节点，且根节点没有前驱节点
    • 除根节点外，其余节点都有且仅有一个前驱节点
    • 树中每个节点都有零个或者多个后继节点

属性（如上图）：

  • 空树 节点数为0的树称为空树
  • 根节点 节点①为根节点，根节点没有前驱节点，在树中具有唯一性
  • 前驱节点 前驱节点是一个相对位置的概念，节点①是节点②③的前驱节点
  • 后继节点 后继节点是一个相对位置的概念，节点②③是节点①的后继节点

    换一种说法:节点①的后继节点是节点②，节点①的后继节点是节点③

  • 子节点 节点的后继节点称为子节点
  • 父节点 节点的前驱节点称为父节点
  • 兄弟节点 具有相同父节点的子节点互为兄弟节点
  • 子孙节点 节点的所有子树中的节点称为子孙节点
  • 祖先节点 从树根节点到达节点的路径上经过的所有节点被称为该节点的祖先节点

抽象数据类型#

1
2
3
4
5
6
7
8
9
10
11
12
13
ADT Tree
{
数据对象：
    D = {ai | ai ∈ ElemType, i=1,2,…,n, n>=0 }              // ElemType为类型标识符
数据关系：
    R = {<ai,aj> | ai, aj∈D, i=1,2,…,n, j=1,2,…,n，其中每个元素只有一个前驱节点 ，可以有零个或多个后继节点，有且仅有一个元素（根节点）没有前驱节点 }
数据操作：
    (1) treeSeq * InitTree();                              //构造一个空的树t      
    (2) DestroyTree(treeSeq *t);                           //释放树t占用的内存空间      
    (3) Parent(treeSeq *t);                                //求t所指节点的双亲结点      
    (4) Sons(treeSeq *t);                                  //求t所指节点的子孙节点      
    ... ...
}

树的运算主要分为三大类：

  1. 寻找满足某种特定关系的节点，如寻找双亲节点；
  2. 插入或删除某个节点，如在树的当前节点上插入一个新节点 或删除当前节点的第i个孩子节点等；
  3. 遍历树中每个节点。

总结起来就是查找、增删、遍历

树的表示方法#

树的表示方法：树形表示法、文氏图表示法、凹入表示法、括号表示法

树的表示方法

树的遍历#

树的遍历指按照一定次序访问树中所有节点，并且每个节点仅被访问一次的过程。

三种方法实现树的遍历：

  1. 先根遍历
    若树不空，则先访问根节点，然后依次从左到右访问子节点。先根遍历上图的树：1 2 4 8 9 5 10 11 3 6 7

  2. 后根遍历
    若树不空，则先依次从左到右访问子节点，然后访问根节点。后根遍历上图的树：8 9 4 10 11 5 2 6 7 3 1

  3. 层次遍历
    若树不空，则自上而下，自左至右访问树中每个节点。层次遍历上图的树：1 2 3 4 5 6 7 8 9 10 11

树的属性2#

  • 节点的度和树的度 树中某个节点的子节点个数称为该节点的度，节点中最大的度称为树的度

  • 分支节点与叶子节点 度不为零的节点称为分支节点，度为零的节点称为叶子节点

    节点的度数也叫节点的分支数，分支数等于1的节点称为单分支节点，分支数等于2的节点称为双分支节点，以此类推

  • 路劲与路径长度 树中任意两个节点 $d_i$ 和 $d_j$ ，若存在一个节点序列 $[d_i,d_{i1},d_{i2},…,d_j]$，使得序列中除了 $d_i$ 外的任一个节点都是其在序列中前一个节点的后继节点，则称该节点序列为由 $d_i$ 到 $d_j$ 的一条路劲。路径长度等于路径序列中节点的数量减1

    节点①和⑩之间存在一个节点序列 [①②⑤⑩]，序列长度为3

  • 节点的层次和数的高度 一个节点的层次为从根节点到该节点的路径长度加1，节点的最大层次为树的高度

  • 森林 n个互不相交的树的集合称为森林

    森林转树：多个树的集合（森林）加一个根节点变成树

    树转森林：一个树的集合去掉一个根节点变成森林

树的性质#

性质1 树中的节点数等于所有节点的度数和加1

证明：

  1. 已知：树中的节点数 = 根节点数 + 分支节点数（除根节点） + 叶子节点数
  2. 因为：所有节点的度数 = 叶子节点数 + 分支节点数（除根节点）
  3. 所以：树中的节点树 = 所有节点的度数 + 1

性质2 度为m的树中第i层(i>=1)上至多有 $m^{i-1}$ 个节点

证明：

  1. 当i=1时，$m^{i-1}=m^0=1$ ，表示第一层有1个节点，命题成立
  2. 假设当i=n-1时，$m^{i-1}=m^{n-2}$ 命题成立
  3. 则当i=n时，第n层的最多节点数是第n-1层的最多节点数的m倍，于是第n层的节点数为： $m^{n-2}*m=m^{n-1}$。命题成立。

性质3 高为h的m次树至多有 $\frac{m^h-1}{m-1}$ 个节点

根据性质2可以计算出m度树每一层至多节点数量 $m^{i-1}$，当每一层都达到最多节点数，那么高度为h的m度树，最多节点数：
$m^{1-1} + m^{2-1} + m^{3-1} + … + m^{h-1} = m^0 + m^1 + m2 + … + m^{h-1} $
通过等比数列前n项和公式可得结果： $\frac {m^h-1}{m-1} $

性质4 具有n个节点的m次树的最小高度h为 $\log_{m}n(m-1)+1$

证明：

  1. 设具有n个节点的m次树的高度为h
  2. 若在该树中前h-1层都是满的，即每一层的节点数都等于 $m^{i-1} (1<=i<=h-1)$ ，则该树具有最小的高度
  3. 第h层（即最后一层）的节点数可能满，也可能不满，高度h可计算如下：
  4. $\frac{m^{h-1}-1}{m-1} < n <= \frac{m^h-1}{m-1} $
    • 两边乘(m-1) ： $m^{k-1}-1 < n(m-1) <= m^{k}-1$
    • 两边加1求对数 ： $h-1 < \log_m(n(m-1)+1) <= h$
  5. $\log_m(n(m-1)+1) <= h < log_m(n(m-1)+1)+1$
  6. 因为h为整数，所以 $h=log_m(n(m-1)+1)$

树的存储结构#

双亲存储结构

存储结构：顺序存储结构

把树的节点按顺序存储到每一个节点，节点包含有值域和父节点的索引下标

1
2
3
4
5
6
7
8
#define MaxSize 50
typedef int ElemType;

typedef struct
{
    ElemType date;
    int parent;
} PTree[MaxSize];

孩子链存储结构

存储结构：链式存储结构

存储每个节点的值，并且保存所有孩子的指针
由于每个节点的孩子数量可能不一样（节点的度），所以按最大节点的度（树的度）数来设计节点的指针数量

1
2
3
4
5
6
#define MaxSize 50
typedef struct node
{
    ElemType date;
    struct node *sone[MaxSize];
} TSonNode;

孩子兄弟链存储结构

存储结构：链式存储结构

存储每个节点的值，并且保存第一个孩子的指针和下一个兄弟的指针

1
2
3
4
5
6
7
typedef int ElemType;
typedef struct tnode·
{
    ElemType date;      //节点的值
    struct tnode *hp;   //指向兄弟
    struct tnode *vp;   //指向孩子节点
}TSBNode;