線索二叉樹能順序存儲嗎

① 關於數據結構的問題

應該是A，雙向鏈表就不說了。
首先應該了解存儲表示方法有四種：
◆ 順序存儲方法：它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構。
◆ 鏈接存儲方法：它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構。
◆ 索引存儲方法：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。
◆ 散列存儲方法：就是根據結點的關鍵字直接計算出該結點的存儲地址。

閉散列表是應該屬於散列存儲，是哈希演算法的一種處理存儲沖突方式，
當由關鍵碼得到的哈希地址一旦產生了沖突,也就是說,該地址已經存放了數據元素,就去尋找下一個空的哈希地址,只要哈希表足夠大,空的哈希地址總能找到,並將數據元素存入. 所以符合散列存儲方法的要求。

而線索二叉樹是索引存儲，它是對二叉樹以某種方式遍歷後，得到二叉樹中所有結點的一個線性序列。這樣，二叉樹中的結點就有了唯一直接前驅結點和唯一直接後繼結點。
在線索二叉樹時，二叉樹採用二叉鏈表作為存儲結構，每個結點有五個域leftChild,leftTag,data,rightTag,rightChild
規定：如果某結點的左指針域為空，令其指向依某種方式遍歷時所得到的該結點的前驅結點，否則指向左孩子。
如果某結點的右指針域為空，令其指向依某種方式遍歷時所得到的該結點的後繼結點，否則指向右孩子（？？）
為了區分一個結點的指針是指向左右孩子還是指向前驅，後繼結點，可用標志為來區分：
如果 leftTag/rightTag=0,那麼指向左/右孩子。
如果 leftTag/rightTag=1,那麼指向前驅/後繼線索。
對一顆二叉樹的遍歷方法不同，得到的線索二叉樹也不同。通常有前序線索二叉樹，中序線索二叉樹，後序線索二叉樹。

② 什麼是二叉樹

二叉樹

在計算機科學中，二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。

二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結點；深度為k的二叉樹至多有2^k-1個結點；對任何一棵二叉樹T，如果其終端結點數為n_0，度為2的結點數為n_2，則n_0=n_2+1。

一棵深度為k，且有2^k-1個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且最後一層或者是滿的，或者是在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。具有n個節點的完全二叉樹的深度為log2n+1。深度為k的完全二叉樹，至少有2^（k-1)個節點，至多有2^k-1個節點。

一、定義

二叉樹在圖論中是這樣定義的：二叉樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二叉樹還要滿足根結點的度不大於2。有了根結點之後，每個頂點定義了唯一的父結點，和最多2個子結點。然而，沒有足夠的信息來區分左結點和右結點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林。

二、基本概念

二叉樹是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：

(1)空二叉樹——如圖(a)；

線索二叉樹的存儲結構

在中序線索樹找結點後繼的規律是：若其右標志為1，則右鏈為線索，指示其後繼，否則遍歷其右子樹時訪問的第一個結點（右子樹最左下的結點）為其後繼；找結點前驅的規律是：若其左標志為1，則左鏈為線索，指示其前驅，否則遍歷左子樹時最後訪問的一個結點（左子樹中最右下的結點）為其前驅。

在後序線索樹中找到結點的後繼分三種情況：

若結點是二叉樹的根，則其後繼為空；若結點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其後繼即為雙親結點；若結點是其雙親的左孩子，且其雙親有右子樹，則其後繼為雙親右子樹上按後序遍歷列出的第一個結點。

數據結構定義為：

/*二叉線索存儲表示*/typedefenum{Link,Thread}PointerTag;/* Link(0)：指針，Thread(1)：線索*/typedefstruct BiThrNode{ TElemType data;struct BiThrNode *lchild,*rchild;/*左右孩子指針*/PointerTag LTag,RTag;/* 左右標志 */}BiThrNode,*BiThrTree;

八、實現演示

範例二叉樹：

A

B C

D E

此樹的順序結構為：ABCD##E

intmain()
{

node*p=newnode;

node*p=head;

head=p;

stringstr;

cin>>str;

creat(p,str,0)//默認根節點在str下標0的位置

return0;

}

//p為樹的根節點（已開辟動態內存）,str為二叉樹的順序存儲數組ABCD##E或其他順序存儲數組，r當前結點所在順序存儲數組位置.

intmain()

{

node*p=newnode;

node*p=head;

head=p;

stringstr;

cin>>str;

creat(p,str,0)//默認根節點在str下標0的位置

return0;

}

//p為樹的根節點（已開辟動態內存）,str為二叉樹的順序存儲數組ABCD##E或其他順序存儲數組，r當前結點所在順序存儲數組位置。

voidcreat(node*p,stringstr,intr)

{

p->data=str[r];

if(str[r*2+1]=='#'||r*2+1>str.size()-1)p->lch=NULL;

else

{

p->lch=newnode;

creat(p->lch,str,r*2+1);

}

if(str[r*2+2]=='#'||r*2+2>str.size()-1)p->rch=NULL;

else

{

p->rch=newnode;

creat(p->rch,str,r*2+2);

}

}

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

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

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

二叉樹演算法思路：

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

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

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

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

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

④ 二叉樹的順序存儲和鏈式存儲的優缺點有哪些

二叉樹的鏈式存儲是指：兩個兒子結點分別用指針指向。而存儲結構值的是：假設該結點在數組中的位置為
i
,則它的左兒子的位置為
2i
,右兒子為
2i
+
1.
(
i
從1開始)
所以你只要創建一個數組,從鏈式存儲的根節點開始,用中序遍歷遍歷樹，按中序遍歷的順序存儲在數組中。即可完成順序存儲結構的轉化。
相關的遍歷你可以查看相關資料，中序遍歷即訪問順序為左兒子-根-右兒子的順序訪問。
希望對你有所幫助。

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

二叉樹的存儲結構
二叉樹是非線性結構，即每個數據結點至多隻有一個前驅，但可以有多個後繼。它可採用順序存儲結構和鏈式存儲結構。
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;