1.树的存储结构：

(1)双亲表示法

是一种顺序保存方法，即用数组存储。

每个结点有两个域:

data是结点的数据元素;

parent是指出该结点的双亲结点在数组中的下标;

本文引用地址：//emb.hqyj.com/Column/7465.html

树的双亲表示法说明：

#define MAX-TREE-SIZE 100

typedef struct PTNode{

ElementType data;

int parent; // 该结点的双亲的下标

} PTNode;

typedef struct {

PTNode nodes[MAX-TREE-SIZE];

int n; //树的结点数

} PTree;

例子：使用双亲法存储森林

(2)孩子(子女)表示法

typedef struct CTNode { //孩子结点(表结点)

int child;

struct CTNode *next;

} *ChildPtr;

tyPedef struct { //头结点

TElemType data;

ChildPtr firstchild;

}CTBox;

typedef struct { //孩子链表头指针

CTBox nodes[MAX_TREE_SIZE];

int n，r; //结点数和根的位置;

}CTree;

带双亲的孩子链表存储表示

typedef struct CTNode { //孩子结点(表结点)

int child;

struct CTNode *next;

} *ChildPtr;

typedef struct{ //头结点

TElemType data; int parent;

ChildPtr firstchild;

}CTBox;

typedef struct { //孩子链表头指针

CTBox nodes[MAX_TREE_SIZE];

int n，r; //结点数和根的位置;

}CTree;

(3)孩子兄弟表示法(也称二叉树表示法或二叉链表表示法)

结点结构(CSNode)：

firstchild:指向该结点的第一个孩子

nextsibling:指向该结点的下一个兄弟

typedef struct CSNode {

TElemType data;

struct CSNode * firstchild， * nextsihling;

}CSNode，*CSTree;

例子：用孩子兄弟法存储树

2.树与森林的遍历

树的遍历:按根的次序区分有两种遍历次序

(1)先根序遍历：

若树非空，则访问根节点;从左到右根遍历根的每棵子树;

遍历上面的树：A B E C F D G H I J

(2)后根遍历：

若树非空，则从左到右后根序遍历根的每棵子树;访问根结点;

遍历上面的树：E B F C H I J G D A

森林的遍历：

森林的遍历是基于树的遍历完成的，对应有两种遍历次序

(1)先序遍历

访问第一棵树的根;

先序遍历第一棵树中的根结点的子树森林;

先序遍历其余的树所构成的森林;

(2)中序遍历

中序遍历第一棵树的子树;

访问第一棵树的根;

中序遍历其余的树构成的森林;

3.森林与二叉树的转换

在森林与二叉树之间存在一一对应的关系

(1)森林=>二叉树的转换

自然转换法：凡是兄弟用线连起来，然后去掉双亲到子女的连线，但保留双亲到其第一子女的连线，后转45度。

(2)二叉树=>森林的转换

自然转换法：

若某结点是其双亲的左孩子，则该结点的右孩子、右孩子的右孩子...,都是与该结点的双亲连接起来，后去掉所有双亲到右孩子的连线。