树的三种存储结构_树的双亲结构转孩子链表结构

树的三种存储结构

一、双亲表示法
用一组连续的空间存储树的结点。每个节点中，除了有数据域，还附加一个指示数，指向其双亲结点在链表中的位置

/************************************************************************/
/* 树的双亲表示存储结构                                                 */
/************************************************************************/
#define MAX_TREE_SIZE 100
typedef int TElemType;
typedef struct PTNode{
	TElemType data;//数据域
	int parent;//双亲位置域
}PTNode;
typedef struct{
	PTNode nodes[MAX_TREE_SIZE];
	int r;//根的位置
	int n;//结点数
}PTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二、孩子表示法
也是用一组连续的空间存储结点数据，只是每个结点包括数据域以及指向其第一个孩子的结点指针，同时从第一个孩子开始，每个孩子指向它的下一个兄弟。

/************************************************************************/
/* 树的孩子链表存储表示                                                 */
/************************************************************************/
typedef struct CTNode{//孩子结点
	int child;
	struct CTNode *next;//指向下一个兄弟
} *Child;
typedef struct{//双亲结点
	TElemType data;
	Child firstChild;
}PTNode;
typedef struct
{
	PTNode nodes[MAX_TREE_SIZE];
	int n;//结点数
	int r;//根个数
}CTree;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、二叉链表表示法（孩子兄弟表示法）
树的二叉链表存储结构和二叉树的二叉链表存储结构一样，都是一个数据域加上两个指针，区别在于二叉树的两个指针代表左右子树，而树的两个指针改变为左为孩子，右为兄弟

/************************************************************************/
/* 树的二叉链表存储表示                                                 */
/************************************************************************/
typedef struct CSNode{
	TElemType data;
	struct CSNode *firstchild,*nextsinling;//左为孩子，右为兄弟
}CSNode,*CSTree;
1
2
3
4
5
6
7

通过树的这种存储结构，也就实现了树到二叉树的转换