㈠ 二叉樹是什麼
二叉樹 (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語言描述是
線性表的鏈式存儲結構：
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等或者自定義數據類型。
㈢ 一個二叉樹按順序方式存儲在一個一維數組中，如圖：
二叉樹按照層序遍歷，依次編號，按照編號的順序，存儲在連續存儲單元的方式就是二叉樹的順序存儲。
㈣ 二叉樹的兩種物理結構是什麼
答：二叉樹就物理結構來分可以分成：順序存儲結構和鏈式存儲結構。
（1）順序存儲結構：
順序存儲結構，顧名思義就是二叉樹的數據元素存放在一組連續的存儲單元中。其主要有一下幾個特點：
①邏輯上相鄰的兩個元素在物理位置上也是相鄰的；
②操作刪除和插入的時候，需要整體移動元素；
③需要預先分配空間，不能動態增長；
（2）鏈式存儲結構：
鏈式存儲結構中二叉樹的每個結點至少包含三個域：數據域、左指針域和右指針域。其二叉樹是通過指針實現，鏈式存儲結構有以下幾個特點：
①邏輯上相鄰的兩個元素在物理位置上不一定是相鄰的；
②操作刪除和插入的時候，不需要整體移動元素；只需要修改相應的指針即可；
③不需要預先分配空間；
④存儲指針本身會消耗一定的存儲的空間；
㈤ 二叉樹_鏈式存儲
二叉鏈：數據域（data）、左子結點域（lchild）、右子節點域（rchild）
定義：
求指定節點的左子節點地址：
求指定節點的右子節點地址：
二叉樹的遍歷：
定義： 按照某種順序訪問二叉樹中的每個結點，使每個結點被訪問一次且僅被訪問一次；
用途： 它是樹結構插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎和核心；
遍歷規則：
1、先序遍歷(DLR)： 頭 -> 左 -> 右
2、中序遍歷(LDR)： 左 -> 頭 -> 右
3、後序遍歷(LRD)： 左 -> 右 -> 頭
先中後都是對於根結點而言。
二叉樹遍歷的遞歸實現：
訪問方法：
先序遍歷：
中序遍歷：
後序遍歷：
插一嘴：遞歸實現的思路清晰，易於理解，但是執行效率很低。非遞歸實現效率高些。
二叉樹遍歷的非遞歸實現：
先序遍歷：
中序遍歷：
後序遍歷：好難-.-||略
利用「擴展先序遍歷序列」 創建二叉樹二叉鏈表：
1、若輸入的字元是 '#'，則建立空樹；
2、否則建立根結點，接著遞歸建立左子樹，然後遞歸建立右子樹。