1樓：
先介紹一下樹：
1.樹的定義
樹是一種常見的非線性的資料結構。樹的遞迴定義如下：
樹是n(n>0)個結點的有限集，這個集合滿足以下條件：
⑴有且僅有一個結點沒有前件（父親結點），該結點稱為樹的根；
⑵除根外，其餘的每個結點都有且僅有一個前件；
⑶除根外，每一個結點都通過唯一的路徑連到根上。這條路徑由根開始，而未端就在該結點上，且除根以外，路徑上的每一個結點都是前一個結點的後件（兒子結點）；
2、結點的分類
在樹中，一個結點包含一個元素以及所有指向其子樹的分支。結點一般分成三類
⑴根結點：沒有前件的結點。在樹中有且僅有一個根結點。
⑵分支結點：除根結點外，有後件的結點稱為分支結點。分支結點亦是其子樹的根；
⑶葉結點：沒有後件的結點稱為樹葉。由樹的定義可知，樹葉本身也是其父結點的子樹。
根結點到每一個分支結點或葉結點的路徑是唯一的。
3、有關度的定義
⑴結點的度：一個結點的子樹數目稱為該結點的度。顯
然，所有樹葉的度為0。
⑵樹的度：所有結點中最大的度稱為該樹的度。4、樹的深度（高度）
樹是分層次的。結點所在的層次是從根算起的。根結點在第一層，根的後件在第二層，其餘各層依次類推。
即若某個結點在第k層，則該結點的後件均處在第k+1層。圖（b）中的樹共有五層。在樹中，父結點在同一層的所有結點構成兄弟關係。
樹中最大的層次稱為樹的深度，亦稱高度。
5、有序樹和無序樹
按照樹中同層結點是否保持有序性，可將樹分為有序樹和無序樹。如果樹中同層結點從左而右排列，其次序不容互換，這樣的樹稱為有序樹；如果同層結點的次序任意，這樣的樹稱為無序樹。
6、樹的表示方法
樹的表示方法一般有兩種：
⑴自然界的樹形表示法：用結點和邊表示樹，例如上圖採用的就是自然界的樹形表示法。樹形表示法一般用於分析問題。
⑵括號表示法：先將根結點放入一對圓括號中，然後把它的子樹按由左而右的順序放入括號中，而對子樹也採用同樣方法處理：同層子樹與它的根結點用圓括號括起來，同層子樹之間用逗號隔開，最後用閉括號括起來。
例如圖可寫成如下形式
（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））
7、樹的儲存結構一般有兩種
⑴靜態的記錄陣列。所有結點儲存在一個陣列中，陣列元素為記錄型別，包括資料域和長度為n(n為樹的度)的陣列，分別儲存該結點的每一個兒子的下標
⑵動態的多重連結串列。由於樹中結點可以有多個元素，所以可以用多重連結串列來描述比較方便。所謂多重連結串列，就是每個結點由資料域和n(n 為樹的度)個指標域共n+1個域組成
下面是有關二叉樹的內容：
二叉樹的概念
二叉樹是一種很重要的非線性資料結構，它的特點是每個結點最多有兩個後件，且其子樹有左右之分（次序不能任意顛倒）。
1、二叉樹的遞迴定義和基本形態
二叉樹是以結點為元素的有限集，它或者為空，或者滿足以下條件：
⑴有一個特定的結點稱為根；
⑵餘下的結點分為互不相交的子集l和r，其中r是根的左子樹；l是根的右子樹；l和r又是二叉樹；
由上述定義可以看出，二叉樹和樹是兩個不同的概念
⑴樹的每一個結點可以有任意多個後件，而二叉樹中每個結點的後件不能超過2；
⑵樹的子樹可以不分次序（除有序樹外）；而二叉樹的子樹有左右之分。我們稱二叉樹中結點的左後件為左兒子，右後件為右兒子。
2、二叉樹的兩個特殊形態
⑴滿二叉樹： 如果一棵二叉樹的任何結點，或者是樹葉，或者恰有兩棵非空子樹，則此二叉樹稱作滿二叉樹。可以驗證具有n個葉結點的滿二叉樹共有2n-1個結點。
⑵完全二叉樹：如果一棵二叉樹最多隻有最下面兩層結點度數可以小於2，並且最下面一層的結點都集中在該層最左邊的若干位置上，則稱此二叉樹為完全二叉樹
3、二叉樹的三個主要性質
性質1：在二叉樹的第i（≥1）層上，最多有2i-1個 結點
證明：我們採用數學歸納法證明：當i=1時只有一個根結點，即2i-1=20=1，結論成立。
假設第k(i=k)層上最多有2k-1個結點，考慮i=k+1。由歸納假設，在二叉樹第k層上最多有2k-1個結點，而每一個結點最多有兩個子結點，因此在第k+1層上最多有2．2k-1=2(k+1)-1=2i，結論成立。綜上所述，性質1成立。
性質2：在深度為k(k≥1)的二叉樹中最多有2k-1個 結點。
證明：由性質1，在二叉樹第i層上最多有2i-1個結點，顯然，第1層¨第k層的最多結點數為 個結點。證畢。
性質3：在任何二叉樹中，葉子結點數總比度為2的結點多1。
證明：設n0為二叉樹的葉結點數；n1為二叉樹中度為1的結點數；n2為二叉樹中度為2的結點數，顯然n=n0+n1+n2 （1）
由於二叉樹中除了根結點外，其餘每個結點都有且僅有一個前件。設 b為二叉樹的前件個數，n=b+1（2）
所有這些前件同時又為度為1和度為2的結點的後件。因此又有b=n1+2n2 (3)
我們將（3）代入（2）得出n=n1+2n2+1 (4)
比較（1）和（4），得出n0=n2+1,即葉子數比度為2的結點數多1
4、普通有序樹轉換成二叉樹
普通樹為有序樹t，將其轉化成二叉樹t’的規則如下：
⑴t中的結點與t’中的結點一一對應，即t中每個結點的序號和值在t’中保持不變；
⑵t中某結點v的第一個兒子結點為v1，則在t’中v1為對應結點v的左兒子結點；
⑶t中結點v的兒子序列，在t’中被依次連結成一條開始於v1的右鏈；
由上述轉化規則可以看出，一棵有序樹轉化成二叉樹的根結點是沒有右子樹的，並且除保留每個結點的最左分支外，其餘分支應去掉，然後從最左的兒子開始沿右兒子方向依次連結該結點的全部兒子。
5、二叉樹的儲存結構
將每個結點依次存放在一維陣列中，用陣列下標指示結點編號，編號的方法是從根結點開始編號1，然後由左而右進行連續編號。每個結點的資訊包括
⑴一個資料域（data）；
⑵三個指標域，其中有父結點編號（prt）、左兒子結點編號（lch）和右兒子結點編號（rch）。
滿二叉樹和完全二叉樹一般採用順序儲存結構
對於一般的二叉樹，通常採用鏈式分配，即用二重連結串列表示一般的二叉樹。這種鏈式分配即可以採用靜態資料結構（陣列），又可以採用動態資料結構（指標）。如果二叉樹的儲存需求量超過64kb，則採用後者。
由於二叉樹中每個結點通常包括資料元素和兩個分支。因此二叉樹對應的二重連結串列中每個結點應有三個域：
⑴值域： data
⑵左指標域： lch
⑶右指標域： rch
這種連結串列也稱為二叉連結串列。二叉連結串列頭指標bt指向二叉樹的根結點
6、二叉樹的遍歷
二叉樹遍歷的定義：按照一定的規律不重複地訪問(或取出結點中的資訊，或對結點作其它的處理)二叉樹中的每一個結點。
二叉樹遍歷的順序：如果用l、d、r分別表示遍歷左子樹、訪問根結點、遍歷右子樹，則對二叉樹的遍歷可以有下列六種（3!=6）組合：
ldr、 lrd、 dlr、 drl、rdl、 rld。若再限定先左後右的次序，則只剩下三種組合：ldr（中序遍歷）、lrd（後序遍歷）、dlr（前序遍歷）。
前序遍歷的規則如下：
若二叉樹為空，則退出。否則
⑴訪問處理根結點；
⑵前序遍歷左子樹；
⑶前序遍歷右子樹；
特點：由左而右逐條訪問由根出發的樹支 （回溯法的基礎）
中序遍歷的規則：
若二叉樹為空，則退出；否則
⑴中序遍歷左子樹；
⑵訪問處理根結點；
⑶中序遍歷右子樹；
後序遍歷的規則如下：
若二叉樹為空，則退出；否則
⑴後序遍歷左子樹；
⑵後序遍歷右子樹；
⑶訪問處理根結點；
特點：可統計任一個結點為根的子樹的情況（例如子樹的權和，最優策略的選擇（博弈數））
2樓：
每個節點擁有的分支節點不超過2個
——個人理解，書上怎麼說得我忘了
3樓：浪情劍客
關於2x樹的演算法也蠻多的,你要的是哪種演算法?
用2x搜尋樹實現字典?
還是就單單2叉樹的基本演算法?
二叉樹是重要的資料結構，點的不同的二叉樹有幾個
2個點有2種 根有左兒子或者根有右兒子 3個點有5種 左邊2個結點或者右邊2個結點或者左右各一結點,2 2 1 5 4個點有14種 左邊3個結點或者右邊3個結點或者左1右2或者左2右1 5 5 2 2 14 5個點有42種 左4或右4或左3右1或左1右3或左2右2，14 14 5 5 2 2 42 ...
資料結構中二叉樹建立結點為什麼用雙重指標？詳細解釋下雙重指標
指標的指標。因為樹的結點要用指標描述。如果只用指標，作形參傳給建立結點的函式，這個指標值傳給了函式棧中的記憶體，函式返回後，函式棧銷毀，不能獲得結點。而用指標的指標，函式內修改了這個雙重指標指向的值 即結點指標 在函式外也能獲得結點。這swap 函式要用指標而不能用值做引數一樣。只是這裡的值本身就是...
線索二叉樹是一種什麼結構線索二叉樹是一種結構？
物理結構。包括線性儲存和非線性儲存其中，線性儲存結構有順序 鏈結 索引和雜湊4種結構。非線性儲存結構有 樹形儲存結構 圖形儲存結構。n個結點的二叉鍊錶中含有n 1 2n n 1 n 1 個空指標域。利用二叉鍊錶中的空指標域，存放指向結點在某種遍歷次序下的前驅和後繼結點的指標。這種加上了線索的二叉鍊錶...