[数据结构] 树、二叉树、森林的转换

树

树的表示方法

双亲表示法

用一组地址连续的存储单元来存放树中的各个节点，每一个节点中有一个数据域和一个指针域，数据域用来存储树中该节点本身的值；另一个指针域用来存储该节点的双亲节点在存储结构中的位置信息。

采用双亲链表存储方式实现查找一个指定节点的双亲节点比较方便，但难以实现查找一个指定节点的孩子节点。

孩子表示法

用一组地址连续的存储单元来存放树中的各个节点，每一个节点有一个数据域和一个指针域，数据域用来存储树中该节点的值；另一个指针域用来存放该节点的孩子链表的头指针。形式上有点像存储图的领接表。

采用孩子表示法便于实现查找树中指定节点的孩子节点，但难以实现查找树中指定节点的双亲节点。

孩子兄弟表示法

孩子兄弟表示法是用一种链式的结构存储一颗树的方式。每个节点含有孩子指针域和兄弟指针域。我们分别用 firstchild 和 nextsibling 表示。
其中孩子指针域，表示指向当前结点的第一个孩子结点，兄弟结点表示指向当前结点的下一个兄弟结点。其本质是先将一棵树转换为二叉树后存储在二叉链式结构之中。

孩子兄弟表示法能够将对一棵树的操作转换成对二叉树的操作，这种表示方法在实际运用中比较广泛。

故在这里给出孩子兄弟表示法创建树的代码，在后文中也都是使用这种表示方法。

孩子兄弟表示法创建树

typedef char Elemtype;
//树 (孩子兄弟表示法)
typedef struct CSNode{

    Elemtype data;
    struct CSNode *firstchild;      //第一个孩子
    struct CSNode *nextsibling;     //下一个兄弟

}CSNode, *CSTree;

//创建 树
CSTree Create_CSTree(){
    Elemtype data;
    CSTree T;
    scanf("%c", &data);                       //输入节点数据
    getchar();

    if(data == '#')        //输入 - 以停止创建子树
        return NULL;
    T = (CSTree)malloc(sizeof(CSNode));
    T->data = data;

    printf("输入 %c 的第一个孩子数据(#停止): ", data);  //递归创建
    T->firstchild = Create_CSTree();
    printf("输入 %c 的下一个兄弟数据(#停止): ", data);  
    T->nextsibling = Create_CSTree();
 
    return T;
}

---

二叉树

二叉树是节点度数不大于 2 的有序树，是简单而又广泛运用的重要数据结构。

二叉树基本结构

//二叉树 结构体
typedef struct BiNode{

    Elemtype data;
    struct BiNode *leftchild;       //左儿子
    struct BiNode *rightchild;      //右儿子

}BiNode, *BinaryTree;              

---

森林

森林很好理解，就是多个树组成的集合。

森林基本结构

//森林 结构体
typedef struct {

    CSTree ct[MAX];
    int n;   //树的个数
	
}forest, *Forest;

---

树、二叉树和森林的转换

树 转换为 二叉树

树 --> 二叉树步骤

（1）将树中每个相邻的兄弟进行连线；
（2）将每个节点除第一个孩子以外，断开其他兄弟与其双亲节点的连线；
（3）适当旋转处理完后的树，使其呈现二叉树的形式。

树 --> 二叉树图解

（1）加线、（2）断线