github中有详尽代码可作参考

返回目录

树的存储结构

• 双亲表示法

采用一组连续空间来存储每个结点,同时在每个结点中增设一个伪指针,指示其双亲结点在数组中的位置.根结点的下标为0,其伪指针域为-1.

#define MAX_TREE_SIZE 100
typedef int ElemType;

typedef struct{//树的结点定义
    ElemType data;//数据元素
    int parent;//双亲位置域
}PTNode;

typedef struct{
    PTNode nodes[MAX_TREE_SIZE];//双亲表示
    int size;//结点个数
}PTree;

查指定结点的双亲很方便,查指定结点的孩子不方便(只能从头遍历)

• 孩子表示法

将每个结点的孩子结点都用单链表链接起来形成一个线性结构,此时 $n$个结点就有 $n$个孩子链表(叶子结点的孩子链表为空表)

#define MAX_TREE_SIZE 100
typedef char ElemType;

struct ChildNode
{//链表中每个结点的定义
    //链表中每个结点存储的不是数据本身,而是数据在数组中存储的位置下标
    int child;//孩子结点在数组中的位置
    struct ChildNode *next;//下一个孩子
};

typedef struct
{//树中每个结点的定义
    ElemType data;
    ChildNode *firstchild;//孩子链表头指针
}CHNode;

typedef struct
{
    CHNode nodes[MAX_TREE_SIZE];
    int size;
}CTree;

孩子表示法这种存储方式寻找子女的操作非常直接,而寻找双亲的操作需要遍历 $n$个结点中孩子链表指针域所指向的 $n$个孩子链表.

• 孩子兄弟表示法(使用较多)

孩子兄弟表示法又称二叉树表示法,即以二叉链表作为树的存储结构.孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针、指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）。

#define MAX_TREE_SIZE 100
typedef char ElemType;

typedef struct CSNode
{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟节点
    //类似于二叉树中左孩子(第一个孩子),右孩子(右兄弟节点)
}CSNode,*CSTree;

孩子兄弟存储表示法比较灵活,其最大的优点是可以方便的实现树转换为二叉树的操作,易于查找结点的孩子等;缺点是从当前结点查找其双亲结点比较麻烦.

若为每一个结点增设一个 $parent$域指向其父结点,则查找结点的父结点也很方便.

通过孩子兄弟表示法,任意一棵普通树都可以相应转化为一棵二叉树,也就是说,任意一棵普通树都有唯一一颗二叉树与之对应;而森林通过相邻树连边变为大树,最后亦可转化为二叉树.

树的遍历

树的遍历主要有先根遍历和后根遍历.

• 先根遍历:若树非空,则先访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树.这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同.
• 后根遍历:若树非空,则按照从左到右的顺序遍历根结点的每一棵子树,之后再访问根结点.其访问顺序与这棵树对应的二叉树的中序遍历顺序相同.
• 层次遍历:与二叉树的层次遍历思想基本相同,即按层序依次访问各结点.

森林的遍历

• 先序遍历森林

若森林为非空，则按如下规则进行遍历：

（1）访问森林中第一棵树的根结点。

（2）先序遍历第一棵树中根结点的子树森林。

（3）先序遍历除去第一棵树之后剩余的树构成的森林。

对森林的先序遍历，效果等同于依次对各个树进行先根遍历，实质上，等同于依次对二叉树的先序遍历。

先序遍历森林结果为: $\color{Red}{BEKLFCGDHMIJ}$

• 中序遍历森林

若森林为非空，则按如下规则进行遍历：

（1）中序遍历森林中第一棵树的根结点的子树森林。

（2）访问第一棵树的根结点。

（3）中序遍历除去第一棵树之后剩余的树构成的森林。

对森林的先序遍历，效果等同于依次对各个树进行后根遍历，实质上，等同于依次对二叉树的中序遍历。

中序遍历森林结果为: $\color{Red}{KLEFBGCMHIJD}$

总结

设森林 $F$中有 $3$棵树，第一、第二、第三棵树的结点个数分别为 $M_1$, $M_2$和 $M_3$。与森林 $F$对应的二叉树根结点的右子树上的结点个数是().

A. $M_1$

B. $M_1+M_2$

C. $M_3$

D. $\color{Red}{M_2+M_3}$

设第一、第二、第三棵树的根结点分别为 $F_1$, $F_2$和 $F_3$,转化为二叉树为如下图所示:

故森林 $F$对应的二叉树根结点为 $F_1$, $F_1$的右子树包含第二和第三棵树,故结点数为 $M_2+M_3$.

设 $F$是一个森林， $B$是由 $F$变换来的二叉树。若 $F$中有 $n$个非终端结点，则 $B$中右指针域为空的结点有()个。

A. $n-1$

B. $n$

C. $\color{Red}{n+1}$

D. $n+2$

根据森林转换为二叉树的“左孩子右兄弟”的表示法，即对于每棵二叉树，每个结点的右指针指向其右邻兄弟.

针对每一个非终端结点，一定会有且仅有一个孩子结点没有右邻兄弟，即右指针域为空。因此 $n$个非终端结点，就有 $n$个右指针域为空。(一对一的关系)

看完单棵二叉树，再来看这些二叉树是怎么连接成一棵二叉树的。原理是：将后一棵二叉树的根节点作为前一棵二叉树的右孩子连接起来，所以只有最后一棵二叉树的根结点没有右孩子，即右指针域为空。

综上,故在 $B$中有 $n+1$个右指针域为空的结点.

某二叉树结点的中序序列为 $BDAECF$,后序序列为 $DBEFCA$,则该二叉树对应的森林包括()棵树.

A. $1$

B. $2$

C. $\color{Red}{3}$

D. $4$

通过二叉树的中序序列和后序序列可构造出如下左图所示,对应的森林如下右图所示,可看出有 $3$棵树.

2009统考真题：将森林转换为对应的二叉树，若在二叉树中，结点 $u$是结点 $v$的父结点的父结点,则在原来的森林中， $u$和 $v$可能具有的关系是( $\color{Red}{B}$).

Ⅰ. 父子关系

Ⅱ. 兄弟关系

Ⅲ. $u$的父结点与 $v$的父结点是兄弟关系

A. 只有Ⅱ

B. Ⅰ和Ⅱ

C. Ⅰ和Ⅲ

D. Ⅰ、Ⅱ和Ⅲ

• 方式一(父子关系)

• 方式二(爷孙关系)

• 方式三(可能兄弟关系,或者没有关系(位于不同的树上))

例如图中 $B$和 $D$在二叉树中构成爷孙关系,而在森林中是兄弟关系;而 $A$和 $G$也在二叉树中构成爷孙关系,而在森林中没有关系.

• 方式四(叔侄关系或没有关系(u为某树的根结点))

当 $u$为某树的根结点时, $u$和 $v$分别位于不同的树上,此时在森林中没有关系;反之,此时在森林中 $a$为 $u$的右兄弟,故 $u$和 $v$构成叔侄关系.

综上,只有 Ⅰ和Ⅱ满足条件.

2011统考真题：已知一棵有 $2011$个结点的树，其叶结点个数为 $116$，该树对应的二叉树中无右孩子的结点个数是().

A. $115$

B. $116$

C. $1895$

D. $\color{Red}{1896}$

由前面知,针对每一个非终端结点(非叶子结点)，一定会有且仅有一个孩子结点没有右邻兄弟，即右指针域为空。因此 $n$个非终端结点，就有 $n$个右指针域为空。(一对一的关系),故非终端结点的个数是 $2011-116=1895$个,而它本身是个森林,仍需考虑最后一棵树(有且仅有一棵树),它没有右孩子，即右指针域为空,故需在非终端结点的基础上加 $1$,结果为 $1896$个.

2016统考真题：若森林 $F$有 $15$条边、 $25$个结点，则 $F$包含树的个数是().

A. $8$

B. $9$

C. $\color{Red}{10}$

D. $11$

假设令 $15$条边都在同一棵树上,此时该数共使用 $16$个(树中结点数=边数+1)结点,剩下共有 $25-16=9$个结点,分别各构成一棵树,故森林共有 $1+9=10$棵树.

书中解释:

2020统考真题：已知森林 $F$及与之对应的二叉树 $T$,若 $F$的先根遍历序列是 $a,b,c,d,e,f$，中根遍历序列是 $b,a,d,f,e,c$，则 $T$的后根遍历序列是().

A. $b,a,d,f,e,c$

B. $b,d,f,e,c,a$

C. $\color{Red}{b,f,e,d,c,a}$

D. $f,e,d,c,b,a$

由表知,此时二叉树的先序(或中序)遍历与森林的先序(或中(后)序)遍历相同,故可通过该先序和中序构造出二叉树,进而得到二叉树的后序遍历.

故二叉树的后序遍历为 $\color{Red}{b,f,e,d,c,a}$

2021统考真题：某森林 $F$对应的二叉树为 $T$,若 $T$的先序遍历序列为 $a,b,d,c,e,g,f$,中序遍历序列是 $b,d,a,e,g,c,f$,则 $F$中树的棵树是().

A. $1$

B. $2$

C. $\color{Red}{3}$

D. $4$

根据二叉树的先序和中序遍历序列生成二叉树,再转化为森林即可.

由上图知,该森林 $F$共有 $3$棵树.

2022统考真题：如果三叉树 $T$中有 $244$个结点(叶结点的高度为 $1$),那么 $T$的高度至少是()

A. $8$

B. $7$

C. $\color{Red}{6}$

D. $5$

套结论：具有 $n$个结点的 $m$叉树(或度为 $m$的树)的最小高度为 $\left \lceil \log _ m (n\times (m-1)+1)\right \rceil$;

$T$的高度至少为 $\left \lceil \log _ 3 (244\times 2+1)\right \rceil=6$

5.4.1

给定一棵树的先根遍历序列和后根遍历序列，能否唯一确定一棵树?若能，请举例说明;若不能，请给出反例。

一棵树的先根遍历结果与其对应二叉树的先序遍历结点相同,树的后根遍历结果与其对应二叉树表示的中序遍历结果相同.

对应二叉树的先序序列为 $1,2,3,4,5,6,8,7$,中序序列为 $3,4,8,6,7,5,2,1$;原树的先根遍历序列为 $1,2,3,4,5,6,8,7$,后根遍历为 $3,4,8,6,7,5,2,1$.

5.4.2

将下面一个由 $3$棵树组成的森林转换为二叉树。

5.4.3

已知某二叉树的先序序列和中序序列分别为 $ABDEHCFIMGJKL$和 $DBHEAIMFCGKLJ$,请画出这棵二叉树,并画出二叉树对应的森林.

左图为二叉树,右图为对应的森林.

5.4.4

编程求以孩子兄弟表示法存储的森林的叶结点数.

当森林(树)以孩子兄弟表示法存储时,若结点的指向结点第一个孩子结点的指针为空,则说明为叶子结点.

void Get_Leaves(CSTree t,int &tot)//通过引用传值
{
    if(t!=NULL)
    {
        Get_Leaves(t->firstchild,tot);
        if(t->firstchild==NULL)
            tot++;
        Get_Leaves(t->nextsibling,tot);
    }    
}

5.4.5

以孩子兄弟链表为存储结构,请设计递归算法求树的深度.

孩子兄弟表示法中采用左孩子右兄弟,故只需递归比较左孩子的深度+1和右兄弟的深度即可.

int Get_Height(CSTree t)
{
    if(t==NULL)
        return 0;
    else
    {
        int hchild=Get_Height(t->firstchild);
        int hsibing=Get_Height(t->nextsibling);
        return hchild+1>hsibing?hchild+1:hsibing;
    }
}

5.4.6

已知一棵树的层次序列及每个结点的度，编写算法构造此树的孩子-兄弟链表.

由于层次遍历的顺序可以根据节点的度去充分地遍历每一个节点的兄弟，所以可以每次都把每一层节点的兄弟关系先链接好，并且由于父子关系只能查找一次，所以按照层序序列经过节点时，需要把其孩子节点链接上。
所以按照层序次序遍历节点时，先链接上第一个孩子节点，然后链接上该节点的全部兄弟节点。

void Init_Tree_By_LevelOrder(CSTree &t,ElemType e[],int degree[],int n)
{
    CSTree *temp=new CSTree[MAX_TREE_SIZE];

    for(int i=0;i<=n-1;i++)//初始化赋值和置空
    {
        temp[i] = new CSNode;//一定记得初始化
        temp[i]->data=e[i];
        temp[i]->firstchild=temp[i]->nextsibling=NULL;
    }

    int pos=0;
    for(int i=0;i<=n-1;i++)//遍历至第i个结点
    {
        if(degree[i]>0)//如果有孩子
        {
            temp[i]->firstchild=temp[++pos];//第一个孩子赋给孩子指针
            for(int j=2;j<=degree[i];j++)
            {
                temp[pos]->nextsibling=temp[pos+1];//其余孩子处理:后一个赋给前一个的兄弟指针
                pos++;
            }
        }
    }
    t=temp[0];
    //delete []temp;
}

5.4.7

2016统考真题：若一棵非空 $k$( $k \geq 2$）叉树 $T$中的每个非叶结点都有 $k$个孩子，则称 $T$为正则 $k$叉树。请回答下列问题并给出推导过程。

1)若 $T$有 $m$个非叶节点,则 $T$中的叶结点有多少个?

2)若 $T$的高度为 $h$(单节点的树 $h=1$),则 $T$的结点数最多有多少个?最少为多少个？

1)设叶子结点的个数为 $n_0$,已知非叶子结点个数为 $m$,总个数为 $n$,则 $n=n_0+m$;

又因为边数=总结点数-1,且边数由每个非叶子结点作出 $k$条边,故 $n-1=m\times k$;

两式联立: $m\times k+1=n_0+m$,即叶子结点的个数为 $n_0=m\times(k-1)+1$

2)当该树为满 $k$叉树时,此时 $T$的结点数最多为 $1+k^1+k^2+\cdots+k^{h-1}=\frac{1(1-k^h)}{1-k}=\frac{k^h-1}{k-1}$;

当第 $1$层只有根结点,第 $2$到第 $h-1$层仅含 $1$个分支结点和 $k-1$个叶结点,第 $h$层有 $k$个叶结点(即即除根外第 $2$到第 $h$层中每层的结点数均为 $k$),此时 $T$的结点数最少,结果为 $1+k\times (h-1)$