A. 二叉樹 兩種存儲結構的優缺點
順序存儲可能會浪費空間，但是讀取某個指定的節點的時候效率比較高，鏈式存儲相對二叉樹比較大的時候浪費空間較少，但是讀取某個指定節點的時候效率偏低O(nlogn)。
在數據的順序存儲中，由於每個元素的存儲位置都可以通過簡單計算得到，所以訪問元素的時間都相同；而在數據的鏈接存儲中，由於每個元素的存儲位置保存在它的前驅或後繼結點中，所以只有當訪問到其前驅結點或後繼結點後才能夠按指針訪問到。
(1)在樹的存儲中擴展閱讀：
分類：
順序存儲方法它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現，由此得到的存儲表示稱為順序存儲結構。順序存儲結構是一種最基本的存儲表示方法，通常藉助於程序設計語言中的數組來實現。
鏈接存儲方法它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構，鏈式存儲結構通常藉助於程序設計語言中的指針類型來實現。
B. 完全二叉樹為什麼最適合順序存儲結構
順序存儲充分利用滿二叉樹的特性，即每層的節點數分別為1、2、4、8等等2i+1，一個深度為i的二叉樹最多隻能包含2i-1個節點，因此只要定義一個長度為2i-1的數組即可存儲這顆二叉樹。
對於普通的不是滿二叉樹的，那些空出來的節點對應的數組元素留空即可，因此順序存儲會造成一定的空間浪費。如果是完全二叉樹，就不會有空間浪費的情況；若是只有右子樹，那麼會造成相當大的浪費。
二叉樹演算法思路：
1、如果樹為空，則直接返回錯。
2、如果樹不為空：層序遍歷二叉樹。
3、如果一個結點左右孩子都不為空，則pop該節點，將其左右孩子入隊列。
4、如果遇到一個結點，左孩子為空，右孩子不為空，則該樹一定不是完全二叉樹。
5、如果遇到一個結點，左孩子不為空，右孩子為空；或者左右孩子都為空；則該節點之後的隊列中的結點都為葉子節點；該樹才是完全二叉樹，否則就不是完全二叉樹。
C. 數據結構--樹和森林
一、 樹的定義：
樹(tree)是n(n>0)個節點的有限集，在任意一棵樹中，(1)有且僅有一個特定的稱為根(root)的節點，(2)當n>1時，其餘節點可分為m(m>0)個互不相交的有限集，而每個集合本身又是一棵樹，稱為根的子樹(subtree)。
從上面樹的定義中可以看到，這是一個遞歸的定義，即樹的定義中又用到了樹的概念。
樹具有下面兩個特點：
(1) 樹的根結點沒有前驅結點，除根結點外的其他結點有且只有一個前驅結點
(2) 樹中所有結點可以有0個或多個後繼結點
根據這兩個特點，可以看出下圖表示的都不是樹。
森林(forest)是m(m≥0)棵互不相交的樹的集合。任何一棵樹，刪除了根結點就變成了森林。
二、 樹的存儲結構
1、 雙親表示法
樹中每個結點都有唯一一個雙親結點，根據這一特性，可以用一組連續的存儲空間（一維數組）存儲樹中的各個結點，數組中每個元素都表示樹中的一個結點，數組元素為結構體類型，這個結構體類型由結點本身的數據和結點的雙親在數組中的序號組成。
樹的雙親表示法對於尋找雙親和根的操作很方便，但是要求某結點的孩子結點，就需要遍歷整個數組，而且也不能反映各兄弟之間的關系，因此找到某結點的兄弟也很困難。
2、 孩子表示法
按如下圖所示的形式存儲。主體是一個與結點個數一樣大小的一維數組，數組的每個元素有兩個域，一個域用於存放結點數據，另一個用於存放指針，該指針指向由該結點孩子組成的單鏈表的首位置。單鏈表的結構也由兩個域組成，一個存放孩子結點在一維數組中的序號，另一個為指針域，指向下一個孩子。
孩子表示法中查找雙親很困難，適用於查找孩子的操作。
3、 雙親孩子表示法
雙親孩子表示法是將雙親表示法和孩子表示法結合起來的方法。如下圖所示，將各節點的孩子結點組成單鏈表，用一維數組順序存儲樹的結點，數組元素包括結點本身的數據，該結點的孩子結點鏈表的頭指針，存儲該結點的雙親在數組中的序號。
4、 孩子兄弟表示法
這種方法的結構體包含：每個結點的數據，指向該結點的第一個孩子結點的指針和指向下一個兄弟結點的指針。
三、 樹轉換為二叉樹
第一步：在樹中所有兄弟結點間加一條連線
第四步：調整位置
五、 二叉樹轉換為樹、森林
七、 森林的遍歷
森林的遍歷分為兩種：前序遍歷和中序遍歷
1、 前序遍歷
A. 訪問森林中第一棵樹的根節點
B. 前序遍歷第一棵樹的根節點的子樹
C. 前序遍歷去掉第一棵樹後剩餘的森林
上圖按照前序遍歷，結果為：A B C D E F G H J I K
2、 中序遍歷
A. 中序遍歷第一棵樹的根節點的子樹
B. 訪問森林中第一棵樹的根結點
C. 中序遍歷去掉第一棵樹剩餘的森林
上圖按照中序遍歷，結果為：B A D E F C J H K I G
D. 圖的五種存儲結構
圖的鄰接矩陣（Adjacency Matrix）： 圖的鄰接矩陣用兩個數組來表示圖。一個一維數組存儲圖中頂點信息，另一個二維數組（一般稱之為鄰接矩陣）來存儲圖中的邊或者弧的信息。從鄰接矩陣中我們自然知道一個頂點的度（對於無向圖）或者有向圖中一個頂點的入度出度信息。
假設圖G有n個頂點，則鄰接矩陣是一個n*n的方陣。
1.對於如果圖上的每條邊不帶權值來說，那麼我們就用真（一般為1）和假（一般為0）來表示一個頂點到另一個頂點存不存在邊。下面是一個圖的鄰接矩陣的定義：
鄰接矩陣法實現帶權值的無向圖的創建如下：
按照如圖輸入各邊（不重復）
測試程序如下：
結果可得該矩陣，證明創建樹成功。 假設n個頂點e條邊的創建，createGraph演算法的時間復雜度為O（n+n*n+e）。如果需要創建一個有向圖，那麼和上面一樣一個一個錄入邊下標和權值。
鄰接矩陣這種存儲結構的優缺點： 缺點是對於邊數相對頂點較少的稀疏圖來說會存在極大的空間浪費。假設有n個頂點,優點是對於有向完全圖和無向完全圖來說鄰接矩陣是一種不錯的存儲結構，浪費的話也只浪費了n個頂點的容量。
在樹的存儲結構一節中我們提到對於孩子表示法的第三種：用一段連續的存儲單元（數組）存儲樹中的所有結點，利用一個單鏈表來存儲數組中每個結點的孩子的信息。對於圖的存儲結構來說，我們也可以利用這種方法實現圖的存儲
鄰接表(Adjacency List): 這種數組與鏈表相結合的存儲方法叫做鄰接表。1.為什麼不也用單鏈表存儲圖的結點信息呢？原因就是數組這種順序存儲結構讀取結點信息速率快。對於頂點數組中，每個數據元素還需要存儲一個指向第一個鄰接頂點的指針，這樣才可以查找邊的信息2.圖中每個頂點Vi(i > 0)的所有鄰接點構成一個線性表 （在無向圖中這個線性表稱為Vi的邊表，有向圖中稱為頂點作為弧尾的出邊表） ，由於鄰接點的不確定性，所以用鏈表存儲，有多少個鄰接點就malloc一個空間存儲鄰接點，這樣更不會造成空間的浪費（與鄰接矩陣相比來說）。3.對於鄰接表中的某個頂點來說，用戶關心的是這個頂點的鄰接點，完全可以遍歷用單鏈表設計成的邊表或者出邊表得到，所以沒必要設計成雙鏈表。
鄰接表的存儲結構：
假設現在有一無向圖G，如下圖：
從鄰接表結構中，知道一個頂點的度或者判斷兩個頂點之間是否存在邊或者求一個頂點的所有鄰接頂點是很容易的。
假設現在有一有向圖G，如下圖：
無向圖的鄰接表創建示例如下：
假設在上圖（無向圖）中的V0V1V2V3頂點值為ABCD，則依據下面測試程序可得結果：
鄰接表的優缺點： 優點是：鄰接表存儲圖，既能夠知道一個頂點的度和頂點的鄰接結點的信息，並且更不會造成空間的浪費。缺點是鄰接表存儲有向圖時，如果關心的是頂點的出度問題自然用鄰接表結構，但是想了解入度需要遍歷圖才知道（需要考慮逆鄰接表）。
十字鏈表(Orthogonal List) ：有向圖的一種存儲方法，它把鄰接表和逆鄰接表結合起來，因此在十字鏈表結構中可以知道一個頂點的入度和出度情況。
重新定義頂點表的結點如下圖：
現在有一有向圖如下圖：
則它的存儲結構示意圖為：
其定義如下：
十字鏈表是用來存儲有向圖的，這樣可以看出一個頂點的出入度信息。對於無向圖來說完全沒必要用十字鏈表來存儲。
在無向圖中，因為我們關注的是頂點的信息，在考慮節約空間的情況下我們利用鄰接表來存儲無向圖。但是如果我們關注的是邊的信息，例如需要刪除某條邊對於鄰接表來說是挺繁瑣的。它需要操作兩個單鏈表刪除兩個結點。因此我們仿照十字鏈表的方式對邊表結點結構重新定義如下圖：
它的鄰接多重表結構為：
多重鄰接表的優點：對於邊的操作相比於鄰接表來說更加方便。比如說我們現在需要刪除(V0,V2)這條邊，只需將69步驟中的指針改為nullptr即可。
邊集數組(edgeset array)： 邊集數組是由兩個數組組成，一個存儲頂點信息，另一個存儲邊的信息，這個邊數組中的每個數據元素由起點下標，終點下標，和權組成（如果邊上含有權值的話）。
邊數組結構如下圖：
邊集數組實現圖的存儲的優缺點：優點是對於邊的操作方便快捷，操作的只是數組元素。比如說刪除某條邊，只需要刪除一個數組元素。缺點是：對於圖的頂點信息，我們只有遍歷整個邊數組才知道，這個費時。因此對於關注邊的操作來說，邊集數組更加方便。
E. 數據結構，樹的常用存儲方式
存入文本文件，每行：孩子節點-父節點。
這樣也方便用Hadoop進行處理。
F. 一個二叉樹按順序方式存儲在一個一維數組中，如圖：
二叉樹按照層序遍歷，依次編號，按照編號的順序，存儲在連續存儲單元的方式就是二叉樹的順序存儲。
G. 什麼是二叉樹的順序存儲
二叉樹的順序存儲是將二叉樹的所有結點，按照一定的次序，存儲到一片連續的存儲單元中
二叉樹的順序存儲必須將結點排成一個適當的線性序列，使得結點在這個序列中的相應位置能反映出結點之間的邏輯關系。這種結構特別適用於近似滿二叉樹。
在一棵具有n個結點的近似滿二叉樹中，當從樹根起，自上層到下層，逐層從左到右給所有結點編號時，就能得到一個足以反映整個二叉樹結構的線性序列。其中每個結點的編號就作為結點。
(7)在樹的存儲中擴展閱讀：
二叉樹的性質：
1、二叉樹第i層上的結點數目最多為2{i-1}(i≥1)。
2、深度為k的二叉樹至多有2{k}-1個結點(k≥1)。
3、包含n個結點的二叉樹的高度至少為log2(n+1)。
4、在任意一棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1。
參考資料來源：網路-二叉樹