【数据结构】树

定义

LaTeX 渲染 树是有n($n \ge 0$)个结点组成的有限集合（记作$T$） $n=0$时这是一棵空树 $n>0$则只有一个根节点，其余结点组成的互不相交的有限集$T_i$组成根节点的子树

表示方法 1.树形表示法 2.文氏图 3.凹入表示法 4.括号表示法

概念

1.度 一个结点的子树个数称为该结点的度，所有结点的度的最大值为树的度，记作m，则该树称为m次树

2.叶子结点 度为0的结点

3.分支节点 不是叶子结点的结点

4.路径 从$k_i$到$k_j$自上而下经过的有序路径序列

5.路径长度 路径结点数目-1

6.孩子节点 一个结点的后继结点（子节点）

7.双亲节点 父节点

8.兄弟结点 相同父节点

9.结点层次 树的高度（深度） 根节点为第一层 深度为1 最大层次称为树的高度

10.有序树 无序树 森林

性质 1.树中的结点数 = 所有结点度数和 + 1 2.度m的树第i层最多有$m^{i-1}$个结点 3.高h的m次树最多有$\frac {m^{h}-1}{m-1}$个结点 当结点数最大时该树为满m次树 4.具有n个结点的m次树的最小高度$\left \lceil log_{m}{n(m-1)+1} \right \rceil$

计算技巧 1.所有结点度数之和 $ = n - 1 = n_1 + 2n_2 + \cdot \cdot \cdot + mn_m$ 其中$n_i$为度为i的结点个数 n为树的结点个数 2.$n = \sum_{i = 0}^{m} n_{i} $

遍历 1.先根遍历 2.后根遍历 3.层次遍历

存储结构 1.双亲存储（存储父节点位置）

typedef struct
{
    int data;
    int parent; //父节点索引
} PTree[MaxN];

2.孩子链存储（儿子存储）

typedef struct node
{
    int data;
    node* sons[MaxSN];//结点最大度
} node;

3.孩子兄弟链

struct node
{
    int data;
    struct node *hp; //兄弟 （有序）t
    struct node *vp; //孩子
}

可用于把树转换成二叉树 兄弟和孩子都是有序的 兄弟相当于下一个兄弟 孩子指向左边第一个孩子

例题

1. 用后两种存储结构 设计一个求树t高度的递归算法

递归模型： $f(t) = \begin{cases}0,t=NULL \\max_{p->t}{f(p)+1} ,t!=NULL\end{cases}$ for all p -> t 1.孩子链

int Height1(node *t)
{
    node *p;
    int i, h, maxh = 0;
    if(!t) return 0;
    for(i = 0; i < MaxSN; i++)
    {
        p = t -> sons[i];
        if(p)
        {
            h = Height1(p);
            if(maxh < h)maxh = h;
        }
    }
    return maxh + 1;

2.孩子兄弟链

int Height2(node *t)
{
    node *p;
    int h, maxh = 0;
    if(!t) return 0;
    p = t -> vp;
    while(p)
    {
        h = Height2(p); // 对子树求最大高
        if(maxh < h) maxh = h;
        p = p -> hp; //对兄弟结点进行求高