最佳方案是二叉樹的存儲結構採用

A. 1、二叉樹採用順序存儲結構進行存儲，如圖所示

答案如下：

B. 若二叉樹採用二叉鏈表存儲結構，要交換其所有分支結點左、右子樹的位置，利用( )遍歷方法最合適。

答案：C。用二叉鏈表存儲結構也就是左孩子右兄弟的存儲結構。

後序遍歷比較合理。正常的邏輯應該就是：做好當前結點子樹內部的交換，然後交換當前結點的左右子樹。剛好符合後序遍歷的演算法邏輯。

1、交換好左子樹

2、交換好右子樹

3、交換左子樹與右子樹

其他演算法如先序和按層次其邏輯都差不多，即訪問當前結點時交換其左右子樹。從邏輯上來看稍顯別扭一點點。因此說最合適應該是後序遍歷，但是從實現上來說先序和按層次都是可以的。

1、交換左子樹與右子樹

2、遍歷左子樹

3、遍歷右子樹

按層次遍歷

1、根結點入隊列

2、出隊列，交換其左右子樹，將子樹的根入隊列

3、重復2直到隊列為空

中序遍歷相對較難實現一些。

(2)最佳方案是二叉樹的存儲結構採用擴展閱讀：

樹的遍歷是樹的一種重要的運算。樹的3種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和後序遍歷。

以這3種方式遍歷一棵樹時，若按訪問結點的先後次序將結點排列起來，就可分別得到樹中所有結點的前序列表、中序列表和後序列表。相應的結點次序分別稱為結點的前序、中序和後序。

C. 二叉樹的存儲方式有哪些

二叉樹的存儲方式通常有動態存儲。用結構體表示二叉樹的一個節點。用數據域保持保存節點的值，用鏈接語保存兩個孩子的指針。還有就是採用滿二叉樹的順序存儲方式。

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

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

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

二叉樹演算法思路：

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

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

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

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

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

E. 若二叉樹採用二叉鏈表作存儲結構，要交換其所有分支結點的左右子樹的位置，採用（）遍歷方法最合適

顯然後序遍歷比較合理。正常的邏輯應該就是：做好當前結點子樹內部的交換，然後交換當前結點的左右子樹。剛好符合後序遍歷的演算法邏輯。
1. 交換好左子樹
2. 交換好右子樹
3. 交換左子樹與右子樹
其他演算法如先序和按層次其邏輯都差不多，即訪問當前結點時交換其左右子樹。從邏輯上來看稍顯別扭一點點。因此說最合適應該是後序遍歷，但是從實現上來說先序和按層次都是可以的。
1. 交換左子樹與右子樹
2. 遍歷左子樹
3. 遍歷右子樹
按層次遍歷
1. 根結點入隊列
2. 出隊列，交換其左右子樹，將子樹的根入隊列
3. 重復2直到隊列為空
中序遍歷相對較難實現一些

F. 順序存儲是二叉樹常用的存儲結構嗎

二叉樹的存儲結構
二叉樹是非線性結構，即每個數據結點至多隻有一個前驅，但可以有多個後繼。它可採用順序存儲結構和鏈式存儲結構。
1．順序存儲結構
二叉樹的順序存儲，就是用一組連續的存儲單元存放二叉樹中的結點。因此，必須把二叉樹的所有結點安排成為一個恰當的序列，結點在這個序列中的相互位置能反映出結點之間的邏輯關系，用編號的方法從樹根起，自上層至下層，每層自左至右地給所有結點編號,缺點是有可能對存儲空間造成極大的浪費，在最壞的情況下，一個深度為k且只有k個結點的右單支樹需要2k-1個結點存儲空間。依據二叉樹的性質，完全二叉樹和滿二叉樹採用順序存儲比較合適，樹中結點的序號可以唯一地反映出結點之間的邏輯關系，這樣既能夠最大可能地節省存儲空間，又可以利用數組元素的下標值確定結點在二叉樹中的位置，以及結點之間的關系。圖5-5(a)是一棵完全二叉樹，圖5-5（b）給出的圖5-5(a)所示的完全二叉樹的順序存儲結構。

(a) 一棵完全二叉樹 (b) 順序存儲結構
圖5-5 完全二叉樹的順序存儲示意圖
對於一般的二叉樹，如果仍按從上至下和從左到右的順序將樹中的結點順序存儲在一維數組中，則數組元素下標之間的關系不能夠反映二叉樹中結點之間的邏輯關系，只有增添一些並不存在的空結點，使之成為一棵完全二叉樹的形式，然後再用一維數組順序存儲。如圖5-6給出了一棵一般二叉樹改造後的完全二叉樹形態和其順序存儲狀態示意圖。顯然，這種存儲對於需增加許多空結點才能將一棵二叉樹改造成為一棵完全二叉樹的存儲時，會造成空間的大量浪費，不宜用順序存儲結構。最壞的情況是右單支樹，如圖5-7 所示，一棵深度為k的右單支樹，只有k個結點，卻需分配2k－1個存儲單元。

(a) 一棵二叉樹 (b) 改造後的完全二叉樹

(c) 改造後完全二叉樹順序存儲狀態
圖5-6 一般二叉樹及其順序存儲示意圖

(a) 一棵右單支二叉樹 (b) 改造後的右單支樹對應的完全二叉樹

(c) 單支樹改造後完全二叉樹的順序存儲狀態
圖5-7 右單支二叉樹及其順序存儲示意圖
結構5-1二叉樹的順序存儲

#define Maxsize 100 //假設一維數組最多存放100個元素
typedef char Datatype; //假設二叉樹元素的數據類型為字元
typedef struct
{ Datatype bt[Maxsize];
int btnum;
}Btseq;

2．鏈式存儲結構
二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。
通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址。其結點結構為：

其中，data域存放某結點的數據信息；lchild與rchild分別存放指向左孩子和右孩子的指針，當左孩子或右孩子不存在時，相應指針域值為空（用符號∧或NULL表示）。利用這樣的結點結構表示的二叉樹的鏈式存儲結構被稱為二叉鏈表，如圖5-8所示。

(a) 一棵二叉樹 (b) 二叉鏈表存儲結構
圖5-8 二叉樹的二叉鏈表表示示意圖
為了方便訪問某結點的雙親，還可以給鏈表結點增加一個雙親欄位parent,用來指向其雙親結點。每個結點由四個域組成，其結點結構為：

這種存儲結構既便於查找孩子結點，又便於查找雙親結點；但是，相對於二叉鏈表存儲結構而言，它增加了空間開銷。利用這樣的結點結構表示的二叉樹的鏈式存儲結構被稱為三叉鏈表。
圖5-9給出了圖5-8 (a)所示的一棵二叉樹的三叉鏈表表示。

圖5-9二叉樹的三叉鏈表表示示意圖
盡管在二叉鏈表中無法由結點直接找到其雙親，但由於二叉鏈表結構靈活，操作方便，對於一般情況的二叉樹，甚至比順序存儲結構還節省空間。因此，二叉鏈表是最常用的二叉樹存儲方式。
結構5-2二叉樹的鏈式存儲
#define datatype char //定義二叉樹元素的數據類型為字元
typedef struct node //定義結點由數據域，左右指針組成
{ Datatype data;
struct node *lchild,*rchild;
}Bitree;

G. 採用順序存儲方法和鏈式存儲方法分別畫出圖6.1所示二叉樹的存儲結構。【在線等】

線性是線性，順序是順序，線性是邏輯結構，順序是儲存結構，兩者不是一個概念。線性是指一個節點只有一個子節點，而樹，或二叉樹一個節點後有多個子節點，且子節點不能相互聯系。

順序存儲可能會浪費空間(在非完全二叉樹的時候)，但是讀取某個指定的節點的時候效率比較高。

鏈式存儲相對二叉樹比較大的時候浪費空間較少，但是讀取某個指定節點的時候效率偏低。

二叉樹的順序存儲，尋找後代節點和祖先節點都非常方便，但對於普通的二叉樹，順序存儲浪費大量的存儲空間，同樣也不利於節點的插入和刪除。因此順序存儲一般用於存儲完全二叉樹。

鏈式存儲相對順序存儲節省存儲空間，插入刪除節點時只需修改指針，但回尋找指定節點時很不方便。不過普通答的二叉樹一般是用鏈式存儲結構。

(7)最佳方案是二叉樹的存儲結構採用擴展閱讀：

(1)完全二叉樹——若設二叉樹的高度為h，除第h層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。

(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL演算法），它是一棵二叉排序樹，且具有以下性質：是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。

二叉樹是樹的一種特殊情形，是一種更簡單而且應用更加廣泛的樹。

H. 二叉樹採用鏈表存儲結構，實現建立、遍歷（先序、中序、後序）、求結點總數、葉子數、度為1.2的結點數。

前幾天寫的，輸入二叉樹的廣義表形式，建立二叉樹的鏈式存儲。輸出的是中序。有注釋。例如輸入：a(b,c(d,e(f)),g,h(i))
#include<stdio.h>
#include<stdlib.h>
int n=0; //全局變數
struct tree //二叉樹結構體
{
char data;
struct tree *lc;
struct tree *rc;
};
tree *creat(char a[]) //創建樹的二叉樹
{
tree *h;
h=(tree *)malloc(sizeof(tree));
h->lc=NULL;
h->rc=NULL;
if(a[n]!=')'&&a[n]!='('&&a[n]!=',') //當a[n]為字母存入a[]
{
h->data=a[n];
n++;
}
if(a[n]=='(') //a[n]為左括弧對h->lc遞歸操作
{
n++;
h->lc=creat(a);
}
if(a[n]==',') //a[n]為逗號對h->rc遞歸操作
{
n++;
h->rc=creat(a);
return h;
}
if(a[n]==')') //a[n]為右括弧返回h
{
n++;
return h;
}
else
return h;

}
void print(tree *h) //二叉樹中序輸出
{
if(h!=NULL)
{
print(h->lc);
printf("%c",h->data);
print(h->rc);
}

}

int high(char a[]) //判斷樹的高度
{
int i=0,max=0,p=0;
while(a[i]!=0)
{
if(a[i]=='(')
{
p++;
if(max<i)
max=p;
}
if(a[i]==')')
p--;
i++;
}
if(p!=0)
{
printf("左右括弧數不等,輸入錯誤\n"); //判斷左右括弧數是否相等
exit(1);
}
return max+1;
}
void main() //主函數
{
int i=0;
tree *h;
char a[50]={0};
gets(a);
while(a[i]!=0) //判斷各種可能出現的輸入錯誤
{

if(i==0&&(a[i]=='('||a[i]==')'||a[i]==',')) //判斷數組首元素是否為字母
{
printf("首節點錯誤\n");
exit(1);
}
if(a[i]=='(') //左括弧之前一定是字母
{
if(a[i-1]=='('||a[i-1]==')'||a[i-1]==',')
{
printf("輸入錯誤\n");
exit(1);
}
}
if(a[i]!='('&&a[i]!=')'&&a[i]!=',') //兩個字母不能在一起
{
if(a[i+1]!='('&&a[i+1]!=')'&&a[i+1]!=',')
{
printf("輸入錯誤,兩個字母不能在一起\n");
exit(1);
}
}
i++;
}
h=creat(a); //創建樹
printf("該樹的高度為:%d\n",high(a));
printf("該二叉樹的中序輸出為:");
print(h);
printf("\n");
}

I. 完全二叉樹的存儲結構通常採用順序存儲結構()

正確。

一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為i（1≤i≤n）的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。

如果對滿二叉樹的結點進行編號, 約定編號從根結點起, 自上而下, 自左而右。則深度為k的, 有n個結點的二叉樹, 當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時, 稱之為完全二叉樹。

(9)最佳方案是二叉樹的存儲結構採用擴展閱讀：

判斷一棵樹是否是完全二叉樹的思路

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

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

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

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

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