双亲表示法存储一维数组

1. 树的存储表示是什么

树的存储结构根据应用的不同而不同，有的从双亲的角度考虑，引出了双亲表示法，有的从孩子的角度考虑，给出孩子表示法，还有的从孩子和兄弟的角度来讨论。这些都是人们在大量的应用中所使用的不同形式的存储结构，这里介绍常用的双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法。

1.双亲表示法由树的定义可知，树中每个结点都有且仅有一个双亲结点，根据这一特性，可以用一组连续的一维数组来存储树中的各个结点（一般按层次存储），数组中的一个元素对应树中的一个结点，其中包括结点的数据信息以及该结点的双亲在数组中的下标。树的这种存储方法称为双亲表示法，双亲表示法的结点结构如图1所示，其中，data表示数据域，存储树中结点的数据信息，parent表示指针域，存储该结点的双亲在数组中的下标。

1.双亲表示法的存储结构2）双亲表示法示例图1所示的树的双亲表示如图1所示，这是一棵树及其双亲表示法的存储结构。根结点A无双亲，所以parent的值为－1，G、H和I的parent值为4，表示它们的双亲是下标为4的结点E。这种存储结构利用任一结点的双亲是唯一的性质，可以方便地直接找到任一结点的双亲结点，但求结点的孩子结点时需要扫描整个数组。

图1树的双亲表示法示例

2. 数据结构问题什么是树的双亲表示法

从树的定义可知，除根结点外，树中的每个结点都有唯一的一个双亲结点。根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各结点。树中的结点除保存结点本身的信息之外，还要保存其双亲结点在数组中的位置（数组的序号），树的这种表示法称为双亲表示法。
树的双亲表示法对于实现 Parent(t)操作和 Root()操作非常方便。 Parent(t)操作可以在常量时间内实现，反复调用Parent(t)操作，
直到遇到无双亲的结点（其
pPos值为-1）时，便找到了树的根，这就是Root()操作的执行过程。但要实现查找孩子结点和兄弟结点等操作非常困难，因为这需要查询整个数组。要实现这些操作，需要在结点结构中增设存放第1个孩子在数组中的序号的域和存放第1个兄弟在数组中的序号的域。

3. 一维数组在内存中的存放方式是怎么样的

一维数组在内存中的存放方式是：

1、硬盘上不可能运行程序的，必须在内存中运行。

2、低地址到高地址存储 。

3、数组元素通常也称为下标变量。

4、在C语言中，只能逐个地使用下标变量， 不能用一个语句输出整个数组。

5、int a[10]和t=a[6]分别是定义数组长度为10和引用a数组中序号为6的元素，6不代表数组长度。

(3)双亲表示法存储一维数组扩展阅读：

数组（Array）是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按有序的形式组织起来的一种形式。 这些有序排列的同类数据元素的集合称为数组。

数组是用于储存多个相同类型数据的集合。

在C语言中， 数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

4. 顺序存储表示法为什么不是树的存储形式

顺序存储表示法是树的存储形式的原因：顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。

对于一般的家谱树(一般的多叉树)来说，我们可以很清楚的看出层次关系，树的层数表示代数（一共多少代人），树的最后一层表示最后一代人，由于多叉链表法表示的不方便，因此被迫无奈采用孩子兄弟表示法(二叉链表法)。

结构

二叉树的顺序存储就是用一组连续的存储单元存放二又树中的结点元素，一般按照二叉树结点自上向下、自左向右的顺序存储。使用此存储方式，结点的前驱和后继不一定是它们在逻辑上的邻接关系，非常适用于满二又树和完全二又树。根据完全二叉树和满二叉树的特性，假设将图1中的完全二又树存放在一维数组bree中，将发现结点的编号正好与数组元素的下标对应。

5. 完全二叉树为什么最适合顺序存储结构

顺序存储充分利用满二叉树的特性，即每层的节点数分别为1、2、4、8等等2i+1，一个深度为i的二叉树最多只能包含2i-1个节点，因此只要定义一个长度为2i-1的数组即可存储这颗二叉树。

对于普通的不是满二叉树的，那些空出来的节点对应的数组元素留空即可，因此顺序存储会造成一定的空间浪费。如果是完全二叉树，就不会有空间浪费的情况；若是只有右子树，那么会造成相当大的浪费。

二叉树算法思路：

1、如果树为空，则直接返回错。

2、如果树不为空：层序遍历二叉树。

3、如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列。

4、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树。

5、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。

6. y采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比！

一．模型表示：
计算机使用数字代码来存储字符，ASC II码是最常用的编码。一个ASC II码值占一个字节(8个二进制位)，其最高位(b7)用作奇偶校验位，共128个。要对一个文本文件进行压缩，就是要对文件内的字符重新编码，使出现次数较多的字符用较短的编码存储，而出现次数少的字符则采用相对较长的编码存储，最终使压缩后整个文件的大小小于原文件。
这里采用哈夫曼编码方式来对每个字符重新编码，因为哈夫曼树具有最小带权路径长度的性质，能够生成用于压缩的二进制前缀码。程序使用的 “静态统计模型”，也就是说在编码前统计要编码的信息中所有字符的出现频率，字符的出现频率即为字符的权，然后根据统计出的信息建立编码树，进行编码。利用所得的编码生成压缩文件。由于采用的是“静态统计模型”，在压缩文件里必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身。
在解压缩时，首先从文件头读入保存的编码信息，从而对后续的编码解码，还原成ASCII的形式，生成与原文相同的文件。

二．概要设计：
由于一棵有n个叶子结点的哈夫曼树共有2n-1个结点，考虑到程序的执行效率，可以将二叉树存放在连续空间里（静态链表），空间的每个结点内仍有左子树、右子树、双亲等指针，以便译码和解码。即存储在一个大小为2n-1的一维数组中，每个结点的结构为：
struct HNode
{
char elem; //保存结点所表示的字符（主要用于译码时）
unsigned long weight; //保存结点的权值，对于叶子，即为字符的出现次数
int parent, lchild, rchild; //保存结点的双亲，左右孩子的位置