数据结构-树的定义和存储

2019-01-11  本文已影响15人  lionsom_lin

一、基本概念

树的定义

树(Tree)是 n(n >= 0)个结点的有限集。

  • n = 0 时,称为空树;
  • n > 0 时,为非空树,在非空树中:
    • (1) 有且只有一个特定的称为根(Root)的结点;
    • (2) n > 1 时,其余结点可分为 m(m>0)个互不相交的有限集,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree);

注意:
1、n > 0 时根结点是唯一的,不可能存在多个根结点。
2、m > 0 时,子树的个数没有限制,但它们一定是互不相交的。

两个结构就不符合树的定义,因为它们都有相交的子树。

相关术语

结点关系 结点的层次 举例 森林

二、树的存储结构

对于存储结构,可能会联想到前面的 顺序存储链式存储结构。但是对于树这种可能会有很多孩子的特殊数据结构,只用顺序存储结构或者链式存储结构很难实现,
不过充分利用顺序存储和链式存储结构的特点,完全可以实现对树的存储结构的表示。产生主要的三种存储结构表示法:双亲表示法、孩子表示法、孩子兄弟表示法。

2.1、双亲表示法

我们假设 以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。
也就是数组中存放一个结构体,结构体大致如下:

struct
/* 树的双亲表法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int  ElemeType;

typedef struct PTNode{ // 结点结构
    ElemeType data; //结点数据
    int parent;    // 双亲位置
}PTNode;

typedef struct { // 树结构
    PTNode nodes[MAX_TREE_SIZE];   // 结点数组
    int r; // 根的位置
    int n; // 结点数
}PTree;
双亲表示法

双亲表示法的特点

对结构体拓展,对其进行改进

可如果我们要知道结点的孩子是什么,对不起,请遍历整个结构才行。
这真是麻烦,能不能改进一下呢?
当然可以。我们增加一个结点最左边孩子的域,不妨叫它长子域,这样就可以很容易得到结点的孩子。如果没有孩子的结点,这个长子域就设置为-1,如下图:

对struct进行拓展

2.2、双亲表示法

初始

树的度是3,所以我们的指针域的个数是3,这种方法实现如图

多重链表表示法

这种方法对于树中各结点的度相差很大时,显然是很浪费空间的,因为有很多的结点,它的指针域都是空的。不过如果树的各结点度相差很小时,那就意味着开辟的空间被充分利用了,这时存储结构的缺点反而变成了优点。

改进

改进方案每个结点指针域的个数等于该结点的度,我们专门取一个位置来存储结点指针域的个数,如下图:

改进,节省空间

这种方法克服了浪费空间的缺点,对空间利用率是很高了,但是由于各个结点的链表是不相同的结构,加上要维护结点的度的数值,在运算上就会带来时间上的损耗。

再次改进

我们为了要遍历整棵树,把每个结点放到一个顺序存储结构的数组中是合理的,但每个结点的孩子有多少是不确定的,所以我们再对每个结点的孩子建立一个单链表体现它们的关系 。

结构体 再次改进

这样的结构对于我们要查找某个结点的某个孩子,或者找某个结点的兄弟,只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的,对头结点的数组循环即可。
但是,这也存在着问题,我如何知道某个结点的双亲是谁呢?比较麻烦,需要整棵树遍历才行,难道就不可以把双亲表示法和孩子表示法综合一下吗?当然是可以。

最终 - 双亲孩子表示法
双亲孩子表示法

2.3、孩子兄弟表示法 - 将复杂树变为二叉树

结构体 image.png

其实这个表示法的最大好处是它把一棵复杂的树变成了一棵二叉树。我们把上图变形就成了下图这个样子:

image.png

最后,如果真的有必要,完全可以再增加一个parent指针域来解决快速查找双亲的问题。

相关文档参考

引用《大话数据结构》作者:程杰
数据结构(十三)——树
树的三种存储结构
【数据结构】树的定义和树的三种存储结构

上一篇下一篇

猜你喜欢

热点阅读