判斷數組是否適合存儲在二叉樹

A. 完全二叉樹為什麼最適合順序存儲結構

順序存儲充分利用滿二叉樹的特性，即每層的節點數分別為1、2、4、8等等2i+1，一個深度為i的二叉樹最多隻能包含2i-1個節點，因此只要定義一個長度為2i-1的數組即可存儲這顆二叉樹。

對於普通的不是滿二叉樹的，那些空出來的節點對應的數組元素留空即可，因此順序存儲會造成一定的空間浪費。如果是完全二叉樹，就不會有空間浪費的情況；若是只有右子樹，那麼會造成相當大的浪費。

二叉樹演算法思路：

1、如果樹為空，則直接返回錯。

2、如果樹不為空：層序遍歷二叉樹。

3、如果一個結點左右孩子都不為空，則pop該節點，將其左右孩子入隊列。

4、如果遇到一個結點，左孩子為空，右孩子不為空，則該樹一定不是完全二叉樹。

5、如果遇到一個結點，左孩子不為空，右孩子為空；或者左右孩子都為空；則該節點之後的隊列中的結點都為葉子節點；該樹才是完全二叉樹，否則就不是完全二叉樹。

B. 數組不適合作為任何二叉樹的存儲結構

這話不對，數組可以用來存儲一棵滿二叉樹，也可以用它存儲普通的二叉樹（會浪費一些存儲空間），還可以以下標形式模擬鏈式存儲任意的二叉樹（用表示下標的數字來代替lchild和rchild指針）。

C. 什麼樣的二叉樹適合用數組存儲

完全二叉樹適合用數組存儲，它在使用時可以沒有存儲單元的浪費。

D. 用一維數組存儲二叉樹有什麼缺點

對存儲空間造成極大的浪費。用一維數組存儲二叉樹缺點對存儲空間造成極大的浪費，一棵深度為k的右斜樹，它只有k個結點，卻需要2^k-1個結點存儲空間。二叉樹，是樹形結構的一個重要類型。許多實際問題抽象出來的數據結構往往是二叉樹形式，即使是普通的樹也能簡單地轉換為二叉樹，而且二叉樹的存儲結構及其演算法都較為簡單，因此二叉樹顯得特別重要。

E. 寫個演算法判斷一個二叉樹用數組還是指針表示更合適

這個不叫用演算法證明。。 好像沒有這么證明的
是這樣的數組是表示一組連續的存儲空間 如果用數組來存儲一個深度為k 且只有k個節點的單支樹，就是沒有度數為2的節點的樹，至少需要2^k - 1個存儲空間 而用指針 即鏈式存儲空間 就只需要動態分配k個節點的存儲空間 所以用指針表示二叉樹更好 ， 假設如果能用演算法寫的話 思路就是 用2種不同的方法分別建立相同節點個數的二叉樹，然後比較2種方法所用存儲空間的大小。

F. 數據結構——二叉樹

二叉樹 在一般的樹上加了兩個限制條件：

順序儲存結構用一個數組來存放一棵二叉樹，這種方式最適合 完全二叉樹

定義如下

若某結點編號為i，且存在左兒子和右兒子，則他們分別對應

定義如下

G. 怎樣編寫一個程序，把一個有序整數數組放到二叉樹中

將有序數組存儲到二叉樹中，可以考慮用二分法建樹。這樣建出來的二叉樹高度最矮。
TreeNode *BuildTree(int array[], int low, int high)
{
if (low > high)
return NULL;
TreeNode *tmp = (TreeNode *)malloc(sizeof(TreeNode));
tmp->data = array[(low + high) / 2)];
tmp->left = BuildTree(array, low, (low + high) / 2 - 1);
tmp->right = BuildTree(array, (low + high) / 2 + 1, high);
return tmp;
}