@[toc]

关于树和二叉树的内容确实是非常多啊，没想到加上这篇已经有三篇了，这篇文章我将会把剩余的树和二叉树的内容全部介绍完，还有一个哈夫曼树的内容，我将单独写一篇专栏文章介绍。

森林的定义

前面的文章中提到了树的定义，我们说树是一个递归的定义，树由若干子树构成，其中的每一棵子树又由若干子树构成。

那么森林是什么呢？

森林是m(m ≥ 0)棵互不相交的树的集合

树的存储结构

下面介绍树的存储结构，对于树的存储结构，它有以下三种实现方式：

双亲表示法
孩子表示法
孩子兄弟表示法

双亲表示法

双亲表示法的关键就是双亲了，对于除根结点外的任意结点，它都有唯一的双亲结点，所以树的结构定义应为：

#define MAX_SIZE 10

typedef struct PTNode{
   
   
    char data;
    int parent;        //双亲位置域
}PTNode;

typedef struct{
   
   
    PTNode nodes[MAX_SIZE];
    int r;            //根结点的位置
    int n;            //树的结点个数
}PTree;

比如这样的一个数组：
在这里插入图片描述
通过双亲位置域很容易知道，这棵树的根结点为R，又因为A、B、C的双亲位置域均为0，而下标0表示根结点R，所以根结点R下有三棵子树，以此类推，这棵树的结构为：

双亲表示法的特点是：找双亲易，找孩子难。

孩子表示法

孩子表示法的意思是：
把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表，用顺序表存储。

比如这棵树：
在这里插入图片描述
其用孩子表示法表示结果如下：

先看根结点，根结点R有三个孩子结点，所以R结点结构中的指针域存放其第一个孩子结点位置，然后这三个孩子组成一个单链表，该单链表结点中的数据域存放结点在数组中的位置，以此类推。

所以树的结构定义应为：

//孩子结点结构
typedef struct CTNode{
   
   
    int child;
    struct CTNode *next;
}*ChildPtr;

//双亲结点结构
typedef struct{
   
   
    char data;
    ChildPtr firstChild;    //存储第一个孩子结点的头指针
}CTBox;

typedef struct{
   
   
    CTBox nodes[MAX_SIZE];
    int r,n;        //根结点位置和结点数
}CTree;

孩子表示法的特点是：找孩子易，找双亲难。

孩子兄弟表示法

什么是孩子兄弟表示法呢？

用二叉链表作为树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。

比如下面的一棵树：
在这里插入图片描述
如何用孩子兄弟法进行表示呢？

先看根结点，根结点R有三个孩子，无兄弟结点，所以应该让根结点的一个指针域指向第一个孩子结点A，另一个指针域为空。
在这里插入图片描述
再看结点A，结点A有两个孩子，一个兄弟结点，所以让结点A的一个指针域指向第一个孩子结点D，另一个指针域指向兄弟结点B。

以此类推，整棵树的表示结果如下：

其结构定义如下：

typedef struct CSNode{
   
   
    char data;
    struct CSNode *firstChild,*nextSibling;
}CSNode,*CSTree;

孩子兄弟表示法的特点：找孩子兄弟易，找双亲难。

树与二叉树的转换

到这里，树、二叉树和森林的讲解就结束了，下面还需要介绍一下树、二叉树、森林之间的相互转换，先讲讲树转换为二叉树。

树转换为二叉树

树要想转换为二叉树，需要一下步骤：

加线：在兄弟结点之间加上一条连线
去线：对每个结点，除了其左孩子外，去除与其它孩子结点之间的连线
旋转：以树的根结点为轴心，将整棵树顺时针旋转45°

总结为一句口诀：兄弟相连留长子。

比如下面的一棵树：
在这里插入图片描述
我们试着将这棵树转换为二叉树。

第一步，先将兄弟结点之间连上线：
在这里插入图片描述
第二步，去掉除左孩子外其它孩子结点的连线，比如根结点A只保留与结点B的连线，结点B只保留与结点E的连线，结点D只保留与结点H的连线：

此时作适当的旋转，最终结果为：

二叉树转换为树

知道了如何将树转换为二叉树后，将二叉树转换为树就非常简单了，需要进行如下步骤：

加线：若p结点是双亲结点的左孩子，则将p结点的右孩子，右孩子的右孩子......沿分支找到所有右孩子，都与p的双亲用线连起来
去线：去除原二叉树中双亲与右孩子的连线
调整：将结点按层次排列，形成树结构

总结为一句口诀：左孩右右连双亲，去掉原来右孩线。

比如下面的一棵二叉树：
在这里插入图片描述
如何将这棵二叉树转换为树呢？

第一步，加线。找到某个结点的左孩子，如根结点A的左孩子为结点B，然后将结点B的右孩子，右孩子的右孩子，右孩子的右孩子的右孩子......都与其双亲结点A用线连接起来，其它结点的操作也是如此。
在这里插入图片描述
第二步，去线。去掉原来的右孩子之间的连线，比如结点B的右孩子，结点C和结点D之间的连续可以去除。

此时进行适当调整使其层次分明，最终结果为：