树的存储结构以及树，二叉树，森林之间的转换

目录

1.双亲表示法

2.孩子链表

3.孩子兄弟表示法

4.树与二叉树的转换

（1）树转换为二叉树

（2）二叉树转换成树

5.二叉树与森林的转化

（1）森林转换为二叉树

以下树为例

1.双亲表示法

双亲表示法定义了一个结构数组，存放树的结点，每个结点含两个域

数据域：存放结点本身信息

双亲域：指示本结点的双亲结点在数组的位置

 如下图所示A,B,C的父节点为R

2.孩子链表

#孩子结点结构
typedef struct CTNode{
    int child;
    struct CTNode *next;
}*ChildPtr;
 
#树结构
typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;//n表示结点数,r表示根结点的位置
}
 
#双亲结点结构
typedef struct{
    TElemType data;
    ChildPtr firstchild;
 
}CTBox;

3.孩子兄弟表示法

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

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;
    
}CSNode,*CSTree;

如下图“A”所示，第一个指针域指向他的第一个孩子“D”，第二个指针域指向他的兄弟结点B，以此类推: 

4.树与二叉树的转换

树的存储结构如上图所示，第一个指针域指向第一个孩子，第二个指针域指向兄弟结点

而二叉树的存储结构则为第一个指针域指向左孩子，第二个指针域指向右孩子，转换如下：

那转换的方法是什么呢？

（1）树转换为二叉树

•在兄弟之间加连线

•对于每一个结点，除了左孩子外，去掉其与其余孩子之间的关系

•以树的根结点为轴心，将整树顺时针转45度

更复杂的可以看下图：

（2）二叉树转换成树

• 若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子......沿分支找到的所有右孩子，都与p的双亲用线连起来

•抹掉原二叉树中双亲与右孩子之间的连线

•将结点按层次排列，形成树结构

5.二叉树与森林的转化

（1）森林转换为二叉树

•将每一棵树转换为二叉树

•将每一个根结点连接起来

•旋转45度

（2）二叉树转换为森林

•将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树

•将孤立的二又树还原成树