树的存储结构以及实现代码

 

1、首先假设有一个树如下：

 

 

 

 

 

 

 

2、双亲表示法

　　我们假设以一组连续空间存储树的结点，在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。这样，每个结点除了知道自己是谁以外，还知道他们的双亲在那里。

　　如下图所示：

data

parent

 

　　由于这种存储结构不能有效的寻找其兄弟结点，我们队这种存储解雇进行修改，插入其第一个第一个孩子firstchild的下标，rightsibling(-1表示没有)的下标，变成

下标	data	parent	firstchild	rightsibling
0	A	-1	-1	-1
1	B	0	3	2
2	C	0	4	-1
3	D	1	6	-1
4	E	2	9	5
5	F	2	-1	-1
6	G	3	-1	7
7	H	3	-1	8
8	I	3	-1	-1
9	J	4	-1	-1

代码如下：

//双亲表示法
#define MAX_TREE_NUM 100        //定义树的最大结点数目
typedef char ElemType;          //定义结点中的数据类型
typedef struct PTNode
{
    int parent;                 //每个结点的双亲所在位置的下标
    ElemType data;              //每个结点中存放的数据
    int firstchild;             //从左边开始数，这个结点第一个孩子的位置（下标）
    int rightsibling;           //从左边开始数，这个结点右边的那个兄弟的下标
}PTNode;
typedef struct PTree
{
    PTNode data[MAX_TREE_NUM];  //树的结点数组
    int r;                      //根节点的位置（下标）
    int n;                      //当前树中结点数目
}PTree;

　　

3、孩子双亲表示法

　　

 

 

 

 

 

 

 

 

代码如下：

typedef struct CNode                    //定义孩子结点，以链表的形式存储孩子和孩子的下标
{
    int child;                          //孩子的下标
    CNode *next;                        //如果存在不止一个孩子，则next用来存放指向下一个孩子的指针，否则为空
}CNode;
typedef struct PNode                    //定义双亲结点
{
    int parent;                         //双亲结点的下标
    struct CNode *firstchild;           //指向第一个孩子结点的指针
    ElemType data;                      //双亲结点中存放的数据
}PNode;

typedef struct PCTree                   //定义一个双亲-孩子存储结构表示的树结构
{
    struct PNode nodes[MAX_TREE_NUM];   //定义一个含有MAX_TREE_NUM个结点的树
    int c;                              //根结点
    int n;                              //当前树中结点数目
}

　　

4、孩子兄弟表示法

 

 

 

 

 

 

 

 

 

代码如下：

//孩子兄弟表示法
typedef struct PNode                    //定义一个孩子-兄弟存储结构表示树
{
    ElemType data;                      //结点中存放的数据
    PNode *firstchild;                  //指向从左边起，第一个孩子结点，没有孩子的结点指向NULL
    PNode *rightsibling;                //指向第一个孩子的右边的一个兄弟结点的指针，如果含有多个兄弟结点，依次指过去（类似单链表）

}PNode;