二叉樹是如何存儲的

A. 二叉樹怎麼操作

1.構造二叉樹給定一棵二叉樹，要對它進行操作必須先把它存儲到計算機中，二叉樹的存儲可以採用順序存儲結構，也可以採用鏈式存儲結構，鏈式存儲結構有二叉鏈表和三叉鏈表等。在這里主要討論二叉鏈表存儲結構。

（1）以先序遞歸遍歷思想建立二叉樹。

①建立二叉樹的根結點；②先序建立二叉樹的左子樹；③先序建立二叉樹的右子樹。

（2）構造二叉樹的操作演算法。

輸入一個二叉樹的先序序列，構造這棵二叉樹。為了保證唯一地構造出所希望的二叉樹，在鍵入這棵樹的先序序列時，需要在所有空二叉樹的位置上填補一個特殊的字元，比如#。在演算法中，需要對每個輸入的字元進行判斷，如果對應的字元是#，則在相應的位置上構造一棵空二叉樹；否則，創建一個新結點。整個演算法結構以先序遍歷遞歸演算法為基礎，二叉樹中結點之間的指針連接是通過指針參數在遞歸調用返回時完成的。

B. 二叉樹是什麼

二叉樹 (binary tree) 是另一種樹型結構，它的特點是每個結點至多隻有二棵子 樹 (即二叉樹中不存在度大於 2的結點 )，並且，二叉樹的子樹有左右之分，其次序不能任意顛倒 . 二叉樹是一種數據結構 :

Binary_tree=(D,R)

其中： D是具有相同特性的數據元素的集合 ;若 D等於空 ,則 R等於空稱為空的二叉樹 ;若 D等於空則 R是 D上某個二元關系 H的集合，即 R={H}，且
(1) D 中存在唯一的稱為根的元素 r，它的關系 H下無前驅 ;
(2) 若 D-{r}不等於空，則 D-{r}={Dl,Dr}，且 Dl交 Dr等於空 ;
(3) 若 Dl不等於空 ,則在 Dl中存在唯一的元素 xl,〈 r,xl〉屬於 H，且存在 Dl上的關系 Hl屬於 H； 若 Dr不等於空 ,則在 Dr中存在唯一的元素 xr,〈 r,xr〉 >屬於 H, 且存 Dr上的關 系 Hr屬於 H； H={r,xl,＜ r,xr＞ ,Hl, Hr};
(4) (Dl, Hl) 是一棵合本定義的二叉樹，稱為根 r的左子樹 ,(Dr,Hr)是一棵符合定義的二叉樹，稱為根的右子樹。

其中，圖 6.2 是各種形態的二叉樹 .

(1) 為空二叉樹 (2)只有一個根結點的二叉樹 (3)右子樹為空的二叉樹 (4)左子樹為空的二叉樹 (5)完全二叉樹

二叉樹的基本操作：

(1)INITIATE(BT ） 初始化操作。置 BT為空樹。

(2)ROOT(BT)\ROOT(x) 求根函數。求二叉樹 BT的根結點或求結點 x所在二叉樹的根結點。
若 BT是空樹或 x不在任何二叉樹上，則函數值為 「空 」。

(3)PARENT(BT,x) 求雙親函數。求二叉樹 BT中結點 x的雙親結點。若結點 x是二叉樹 BT 的根結點
或二叉樹 BT中無 x結點，則函數值為 「空 」。

(4)LCHILD(BT,x) 和 RCHILD(BT,x) 求孩子結點函數。分別求二叉樹 BT中結點 x的左孩 子和右孩子結點。
若結點 x為葉子結點或不在二叉樹 BT中，則函數值為 「空 」。

(5)LSIBLING(BT,x) 和 RSIBING(BT,x) 求兄弟函數。分別求二叉樹 BT中結點 x的左兄弟和右兄弟結點。
若結點 x是根結點或不在 BT中或是其雙親的左 /右子樹根 ,則函樹值 為 「空 」。

(6)CRT_BT(x,LBT,RBT) 建樹操作。生成一棵以結點 x為根，二叉樹 LBT和 RBT分別為左， 右子樹的二叉樹。

(7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子樹操作。將以結點 x為根且右子樹為空的二叉樹
分別置為二叉樹 BT中結點 y的左子樹和右子樹。若結點 y有左子樹 /右子樹，則插入後是結點 x的右子樹。

(8)DEL_LCHILD(BT,x) 和 DEL-RCHILD(BT,x) 刪除子樹操作。分別刪除二叉樹 BT中以結點 x為根的左子樹或右子樹。
若 x無左子樹或右子樹，則空操作。

(9)TRAVERSE(BT) 遍歷操作。按某個次序依此訪問二叉樹中各個結點，並使每個結點只被訪問一次。

(10)CLEAR(BT) 清除結構操作。將二叉樹 BT置為空樹。

5.2.2 二叉樹的存儲結構

一 、順序存儲結構
連續的存儲單元存儲二叉樹的數據元素。例如圖 6.4(b)的完全二叉樹 , 可以向量 (一維數組 ) bt(1:6)作它的存儲結構，將二叉樹中編號為 i的結點的數據元素存放在分量 bt[i]中 ,如圖 6.6(a) 所示。但這種順序存儲結構僅適合於完全二叉樹 ,而一般二叉樹也按這種形式來存儲 ,這將造成存 貯浪費。如和圖 6.4(c)的二叉樹相應的存儲結構圖 6.6(b)所示，圖中以 「0」表示不存在此結點 .

二、 鏈式存儲結構
由二叉樹的定義得知二叉樹的結點由一個數據元素和分別指向左右子樹的兩個分支構成 ,則表 示二叉樹的鏈表中的結點至少包含三個域 :數據域和左右指針域 ,如圖 (b)所示。有時 ,為了便於找 到結點的雙親 ,則還可在結點結構中增加一個指向其雙親受的指針域，如圖 6.7(c)所示。

5.3 遍歷二叉樹

遍歷二叉樹 (traversing binary tree)的問題， 即如何按某條搜索路徑巡訪樹中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。 其中常見的有三種情況：分別稱之為先 (根 )序遍歷，中 (根 )序遍歷和後 (根 )序遍歷。

5.3.1 前序遍歷

前序遍歷運算：即先訪問根結點，再前序遍歷左子樹，最後再前序遍歷右子樹。前序遍歷運算訪問二叉樹各結點是以根、左、右的順序進行訪問的。例如：

按前序遍歷此二叉樹的結果為： Hello!How are you?

proc preorder(bt:bitreprtr)
if (bt>null)[
print(bt^);
preorder(bt^.lchild);
preorder(bt^.rchild);]
end;

5.3.2 中序遍歷

中序遍歷運算：即先中前序遍歷左子樹，然後再訪問根結點，最後再中序遍歷右子樹。中序遍歷運算訪問二叉樹各結點是以左、根、右的順序進行訪問的。例如：

按中序遍歷此二叉樹的結果為： a*b-c

proc inorder(bt:bitreprtr)
if (bt>null)[
inorder(bt^.lchild);
print(bt^);
niorder(bt^.rchild);]
end;

5.3.3 後序遍歷

後序遍歷運算：即先後序遍歷左子樹，然後再後序遍歷右子樹，最後訪問根結點。後序遍歷運算訪問二叉樹各結點是以左、右、根的順序進行訪問的。例如：

按後序遍歷此二叉樹的結果為： Welecome to use it!

proc postorder(bt:bitreprtr)
if (bt>null)[
postorder(bt^.lchild);
postorder(bt^.rchild);]
print(bt^);
end;

五、例：
1.用順序存儲方式建立一棵有31個結點的滿二叉樹，並對其進行先序遍歷。
2.用鏈表存儲方式建立一棵如圖三、4所示的二叉樹，並對其進行先序遍歷。
3.給出一組數據：R={10.18,3,8,12,2,7,3}，試編程序，先構造一棵二叉樹，然後以中序遍歷訪問所得到的二叉樹，並輸出遍歷結果。
4.給出八枚金幣a,b,c,d,e,f,g,h，編程以稱最少的次數，判定它們蹭是否有假幣，如果有，請找出這枚假幣，並判定這枚假幣是重了還是輕了。

中山紀念中學三鑫雙語學校信息學競賽組編寫 2004.7.15

C. 試分析二叉樹的存儲時如何實現的,分別介紹二叉樹的順序存儲和鏈式存儲 .

4.二叉樹的存儲結構
(1）順序存儲方式

type node=record
data:datatype
l,r:integer;
end;
var tr:array[1..n] of node;

(2)鏈表存儲方式，如：
type btree=^node；
node=record
data:datatye;
lchild,rchild:btree;
end;

D. 二叉樹的存儲結構是怎樣的有哪些類型的存儲結構對應的c語言描述是

線性表的鏈式存儲結構：
typedef
int
elemtype;
typedef
struct
lnode
{
elemtype
data;
struct
lnode
*next;
}lnode,*linklist;
(被封裝好的每個節點，都有一個數據域data和一個指針域*next用於指向下一個節點)
二叉樹的二叉鏈表：
typedef
int
telemtype;
typedef
struct
bitnode
{
telemtype
data;
struct
bitnode
*lchild,*rchild;
}bitnode,*bitree;
(被封裝好的每個節點，都有一個數據域data和兩個指針域
*lchild,*rchild分別指向左右子樹)
需要什麼類型的數據作為數據域可更改，或者typedef
int
elemtype;和typedef
int
telemtype;中的int，比如改為char、float等或者自定義數據類型。

E. 如何進行二叉樹的存儲

用二叉鏈表進行存儲，採用先序遍歷的思想來創建二叉樹就行了

F. 數據結構 二叉樹的順序存儲結構

此結構是將二叉樹的所有結點，
按照一定的次序，存儲到一片連續的存儲單元中。
因此，必須將結點排成一個適當的線性序列，
使得結點在這個序列中的相應位置能反映出結點之間的邏輯關系。
這種結構特別適用於近似滿二叉樹。
在一棵具有n個結點的近似滿二叉樹中，
我們從樹根起，自上層到下層，逐層從左到右給所有結點編號，就能得到一個足以反映整個二叉樹結構的線性序列

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

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

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

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

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

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

(7)二叉樹是如何存儲的擴展閱讀：

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

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

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

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

H. 什麼是二叉樹的順序存儲

二叉樹的順序存儲是將二叉樹的所有結點，按照一定的次序，存儲到一片連續的存儲單元中

二叉樹的順序存儲必須將結點排成一個適當的線性序列，使得結點在這個序列中的相應位置能反映出結點之間的邏輯關系。這種結構特別適用於近似滿二叉樹。

在一棵具有n個結點的近似滿二叉樹中，當從樹根起，自上層到下層，逐層從左到右給所有結點編號時，就能得到一個足以反映整個二叉樹結構的線性序列。其中每個結點的編號就作為結點。

(8)二叉樹是如何存儲的擴展閱讀：

二叉樹的性質：

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。

參考資料來源：網路-二叉樹

I. 如何存儲一顆二叉樹

1、順序存儲結構，用一組地址連續的存儲單元由上而下由左至右的存儲完全二叉樹的節點元素，其他二叉樹則與完全二叉樹上的結點進行對照，存儲在一維數組的相應分量中
2、鏈式存儲結構，如二叉鏈表，三叉鏈表
3、線索二叉樹

J. 二叉樹順序存儲

順序存儲的話，就是存儲在數組中，數組的下標就是二叉樹的結點位置（層次結構），比如結點A，在數組中就是位置0，B就是1，C就是2....，以此類推，所以第i個結點的在數組中的位置就是i（i從0開始），i的兩個孩子結點在數組中的位置是2i+1和2i+2