1.树的存储结构:
(1)双亲表示法
是一种顺序保存方法,即用数组存储。
每个结点有两个域:
data是结点的数据元素;
parent是指出该结点的双亲结点在数组中的下标;
本文引用地址://www.hqyj.com/emb/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)二叉树=>森林的转换
自然转换法:
若某结点是其双亲的左孩子,则该结点的右孩子、右孩子的右孩子...,都是与该结点的双亲连接起来,后去掉所有双亲到右孩子的连线。