首页 > 代码库 > 树的存储结构以及实现代码

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

 

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

 

 

 

 

 

 

 

2、双亲表示法

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

  如下图所示:

data parent

 

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

下标dataparentfirstchildrightsibling
0A-1-1-1
1B032
2C04-1
3D16-1
4E295
5F2-1-1
6G3-17
7H3-18
8I3-1-1
9J4-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;

  

 

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