雙親表示法存儲一維數組

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; //保存結點的雙親，左右孩子的位置