二叉樹資料庫

㈠ 二叉樹是什麼

二叉樹 (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

㈡ 資料庫:二叉樹的前序遍歷(奇怪)

對，前序遍歷總是先訪問當前節點，然後訪問左子樹，再右子樹。如此遞歸。
所以根節點的右子樹肯定是在根節點的左子樹之後訪問的，如此類推，每個節點都是這樣。

㈢ 什麼是二叉樹，舉一個二叉樹的例子

樹是一種重要的非線性數據結構，直觀地看，它是數據元素（在樹中稱為結點）按分支關系組織起來的結構，很象自然界中的樹那樣。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構都可用樹形象表示。樹在計算機領域中也得到廣泛應用，如在編譯源程序如下時，可用樹表示源源程序如下的語法結構。又如在資料庫系統中，樹型結構也是信息的重要組織形式之一。一切具有層次關系的問題都可用樹來描述。樹結構的特點是：它的每一個結點都可以有不止一個直接後繼，除根結點外的所有結點都有且只有一個直接前趨。以下具體地給出樹的定義及樹的數據結構表示。樹是由一個或多個結點組成的有限集合，其中：⒉剩下的結點被分成n>=0個互不相交的集合T1、T2、......Tn，而且， 這些集合的每一個又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。1.樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如上圖的樹，其度為3;樹中度為零的結點稱為葉結點或終端結點。樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。2.樹的深度——組成該樹各結點的最大層次，如上圖，其深度為4；3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結點A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；4.有序樹——指樹中同層結點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。樹的表示方法有許多，常用的方法是用括弧：先將根結點放入一對圓括弧中，然後把它的子樹由左至右的順序放入括弧中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括弧括起來，同層子樹之間用逗號隔開，最後用閉括弧括起來。如上圖可寫成如下形式：二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。(1)完全二叉樹——只有最下面的兩層結點度小於2，並且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹；(2)滿二叉樹——除了葉結點外每一個結點都有左右子女且葉結點都處在最底層的二叉樹,。(1) 在二叉樹中，第i層的結點總數不超過2^(i-1)；(2) 深度為h的二叉樹最多有2h-1個結點(h>=1)，最少有h個結點；(3) 對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，(5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：若I為結點編號則 如果I<>1，則其父結點的編號為I/2；如果2*I<=N，則其左兒子（即左子樹的根結點）的編號為2*I；若2*I>N，則無左兒子；如果2*I+1<=N，則其右兒子的結點編號為2*I+1；若2*I+1>N，則無右兒子。(2)鏈表存儲方式，如：5.普通樹轉換成二叉樹：凡是兄弟就用線連起來，然後去掉父親到兒子的連線，只留下父母到其第一個子女的連線。二叉樹很象一株倒懸著的樹，從樹根到大分枝、小分枝、直到葉子把數據聯系起來，這種數據結構就叫做樹結構，簡稱樹。樹中每個分叉點稱為結點，起始結點稱為樹根，任意兩個結點間的連接關系稱為樹枝，結點下面不再有分枝稱為樹葉。結點的前趨結點稱為該結點的"雙親"，結點的後趨結點稱為該結點的"子女"或"孩子"，同一結點的"子女"之間互稱"兄弟"。二、二叉樹：二叉樹是一種十分重要的樹型結構。它的特點是，樹中的每個結點最多隻有兩棵子樹，即樹中任何結點的度數不得大於2。二叉樹的子樹有左右之分，而且，子樹的左右次序是重要的，即使在只有一棵子樹的情況下，也應分清是左子樹還是右子樹。定義：二叉樹是結點的有限集合，這個集合或是空的，或是由一個根結點和兩棵互不相交的稱之為左子樹和右子樹的二叉樹組成。對滿二叉樹，從第一層的結點(即根)開始，由下而上，由左及右，按順序結點編號，便得到滿二叉樹的一個順序表示。據此編號，完全二叉樹定義如下：一棵具有n個結點，深度為K的二叉樹，當且僅當所有結點對應於深度為K的滿二叉樹中編號由1至n的那些結點時，該二叉樹便是完全二叉樹。圖4是一棵完全二叉樹。遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。設L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為後根次序遍歷）。

㈣ 內存資料庫如何將 二叉樹直接存入

當然可以，只要你設計好終端點的結束條件，然後使用二叉樹的那些個什麼遍歷演算法就了存入，取出就是存入的逆操作。

㈤ 資料庫結構的遍厲二叉樹的問題!!高手進!

後序中A在最後，A為根；看中序知BDCE在左，FHG在右。
第一層
A
在看後序B在最後，中序中B在最前，知CDE都在B的右支上。..........
第二層
B
F
第三層
*
C
*
G
第四層*
*
D
E
*
*
H
*
*代表空
好了，連起來吧

㈥ 資料庫中二叉樹索引對字元怎麼寫

首先mysql不是二叉樹索引，而是B+樹索引，這種作為索引的好處是可以對有序的記錄作logN級的查找，不過對於沒有大小之分的數據來說，還是建立哈希索引更好，因為哈希索引的時間復雜度基本是log1的

㈦ 二叉樹的學習，對於資料庫方向的學生有什麼意義

如果不是涉及情況到比較底層的資料庫編程，大多數沒有太大的意義

㈧ 《C語言》有叫「二叉樹/數」的東西嗎 它到底是什麼

上面都講了，二叉樹是一種資料庫結構。
在壓縮文件的時候用到二叉樹，那裡稱哈夫曼樹。
一般數組是像一條線一樣，竄在一起，一個數的後面只有一個數。
二叉一個數後面有兩個數，大概就是這樣解釋。