树的存储结构
标签: 数据结构
学习人数: 19.6k

树中的某个结点的孩子可以有多个,所以仅仅使用简单的顺序结构或者链式结构是不能完全表示一整棵树的。
充分利用顺序存储结构和链式存储结构的特点,完全可以实现对树的存储结构的表示
我们表示一棵树的方法有:双亲表示法孩子表示法孩子兄弟表示法

对于双亲表示法:我们先将双亲结点存入,我们每插入一个结点都是知道双亲结点位置的,数据可以直接插入。使用顺序存储结构更加方便
而对于孩子表示法,我们每次插入一个结点,对其子树的位置存放暂不确定,所有使用链式存储结构占主要

(一)双亲表示法
以双亲作为索引的关键词的一种存储方式
每个结点只有一个双亲,所以选择顺序存储占主要
以一组连续空间存储树的结点,同时在每个结点中,附设一个指示其双亲结点位置的指针域

1.结点结构 

2.结点结构定义

/*树的双亲表示法结点结构定义*/
#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, n;    //r是根位置,n是结点数
}PTree;

3.优缺点分析
优点:parent指针域指向数组下标,所以找双亲结点的时间复杂度为O(1),向上一直找到根节点也快
缺点:由上向下找就十分慢,若要找结点的孩子或者兄弟,要遍历整个树

 

(二)孩子表示法(主要关注孩子结点)
由于每个结点可有多个子树(无法确定子树个数),可以考虑使用多重链表来实现。

根据树的度来设置孩子域的个数,例如本例中度为3,设置3个孩子域

/*树的孩子表示法结点结构定义*/
#define MAX_TREE_SIZE 100

typedef int TElemType;

typedef struct PTNode    //结点结构
{
    TElemType data;    //结点数据
    int child1;    //孩子1结点
    int child2;    //孩子2结点
    int child3;    //孩子3结点
}PTNode;

typedef struct //树结构
{
    PTNode nodes[MAX_TREE_SIZE];    //结点数组
    int r, n;    //r是根位置,n是结点数
}PTree;

 缺点:占用了大量不必要的孩子域空指针
以其为标准:需要3n个指针域,实际上有用n-1个(除了根节点,其他n-1个都向上需要一条边),则有2n+1个无用,浪费

 

(三)孩子兄弟表示法
上面从双亲,孩子角度研究树的结构,下面我们从树的结点的兄弟角度来研究
任意一棵树,他的结点的第一个孩子如果存在就是唯一结点,他的右兄弟如果存在,也是唯一的,因此,我们设置两个指针,分别指向该结点的第一个孩子和该结点的右兄弟


n个结点,有2n个指针域,有n-1条边,空n+1个指针...

登录查看完整内容


课后作业

课后习题

 

【2016年真题】若森林F有15条边、25个节点,则F包含树的个数是()
A.8        B.9        C.10        D.11

参考答案:C


登录后开始许愿

2 条上岸许愿
愁久骑士
2021年6月1日 09:48

分析:森林中树的个数与结点数的关系推导。
先看一般性的解决策略:根据一棵树的边数+1=结点数。
可以知道,每多一棵树,结点数就少一个。
即,
一棵树时,边数 = 结点数-1
两棵树时,边数 = 结点数-2
….
n棵树时,边数 = 结点数-n

于是得到:25-15 = 10.

有时候,可能过于关注局部特征,没能体会到宏观的特性。但是可用特值迅速解决:15条边全是一棵树的,那么这棵树有16个结点,剩下9个结点都不再形成边,即一个结点算一棵树。那么,共1+9 = 10棵树。

赞(0)
愁久骑士
2021年6月1日 09:48

分析:森林中树的个数与结点数的关系推导。
先看一般性的解决策略:根据一棵树的边数+1=结点数。
可以知道,每多一棵树,结点数就少一个。
即,
一棵树时,边数 = 结点数-1
两棵树时,边数 = 结点数-2
….
n棵树时,边数 = 结点数-n

于是得到:25-15 = 10.

有时候,可能过于关注局部特征,没能体会到宏观的特性。但是可用特值迅速解决:15条边全是一棵树的,那么这棵树有16个结点,剩下9个结点都不再形成边,即一个结点算一棵树。那么,共1+9 = 10棵树。

赞(0)