树——树的转换

1. 树的存储结构

    通常，树的存储结构有三种，双亲表示法、孩子表示法和孩子兄弟表示法。

（1）双亲表示法

    双亲表示法是利用一组连续的存储单元存储树的每个结点，并利用一个指示器表示结点的双亲结点在树中的位置。

    树的双亲表示法存储表示描述如下：

   

#define MaxSize 200
typedef struct PNode        /* 双亲表示法的结点定义 */
{
    DataType data;
    int parent;                    /* 指示结点的双亲 */
}PNode;

typedef struct
{
    PNode node[MaxSize];
    int num;                        /* 结点的个数 */
}PTree;

 

图 树的双亲表示法

 

（2）孩子表示法

    由于树中每个结点可能有多个孩子，所以自然想到用多重链表存储树。在这种多重链表的每个结点中除了用于存放数据信息的data域外，还有若干指针域，分别用于指向该结点的孩子结点。但是一棵树中，不同结点的度数是不同的，那么每个结点中到底需要多少个指针域呢？我们有如下二种方案：

① 定长结点

    即树中每个结点均按树的度k来设置指针。n个结点的树一共有n*k个指针域，而树中只有n-1条边，故树中的空指针数目为kn-(n-1)=n(k-1)+1（k越大，浪费的空间越多）。

②不定长结点

    即树中每个结点按本结点的度来设置指针数，并在结点中增设一个度数域degree指出该结点包含的指针数。各结点不等长，虽然节省了空间，但是给运算带来不便。

    孩子结点表示法的类型定义如下：

//以下的DataType和MaxTreeSize由用户定义
    typedef struct CNode{//子链表结点
        int child； //孩子结点在向量中对应的序号
        struct CNode *next；
      }CNode；
    typedef struct{ 
        DataType data； //存放树中结点数据
        CNode *firstchild；//孩子链表的头指针
      }PTNode；
    typedef struct{
        PTNode nodes[MaxTreeSize]；
        Int n，root； //n为结点总数，root指出根在向量中的位置
      }CTree；
    Ctree T； //T为孩子链表表示

 注意：当结点T.nodes[i]为叶子时，其孩子链表为空，即T.nodes[i].firstchild=NULL。

（3）孩子兄弟表示法

    孩子兄弟表示法，也成为树的二叉链表表示法。孩子兄弟表示法，采用链式存储结构，链表由一个数据域和两个指针域组成。其中，数据域存放结点的数据信息，一个指针域用来指示结点的第一个孩子结点，另一个指针域用来指示结点的下一个兄弟结点。

图 孩子兄弟表示法

    树的孩子兄弟表示法的类型定义如下：

/* 孩子兄弟表示法的类型定义 */
typedef struct CSNode
{
    DataType data;
    struct CSNode *firstchild, *nextsibling; /* 指向第一个孩子和下一个结点 */
}CSNode, *CSTree;

 

2. 树、森林的遍历

（1）树的遍历

    设树T如下图所示，结点R是根，根的子树从左到右依次为T₁，T₂，…，T_k。

（1）树T的前序遍历定义： 
　　若树T非空，则：
　①访问根结点R；
  ②依次前序遍历根R的各子树T₁，T₂，…，T_k。

（2）树的后序遍历定义：
　　若树T非空，则：
    ①依次后序遍历根T的各子树T_l，T₂，…，T_k；
    ②访问根结点R。

【例】对下面的(a)图中的树进行前序遍历和后序遍历，得到的前序序列和后序序列分别是ABCDE和BDCEA。

图 树和对应的二叉树

注意：
    　① 前序遍历一棵树恰好等价于前序遍历该树对应的二叉树
    　② 后序遍历树恰好等价于中序遍历该树对应的二叉树。

（2）森林的遍历

（1）前序遍历森林
    若森林非空，则：
①访问森林中第一棵树的根结点；
②前序遍历第一棵树中根结点的各子树所构成的森林
③前序遍历除第一棵树外其它树构成的森林。

（2）后序遍历森林
　　若森林非空，则:
①后序遍历森林中第一棵树的根结点的各子树所构成的森林；
②访问第一棵树的根结点；
③后序遍历除第一棵树外其它树构成的森林。
  注意：
 ① 前序遍历森林等同于前序遍历该森林对应的二叉树
 ② 后序遍历森林等同于中序遍历该森林对应的二叉树
【例】对下面(a)图中所示的森林进行前序遍历和后序遍历，则得到该森林的前序序列和后序序列分别为ABCDEFICJH和BDCAIFJGHE。而(b)图所示二叉树的前序序列和中序序列也分别为ABCDEFICJH和BDCAIFJGHE。

图 森林和对应的二叉树

  ③ 当用二叉链表作树和森林的存储结构时，树和森林的前序遍历和后遍历，可用二叉树的前序遍历和中序遍历算法来实现。

 

3. 树、森林和二叉树的转换

    树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树；反之，任何一棵二叉树也能惟一地对应到一个森林或一棵树。

（1）树、森林到二叉树的转换

* 将树转换为二叉树
    　树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：
　　①在所有兄弟结点之间加一连线；
　　②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。
【例】下面(a)图所示的树可转换为(c)图所示的二叉树。

图 树转化为二叉树

注意：由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。
* 将一个森林转换为二叉树
 具体方法是：
　　① 将森林中的每棵树变为二叉树
　　② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。
【例】下图中，左边包含三棵树的森林可转换为右边的二叉树。

图 森林转化为二叉树

（2）二叉树到树、森林的转换
    把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。
【例】下图的森林就是由二叉树转换成的。 

图 森林转化为二叉树