索引存儲二叉樹

❶ oracle的B樹索引到底是不是基於二叉樹

B-Tree索引是最常見的索引結構，默認創建的索引就是B-Tree索引。
一、B樹索引的結構
B-樹索引是基於二叉樹結構的。B-樹索引結構有3個基本組成部分：根節點、分支節點和葉子節點。其中根節點位於索引結構的最頂端，而葉子節點位於索引結構的最底端，中間為分子節點。
葉子節點（Leaf node）：包含條目直接指向表裡的數據行。
分支節點（Branch node）：包含的條目指向索引里其他的分支節點或者是葉子節點。
根節點（Branch node）：一個B樹索引只有一個根節點，它實際就是位於樹的最頂端的分支節點。
可以用下圖一來描述B樹索引的結構。其中，B表示分支節點，而L表示葉子節點。
clip_image001
1.1關於分支節點塊（包括根節點塊）
1、 其所包含的索引條目都是按照順序排列的（預設是升序排列，也可以在創建索引時指定為降序排列）。
2、 每個索引條目（也可以叫做每條記錄）都具有兩個欄位。第一個欄位表示當前該分支節點塊下面所鏈接的索引塊中所包含的最小鍵值；第二個欄位為四個位元組，表示所鏈接的索引塊的地址，該地址指向下面一個索引塊。
3、 在一個分支節點塊中所能容納的記錄行數由數據塊大小以及索引鍵值的長度決定。比如從上圖一可以看到，對於根節點塊來說，包含三條記錄，分別為（0 B1）、（500 B2）、（1000 B3），它們指向三個分支節點塊。其中的0、500和1000分別表示這三個分支節點塊所鏈接的鍵值的最小值。而B1、B2和B3則表示所指向的三個分支節點塊的地址。
1.2關於葉子節點
1、 B樹索引的所有葉子塊一定位於同一層上，這是由B樹的數據結構定義的。Oracle 設計的B樹索引結構保證了B 樹索引從根到葉子都有相等的分支節點，保證了B樹索引的平衡，這樣就不會因為基表的數據插入後刪除操作造成B樹索引變得不平衡，從而影響索引的性能。因此，從根塊到達任何一個葉子塊的遍歷代價都是相同的； 索引高度是指從根塊到達葉子塊時所遍歷的數據塊的個數，通常，大多數的B樹索引的高度都是2到3，也就意味著，即使表中有上百萬條記錄，從索引中定位一個鍵字只需要2或3次I/O,索引越高，性能越差；
2、 葉子節點所包含的索引條目與分支節點一樣，都是按照順序排列的（預設是升序排列，也可以在創建索引時指定為降序排列）
3、 每個索引條目（也可以 叫做每條記錄）也具有兩個欄位。第一個欄位表示索引的鍵值，對於單列索引來說是一個值；而對於多列索引來說則是多個值組合在一起的。第二個欄位表示鍵值所對應的記錄行的ROWID，該ROWID是記錄行在表裡的物理地址。ROWID 是唯一的Oracle 指針，指向該行的物理位置，使用ROWID 是Oracle 資料庫中訪問行最快的方法。參照Oracle中的rowid
4、 葉子節點其實是一個雙向鏈表，每個葉子節點包含一個指向下一個和上一個葉子點的指針，這樣在一定范圍內便利索引以搜索需要的記錄。
clip_image002
clip_image004
二、B樹索引的訪問
當oracle進程需要訪問數據文件里的數據塊時，oracle會有兩種類型的I/O操作方式：
1） 隨機訪問，每次讀取一個數據塊（通過等待事件「db file sequential read」體現出來）。
2） 順序訪問，每次讀取多個數據塊（通過等待事件「db file scattered read」體現出來）。
第一種方式則是訪問索引里的數據塊，而第二種方式的I/O操作屬於全表掃描。這里順帶有一個問題，為何隨機訪問會對應到db file sequential read等待事件，而順序訪問則會對應到db file scattered read等待事件呢？這似乎反過來了，隨機訪問才應該是分散（scattered）的，而順序訪問才應該是順序（sequential）的。其實，等待事件主要根據實際獲取物理I/O塊的方式來命名的，而不是根據其在I/O子系統的邏輯方式來命名的。下面對於如何獲取索引數據塊的方式中會對此進行說明。
事實上在B樹索引雖然為一個樹狀的立體結構，但其對應到數據文件里的排列當然還是一個平面的形式，也就是像下面這樣。
/根/分支/分支/葉子/…/葉子/分支/葉子/葉子/…/葉子/分支/葉子/葉子/…/葉子/分支/.....
因此，當oracle需要訪問某個索引塊的時候，勢必會在這個結構上跳躍的移動。
當oracle需要獲得一個索引塊時，首先從根節點開始，根據所要查找的鍵值，從而知道其所在的下一層的分支節點，然後訪問下一層的分支節點，再次同樣根據鍵值訪問再下一層的分支節點，如此這般，最終訪問到最底層的葉子節點。可以看出，其獲得物理I/O塊時，是一個接著一個，按照順序，串列進行的。在獲得最終物理塊的過程中，我們不能同時讀取多個塊，因為我們在沒有獲得當前塊的時候是不知道接下來應該訪問哪個塊的。因此，在索引上訪問數據塊時，會對應到 db file sequential read等待事件，其根源在於我們是按照順序從一個索引塊跳到另一個索引塊，從而找到最終的索引塊的。
那麼對於全表掃描來說，則不存在訪問下一個塊之前需要先訪問上一個塊的情況。全表掃描時，oracle知道要訪問所有的數據塊，因此唯一的問題就是盡可能高效的訪問這些數據塊。因此，這時oracle可以採用同步的方式，分幾批，同時獲取多個數據塊。這幾批的數據塊在物理上可能是分散在表裡的，因此其對應到db file scattered read等待事件。
三、DML對B樹索引的影響
3.1 INSERT
在每個INSERT操作過程中，關鍵字必須被插入在正確葉節點的位置。如果葉節點已滿，不能容納更多的關鍵字，就必須將葉節點拆分。拆分的方法有兩種：
1)如果新關鍵字值在所有舊葉節點塊的所有關鍵字中是最大的，那麼所有的關鍵字將按照99:1的比例進行拆分，使得在新的葉節點塊中只存放有新關鍵字，而其他的所有關鍵字（包括所有刪除的關鍵字）仍然保存在舊葉節點塊中。
2)如果新關鍵字值不是最大的，那麼所有的關鍵字將按照50:50的比例進行拆分，這時每個葉節點塊（舊與新）中將各包含原始葉節點中的一半關鍵字。
這個拆分必須通過一個指向新葉節點的新入口向上傳送到父節點。如果父節點已滿，那麼這個父節點也必須進行拆分，並且需要將這種拆分向上傳送到父節點的父節點。這時，如果這個父節點也已滿，將繼續進行這個過程。這樣，某個拆分可能最終被一直傳送到根節點。如果根節點滿了，根結點也將進行分裂。根結點在進行分裂的時候，就是樹的高度增加的時候。根節點進行分裂的方式跟其他的的節點分裂的方式相比較，在物理位置上的處理也是不同的。根節點分裂時，將原來的根結點分裂為分支節點或葉節點，保存到新的塊中，而將新的根節點信息保存到原來的根結點塊中，這樣做的是為因為避免修改數據字典所帶來的相對較大的開銷。
注意：現在Oracle都是採用了平衡演算法，正常情況下即使索引關鍵字不斷增大，也不會產生不平衡樹。當索引關鍵字不斷增大，導致樹級別單方向增長時，Oracle會自動進行索引翻轉以維持索引的平衡，當然這種操作非常消耗資源
在索引的每一個層次之間，每一個層最左邊的節點的block頭部都有一個指向下層最左邊的塊的指針，這樣有利於fast full scan 的快速定位最左邊的葉子節點。
每個拆分過程都是要花費一定的開銷的，特別是要進行物理硬碟I/O動作。此外，在進行拆分之前，Oracle必須查找到一個空塊，用來保存這個拆分。可以用以下步驟來進行查找空塊的動作：
1) 在索引的自由列表(free-list, 又稱為空閑列表) 中查到一個空閑塊，可以通過CREATE/ALTER INDEX命令為一個索引定義多個空閑列表。索引空閑列表並不能幫助Oracle查找一個可用來存放將要被插入的新關鍵字的塊。這是因為關鍵字值不能隨機地存放在索引中可用的第一個「空閑」葉節點塊中，這個值必須經過適當的排序之後，放置在某個特定的葉節點塊中。只有在塊拆分過程中才需要使用索引的空閑列表，每個空閑列表都包含有一個關於「空」塊的鏈接列表。當為某個索引定義了多個空閑列表時，首先將從分配給進程的空間列表中掃描一個空閑塊。如果沒有找到所需要的空閑塊，將從主空閑列表中進行掃描空閑塊的動作。
2) 如果沒有找到任何空閑塊，Oracle將試圖分配另一個擴展段。如果在表空間中沒有更多的自由空間，Oracle將產生錯誤ORA-01654。
3) 如果通過上述步驟，找到了所需的空閑塊，那麼這個索引的高水位標(HWM)將加大。
4) 所找到的空閑塊將用來執行拆分動作。
在創建B*樹索引時，一個需要注意的問題就是要避免在運行時進行拆分，或者，要在索引創建過程中進行拆分（「預拆分」），從而使得在進行拆分時能夠快速命中，以便避免運行時插入動作。當然，這些拆分也不僅僅局限於插入動作，在進行更新的過程中也有可能會發生拆分動作。
3.2 UPDATE
索引更新完全不同於表更新，在表更新中，數據是在數據塊內部改變的（假設數據塊中有足夠的空間來允許進行這種改變）；但在索引更新中，如果有關鍵字發生改變，那麼它在樹中的位置也需要發生改變。請記住，一個關鍵字在B*樹中有且只有一個位置。因此，當某個關鍵字發生改變時，關鍵字的舊表項必須被刪除，並且需要在一個新的葉節點上創建一個新的關鍵字。舊的表項有可能永遠不會被重新使用，這是因為只有在非常特殊的情況下， Oracle才會重用關鍵字表項槽，例如，新插入的關鍵字正好是被刪除的那個關鍵字（包括數據類型、長度等等）。（這里重用的是塊，但完全插入相同的值的時候，也不一定插入在原來的被刪除的位置，只是插入在原來的塊中，可能是該塊中的一個新位置。也正因為如此，在索引塊中保存的的記錄可能並不是根據關鍵字順序排列的，隨著update等的操作，會發生變化。）那麼，這種情況發生的可能性有多大呢？許多應用程序使用一個數列來產生NUMBER關鍵字（特別是主關鍵字）。除非它們使用了RECYCLE選項，否則這個數列將不會兩次產生完全相同的數。這樣，索引中被刪除的空間一直沒有被使用。這就是在大規模刪除與更新過程中，表大小不斷減小或至少保持不變但索引不斷加大的原因。
3.3 DELETE
當刪除表裡的一條記錄時，其對應於索引里的索引條目並不會被物理的刪除，只是做了一個刪除標記。當一個新的索引條目進入一個索引葉子節點的時候，oracle會檢查該葉子節點里是否存在被標記為刪除的索引條目，如果存在，則會將所有具有刪除標記的索引條目從該葉子節點里物理的刪除。
當一個新的索引條目進入索引時，oracle會將當前所有被清空的葉子節點（該葉子節點中所有的索引條目都被設置為刪除標記）收回，從而再次成為可用索引塊。
盡管被刪除的索引條目所佔用的空間大部分情況下都能夠被重用，但仍然存在一些情況可能導致索引空間被浪費，並造成索引數據塊很多但是索引條目很少的後果，這時該索引可以認為出現碎片。而導致索引出現碎片的情況主要包括：
1、不合理的、較高的PCTFREE。很明顯，這將導致索引塊的可用空間減少。
2、索引鍵值持續增加（比如採用sequence生成序列號的鍵值），同時對索引鍵值按照順序連續刪除，這時可能導致索引碎片的發生。因為前面我們知道，某個索引塊中刪除了部分的索引條目，只有當有鍵值進入該索引塊時才能將空間收回。而持續增加的索引鍵值永遠只會向插入排在前面的索引塊中，因此這種索引里的空間幾乎不能收回，而只有其所含的索引條目全部刪除時，該索引塊才能被重新利用。
3、經常被刪除或更新的鍵值，以後幾乎不再會被插入時，這種情況與上面的情況類似。
四、總結
通過上面對B樹的分析，可以得出以下的應用准則：
1、避免對那些可能會產生很高的更新動作的列進行索引。
2、避免對那些經常會被刪除的表中的多個列進行索引。若有可能，只對那些在這樣的表上會進行刪除的主關鍵字與/或列進行索引。如果對多個列進行索引是不可避免的，那麼就應該考慮根據這些列對表進行劃分，然後在每個這樣的劃分上執行TRUNCATE動作（而不是DELETE動作）。TRUNCATE在與 DROP STORAGE短語一同使用時，通過重新設置高水位標來模擬刪除表與索引以及重新創建表與索引的過程。
3、避免為那些唯一度不高的列創建B*樹索引。這樣的低選擇性將會導致樹節點塊的稠密性，從而導致由於索引「平鋪( flat)」而出現的大規模索引掃描。唯一性的程度越高，性能就越好，因為這樣能夠減少范圍掃描，甚至可能用唯一掃描來取代范圍掃描。
4）空值不存儲在單列索引中。對於復合索引的方式，只有當某個列不空時，才需要進行值的存儲。在為DML語句創建IS NULL或IS NOT NULL短語時，應該切記這個問題。
5）IS NULL不會導致索引掃描，而一個沒有帶任何限制的IS NOT NULL則可能會導致完全索引掃描。

❷ 關於數據結構的問題

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

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

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

❸ 索引的種類

二、索引類型
Mysql目前主要有以下幾種索引類型：FULLTEXT，HASH，BTREE，RTREE。

1. FULLTEXT
即為全文索引，目前只有MyISAM引擎支持。其可以在CREATE TABLE ，ALTER TABLE ，CREATE INDEX 使用，不過目前只有 CHAR、VARCHAR ，TEXT 列上可以創建全文索引。

全文索引並不是和MyISAM一起誕生的，它的出現是為了解決WHERE name LIKE 「%word%"這類針對文本的模糊查詢效率較低的問題。

2. HASH
由於HASH的唯一（幾乎100%的唯一）及類似鍵值對的形式，很適合作為索引。

HASH索引可以一次定位，不需要像樹形索引那樣逐層查找,因此具有極高的效率。但是，這種高效是有條件的，即只在「=」和「in」條件下高效，對於范圍查詢、排序及組合索引仍然效率不高。

3. BTREE
BTREE索引就是一種將索引值按一定的演算法，存入一個樹形的數據結構中（二叉樹），每次查詢都是從樹的入口root開始，依次遍歷node，獲取leaf。這是MySQL里默認和最常用的索引類型。

4. RTREE
RTREE在MySQL很少使用，僅支持geometry數據類型，支持該類型的存儲引擎只有MyISAM、BDb、InnoDb、NDb、Archive幾種。

相對於BTREE，RTREE的優勢在於范圍查找。

ps. 此段詳細內容見此片博文：Mysql幾種索引類型的區別及適用情況

三、索引種類
普通索引：僅加速查詢

唯一索引：加速查詢 + 列值唯一（可以有null）

主鍵索引：加速查詢 + 列值唯一（不可以有null）+ 表中只有一個

組合索引：多列值組成一個索引，專門用於組合搜索，其效率大於索引合並

全文索引：對文本的內容進行分詞，進行搜索

ps.

索引合並，使用多個單列索引組合搜索
覆蓋索引，select的數據列只用從索引中就能夠取得，不必讀取數據行，換句話說查詢列要被所建的索引覆蓋

❹ 用數組存儲完全二叉樹時,結點的索引(數組下標)與其父子結點索引的關系.

如果從下標從1開始存儲，則編號為i的結點的主要關系為：
雙親：下取整 （i/2）
左孩子：2i
右孩子：2i+1

如果從下標從0開始存儲，則編號為i的結點的主要關系為：
雙親：下取整 （(i-1)/2）
左孩子：2i+1
右孩子：2i+2

❺ 二叉樹索引原理是什麼

索引是為檢索而存在的。如一些書籍的末尾就專門附有索引，指明了某個關鍵字在正文中的出現的頁碼位置，方便我們查找，但大多數的書籍只有目錄，目錄不是索引，只是書中內容的排序，並不提供真正的檢索功能。可見建立索引要單獨佔用空間；索引也並不是必須要建立的，它們只是為更好、更快的檢索和定位關鍵字而存在。
再進一步說，我們要在圖書館中查閱圖書，該怎麼辦呢？圖書館的前台有很多叫做索引卡片櫃的小櫃子，裡面分了若乾的類別供我們檢索圖書，比如你可以用書名的筆畫順序或者拼音順序作為查找的依據，你還可以從作者名的筆畫順序或拼音順序去查詢想要的圖書，反正有許多檢索方式，但有一點很明白，書庫中的書並沒有按照這些卡片櫃中的順序排列——雖然理論上可以這樣做，事實上，所有圖書的脊背上都人工的粘貼了一個特定的編號①，它們是以這個順序在排列。索引卡片中並沒有指明這本書擺放在書庫中的第幾個書架的第幾本，僅僅指明了這個特定的編號。管理員則根據這一編號將請求的圖書返回到讀者手中。這是很形象的例子，以下的講解將會反復用到它。

❻ 為什麼常見索引採用b+樹的數據結構而不是平衡二叉樹

當記錄較多時，採用平衡二叉樹就會出現深度較高的情況，這樣檢索起來O（lgN）的效率較低，而B+樹則是多路平衡樹，每個節點可以存儲多個數據，通過定位以後，如果在葉節點之前沒找到，在相應的葉子節點中通過二叉查找，效率較高。

❼ 二叉樹類及其實現

二叉樹結點類

1 using System;
2 public class Node
3 {
4 //成員變數
5 private object _data; //數據
6 private Node _left; //左孩子
7 private Node _right; //右孩子
8 public object Data
9 {
10 get { return _data; }
11 }
12 public Node Left //左孩子
13 {
14 get { return _left; }
15 set { _left = value; }
16 }
17 public Node Right //右孩子
18 {
19 get { return _right; }
20 set { _right = value; }
21 }
22 //構造方法
23 public Node(object data)
24 {
25 _data = data;
26 }
27 public override string ToString()
28 {
29 return _data.ToString();
30 }
31 }
32

Node類專門用於表示二叉樹中的一個結點，它很簡單，只有三個屬性：Data表示結點中的數據；Left表示這個結點的左孩子，它是Node類型；Right表示這個結點的右孩子，它也是Node類型。

【例6-1 BinaryTree.cs】二叉樹集合類

1 using System;
2 public class BinaryTree
3 { //成員變數
4 private Node _head; //頭指針
5 private string cStr; //用於構造二叉樹的字元串
6 public Node Head //頭指針
7 {
8 get { return _head; }
9 }
10 //構造方法
11 public BinaryTree(string constructStr)
12 {
13 cStr = constructStr;
14 _head = new Node(cStr[0]); //添加頭結點
15 Add(_head, 0); //給頭結點添加孩子結點
16 }
17 private void Add(Node parent, int index)
18 {
19 int leftIndex = 2 * index + 1; //計算左孩子索引
20 if (leftIndex < cStr.Length) //如果索引沒超過字元串長度
21 {
22 if (cStr[leftIndex] != '#') //'#'表示空結點
23 { //添加左孩子
24 parent.Left = new Node(cStr[leftIndex]);
25 //遞歸調用Add方法給左孩子添加孩子節點
26 Add(parent.Left, leftIndex);
27 }
28 }
29 int rightIndex = 2 * index + 2;
30 if (rightIndex < cStr.Length)
31 {
32 if (cStr[rightIndex] != '#')
33 { //添加右孩子
34 parent.Right = new Node(cStr[rightIndex]);
35 //遞歸調用Add方法給右孩子添加孩子節點
36 Add(parent.Right, rightIndex);
37 }
38 }
39 }
40 public void PreOrder(Node node) //先序遍歷
41 {
42 if (node != null)
43 {
44 Console.Write(node.ToString()); //列印字元
45 PreOrder(node.Left); //遞歸
46 PreOrder(node.Right); //遞歸
47 }
48 }
49 public void MidOrder(Node node) //中序遍歷
50 {
51 if (node != null)
52 {
53 MidOrder(node.Left); //遞歸
54 Console.Write(node.ToString()); //列印字元
55 MidOrder(node.Right); //遞歸
56 }
57 }
58 public void AfterOrder(Node node) //後繼遍歷
59 {
60 if (node != null)
61 {
62 AfterOrder(node.Left); //遞歸
63 AfterOrder(node.Right); //遞歸
64 Console.Write(node.ToString()); //列印字元
65 }
66 }
67 }
68

BinaryTree是一個二叉樹的集合類，它屬於二叉鏈表，實際存儲的信息只有一個頭結點指針（Head），由於是鏈式存儲結構，可以由Head指針出發遍歷整個二叉樹。為了便於測試及添加結點，假設BinaryTree類中存放的數據是字元類型，第5行聲明了一個字元串類型成員cStr，它用於存放結點中所有的字元。字元串由滿二叉樹的方式進行構造，空結點用『#』號表示（參考本章「二叉樹存儲結構」這一小節中的「順序存儲結構」）。圖6.13所示的二叉樹可表示為：「ABCDE#F」。

11～16行的構造方法傳入一個構造字元串，並在Add()方法中根據這個字元串來構造二叉樹中相應的結點。需要注意，這個構造方法只用於測試。

17～39行的Add()方法用於添加結點，它的第一個參數parent表示需要添加孩子結點的雙親結點，第二個參數index表示這個雙親結點的編號（編號表示使用順序存儲結構時它在數組中的索引，請參考本章「二叉樹存儲結構」這一小節中的「順序存儲結構」）。添加孩子結點的方法是先計算孩子結點的編號，然後通過這個編號在cStr中取出相應的字元，並構造新的孩子結點用於存放這個字元，接下來遞歸調用Add()方法給孩子結點添加它們的孩子結點。注意，這個方法只用於測試。

40～48行代碼的PreOrder()方法用於先序遍歷，它的代碼跟之前所講解的先序遍歷過程完全一樣。

49～57行代碼的MidOrder()方法用於中序遍歷。

58～66行代碼的AfterOrder()方法用於後序遍歷。

以上三個方法都使用了遞歸來完成遍歷，這符合二叉樹的定義。

【例6-1 Demo6-1.cs】二叉樹深度優先遍歷測試

1 using System;
2 class Demo6_1
3 {
4 static void Main(string[] args)
5 { //使用字元串構造二叉樹
6 BinaryTree bTree = new BinaryTree("ABCDE#F");
7 bTree.PreOrder(bTree.Head); //先序遍
8 Console.WriteLine();
9 bTree.MidOrder(bTree.Head); //中序遍
10 Console.WriteLine();
11 bTree.AfterOrder(bTree.Head); //後序遍
12 Console.WriteLine();
13 }
14 }
15

運行結果：

ABDECF

DBEACF

DEBFCA

6.3.2 二叉樹的寬度優先遍歷

之前所講述的二叉樹的深度優先遍歷的搜索路徑是首先搜索一個結點的所有子孫結點，再搜索這個結點的兄弟結點。是否可以先搜索所有兄弟和堂兄弟結點再搜索子孫結點呢？

由於二叉樹結點分屬不同的層次，因此可以從上到下、從左到右依次按層訪問每個結點。它的訪問順序正好和之前所述二叉樹順序存儲結構中的結點在數組中的存放順序相吻合。如圖6.13中的二叉樹使用寬度優先遍歷訪問的順序為：ABCDEF。

這個搜索過程不再需要使用遞歸，但需要藉助隊列來完成。

（1） 將根結點壓入隊列之中，開始執行步驟(2)。

（2） 若隊列為空，則結束遍歷操作，否則取隊頭結點D。

（3） 若結點D的左孩子結點存在，則將其左孩子結點壓入隊列。

（4） 若結點D的右孩子結點存在，則將其右孩子結點壓入隊列，並重復步驟(2)。

【例6-2 BinaryTreeNode.cs.cs】二叉樹結點類，使用例6-1同名文件。

【例6-2 LevelOrderBinaryTree.cs】包含寬度優先遍歷方法的二叉樹集合類

打開例6-1的【BinaryTree.cs】文件，在BinaryTree類中添加如入方法後另存為LevelOrderBinaryTree.cs文件。
1 public void LevelOrder() //寬度優先遍歷
2 {
3 Queue queue = new Queue(); //聲明一個隊例
4 queue.Enqueue(_head); //把根結點壓入隊列
5 while (queue.Count > 0) //只要隊列不為空
6 {
7 Node node = (Node)queue.Dequeue(); //出隊
8 Console.Write(node.ToString()); //訪問結點
9 if (node.Left != null) //如果結點左孩子不為空
10 { //把左孩子壓入隊列
11 queue.Enqueue(node.Left);
12 }
13 if (node.Right != null) //如果結點右孩子不為熔
14 { //把右孩子壓入隊列
15 queue.Enqueue(node.Right);
16 }
17 }
18 }

【例6-2 Demo6-2.cs】二叉樹寬度優先遍歷測試
1 using System;
2 class Demo6_2
3 {
4 static void Main(string[] args)
5 { //使用字元串構造二叉樹
6 BinaryTree bTree = new BinaryTree("ABCDE#F");
7 bTree.LevelOrder();
8 }
9 }

運行結果：ABCDEF

❽ 線索二叉樹是一種什麼結構

物理結構。包括線性存儲和非線性存儲其中，線性存儲結構有順序、鏈接、索引和散列4種結構。非線性存儲結構有：樹形存儲結構、圖形存儲結構。

n個結點的二叉鏈表中含有n+1(2n-(n-1)=n+1)個空指針域。利用二叉鏈表中的空指針域，存放指向結點在某種遍歷次序下的前驅和後繼結點的指針。

這種加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹(Threaded BinaryTree)。根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和後序線索二叉樹三種。

(8)索引存儲二叉樹擴展閱讀：

二叉樹的遍歷本質上是將一個復雜的非線性結構轉換為線性結構，使每個結點都有了唯一前驅和後繼（第一個結點無前驅，最後一個結點無後繼）。對於二叉樹的一個結點，查找其左右子女是方便的，其前驅後繼只有在遍歷中得到。

為了容易找到前驅和後繼，有兩種方法。一是在結點結構中增加向前和向後的指針fwd和bkd，這種方法增加了存儲開銷，不可取；二是利用二叉樹的空鏈指針。

建立線索二叉樹，或者說對二叉樹線索化，實質上就是遍歷一棵二叉樹。在遍歷過程中，訪問結點的操作是檢查當前的左，右指針域是否為空，將它們改為指向前驅結點或後續結點的線索。為實現這一過程，設指針pre始終指向剛剛訪問的結點，即若指針p指向當前結點，則pre指向它的前驅，以便設線索。