数据结构与算法 －树和森林

树的存储结构

1. 双亲表示法

以一组连续空间存储树的结点，即一个一维数组构成，数组每个分量包含两个域：数据域和双亲域。数据域用于存储树上一个结点的数据元素值，双亲域用于存储本结点的双亲结点在数组中的序号（下标值），根结点没有双亲，双亲域的值为-1。

双亲链表的类型定义如下：

#define size 10;
typedef struct{ 
    datatype data;
    int parent;
} Node;
Node slist[size];

由树可以转化为双亲表示法，同时，由双亲表示法也可以转化为树，通常情况下会给一个双亲表示法，然后让我们求出树的高度。

 

2. 孩子链表表示法

树中每个结点的孩子串成一个单链表，数组元素存储结点本身的信息和该结点的孩子链表的头指针。

 孩子链表表示法的类型定义：

# define MAXND 20
// 孩子节点
typedef struct bnode{
    int child;
    struct bnode *next;
}node,*childlink;
// 父节点
Typedef struct{ 
    DataType data;
    childlink hp;
}headnode;

Headnode;link[MAXND];

在孩子链表表示中，找孩子方便，但求 结点的双亲困难，因此可在顺序表中再增加 一个域，用于指明每个结点的双亲在表中位 置，即将双亲表示法和孩子链表表示法结合起来。

 

3. 双亲孩子表示法

树中每个结点的孩子串成一单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子链表的头指针之外，还增设一个域，用来存储结点双亲结点在数组中的序号。

双亲孩子表示法的类型定义：

# define MAXND 20
// 孩子节点
typedef struct bnode{
    int child; 
    struct bnode *next;
}node,*childlink;

// 父节点
Typedef struct{
    DataType data; 
    // 当前节点的父节点
    int parent; 
    childlink hp;
}headnode;

Headnode;link[MAXND];

 

4. 孩子兄弟链表表示法

树中的每一个节点的左指针域指向该节点的第一个孩子结点，右指针域指向该结点的下一个兄弟结点。

另外也可以用下面这种表现形式，意义是一样的。 

孩子兄弟链表表示法类型定义：

Typedef struct tnode{
    DataType data;
    struct tnode *son,*brother;
}*Tree;

 

树、森林与二叉树的关系

1. 一般树转化为二叉树

(1). 各兄弟之间加连线；

(2). 对任一结点，除最左孩子外，抹掉该结点与其余孩子的各枝；

(3). 以根为轴心，将连线顺时针转450 。

一棵树唯一对应一棵二叉树，二叉链表的结构形式与兄弟链表完全相同，但结点中指针的含义不同。

 

2. 森林转化为二叉树

(1). 将每棵树转换成相应的二叉树；

(2). 将转换得到的各棵二叉树的根结点看做是兄弟连接起来。

最终将多个子树转化为二叉树，二叉树每个结点的左子树是孩子，右子树是兄弟。

 

3. 二叉树转化为一般树

(1). 从根结点起；

(2). 该结点 左孩 和 左孩右枝上的结点依次作为该结点孩子；

(3). 重复第1步。

以下是将多棵树转化成的二叉树还原成一般树的过程。

 

树和森林的遍历

1. 树的遍历

(1). 先序遍历：先访问根结点，然后依次先序 遍历根的每棵子树。

(2). 后序遍历：先依次后序遍历每棵子树，最后访问根结点。

(3). 层次遍历：从根结点开始，从下至下，从左往右依次访问结点。

树的后序遍历之所以对应转化后的二叉树的中序遍历，是因为后序遍历都是先遍历其子节点，而转化后的二叉树的中序遍历中，左边的是孩子节点，按照 左、根、右的顺序，也是先访问孩子节点，再访问根节点。

 

2.森林的遍历

(1). 先序遍历森林

先序遍历森林中第一棵树的根结点的子树组成的森林，然后先序遍历其余的树组成的森林。

(2). 中序遍历森林

中序访问森林中第一棵树的根结点的子树组成的森林，然后中序遍历其余的树组成的森林。