树与二叉树的存储结构

手机软件开发 · 2024-9-6 12:23:20

树的存储结构

双亲表现法：

除了树的根节点之外，别的每个结点不肯定有孩子，但是肯定有且仅有一个双亲。
假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示双亲结点在数组中的位置
结点结构如下:此中data是数据域，存储结点的数据信息。而parent是指针域，存储该节点的双亲在数组中的下标。
如答应以根据结点的parent指针很轻易找到它的双亲结点，可如果须要知道孩子结点，则须要遍历整个树结构。故可以增长一个指针域指向最左边孩子。同样的，也可以增长指向右兄弟的指针域来表现兄弟关系。

双亲表现法示例如下：
孩子表现法：

由于树中每个结点大概有多棵子树，可以思量用多重链表，即每个结点有多个指针域，此中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表现法。不外，树中的每个结点的度，也就是它的孩子个数是差别的。以是可以计划两种方案办理：
1、指针域的个数就等于树的度（树的度等于树中各个结点的度的最大值d）,此中data是数据域，child1到childd是指针域，用来指向该结点的孩子结点（对于树中各个结点的度相差很大时，浪费空间）

2.每个结点指针域的个数等于该结点的度，专门取一个位置存储结点指针域的个数（虽然降服了浪费空间的缺点，但是时间上的斲丧增大，须要维护度的数值）

综上，有了孩子表现法，把每个结点的孩子结点分列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又构成一个线性表，接纳序次存储结构，存放金一个一维数组中。
为此，计划两种结点结构，一个是孩子链表的孩子结点，如图所示,此中child为数据域，用于存储某个结点在表头数组中的下标。next为指针域，用于存储指向某结点的下一个孩子结点的指针。

另一个是表头数组的表头结点，此中data为数据域，存储某个结点的数据信息，firstchild是头指针域，存储该结点的孩子链表的头指针。

但是这也存在着标题，须要通过遍历查找某个结点的双亲，故改进上述表头数组的表头结点，再附加一个指向双亲结点的指针域,把这种方法称为双亲孩子表现法。

孩子兄弟表现法：

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。此中data是数据域，firstchild为指针域，存储该结点的第一个孩子结点的所在，rightsib是指针域，存储该结点的右兄弟结点的所在。

这个方法的最大利益是可将一棵复杂的树变成一棵二叉树，可以充实使用二叉树的特性和算法处置处罚这棵树。
二叉树的存储结构

二叉树的序次存储结构：

用一维数组存储二叉树的结点，而且结点的存储位置，也就是数组的下标要能表现结点之间的逻辑关系，比如双亲与孩子之间的关系

可以看出，完全二叉树可以用序次结构表现出来，当然对于一样平常的二叉树，只管层序编号不能反应逻辑关系，但是可以将其按完全二叉树编号，只不外，将不存在的结点设置为空而已。
但是，下面这种极端环境下，一棵深度为k的斜树，只有k的结点，却须要分配2k-1个存储单元空间，非常浪费空间

二叉树的链式存储结构

二叉树每个结点最多有两个孩子，全部为它计划一个数据域和两个指针域的结点，称如许的链表为二叉链表。此中data为数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。（如果须要，还可以增长一个指向其双亲的指针域，那样就称之为三叉链表）

树与二叉树的存储结构

所属分类: 问答交流

新帖推荐: 30日

推荐作品