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


全屏播放
赞赏支持

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

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

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

1.结点结构 

2.结点结构定义

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

typedef int TElemType;

typedef struct PTNode    //结点结构
{
    TElemType dat...
登录查看完整内容


课后作业

课后习题

 

【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棵树。

愁久骑士
2021年6月1日 09:48

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

于是得到:25-15 = 10.

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