1. 樹的存儲方法主要有哪些
三叉鏈表不就是存儲結構，其具體實現既可以用指針實現，也可以用數組實現 至於遍歷方法可以任意地在二叉樹中上下
2. 【數據結構】樹的定義和樹的三種存儲結構
樹（Tree）是n（n>=0）個結點的有限集。n=0時稱為空樹。在任意一顆非空樹中：
假設以一組連續空間存儲數的結點，同時在每個結點中， 附設一個指示器指示其雙親結點到鏈表中的位置 。
把每個結點的孩子結點排列起來，以 單鏈表作為存儲結構 ，則n個結點有n個孩子鏈表，如果是葉子結點則此單鏈表為空。然後 n個頭指針又組成一個線性表，採用順序存儲結構 ，存放進一個一維數組中。
孩子表示法有兩種結點結構： 孩子鏈表的孩子結點 和 表頭數組的表頭結點
對於孩子表示法，查找某個結點的某個孩子，或者找某個結點的兄弟，只需要查找這個結點的孩子單鏈表即可。但是 當要尋找某個結點的雙親時 ，就不是那麼方便了。所以可以將雙親表示法和孩子表示法結合，形成 雙親孩子表示法 。
任意一棵樹，它的結點的第一個孩子如果存在就是唯一的，它的右兄弟存在也是唯一的。因此，設置兩個指針，分別指向該結點的第一個孩子和此結點的右兄弟。
3. 數據結構，樹的常用存儲方式
存入文本文件，每行：孩子節點-父節點。
這樣也方便用Hadoop進行處理。
4. 樹的存儲表示是什麼
樹的存儲結構根據應用的不同而不同，有的從雙親的角度考慮，引出了雙親表示法，有的從孩子的角度考慮，給出孩子表示法，還有的從孩子和兄弟的角度來討論。這些都是人們在大量的應用中所使用的不同形式的存儲結構，這里介紹常用的雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法。
1.雙親表示法由樹的定義可知，樹中每個結點都有且僅有一個雙親結點，根據這一特性，可以用一組連續的一維數組來存儲樹中的各個結點（一般按層次存儲），數組中的一個元素對應樹中的一個結點，其中包括結點的數據信息以及該結點的雙親在數組中的下標。樹的這種存儲方法稱為雙親表示法，雙親表示法的結點結構如圖1所示，其中，data表示數據域，存儲樹中結點的數據信息，parent表示指針域，存儲該結點的雙親在數組中的下標。
1.雙親表示法的存儲結構2）雙親表示法示例圖1所示的樹的雙親表示如圖1所示，這是一棵樹及其雙親表示法的存儲結構。根結點A無雙親，所以parent的值為－1，G、H和I的parent值為4，表示它們的雙親是下標為4的結點E。這種存儲結構利用任一結點的雙親是唯一的性質，可以方便地直接找到任一結點的雙親結點，但求結點的孩子結點時需要掃描整個數組。
圖1樹的雙親表示法示例
5. 二叉樹通常鏈式結構還有什麼結構
二叉樹就物理結構來分可以分成：順序存儲結構和鏈式存儲結構。
（1）順序存儲結構：
順序存儲結構，顧名思義就是二叉樹的數據元素存放在一組連續的存儲單元中。其主要有一下幾個特點：
①邏輯上相鄰的兩個元素在物理位置上也是相鄰的；
②操作刪除和插入的時候，需要整體移動元素；
③需要預先分配空間，不能動態增長；
（2）鏈式存儲結構：
鏈式存儲結構中二叉樹的每個結點至少包含三個域：數據域、左指針域和右指針域。其二叉樹是通過指針實現，鏈式存儲結構有以下幾個特點：
①邏輯上相鄰的兩個元素在物理位置上不一定是相鄰的；
②操作刪除和插入的時候，不需要整體移動元素；只需要修改相應的指針即可；
③不需要預先分配空間；
④存儲指針本身會消耗一定的存儲的空間；
6. 數據結構—樹的詳解
樹是非線性存儲結構，存儲的是具有「一對多」關系的數據元素的集合。
使用樹結構存儲的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意圖。對於數據 A 來說，和數據 B、C、D 有關系；對於數據 B 來說，和 E、F 有關系。這就是「一對多」的關系。
將具有「一對多」關系的集合中的數據元素按照圖中的形式進行存儲，整個存儲形狀在邏輯結構上看，類似於實際生活中倒著的樹，所以稱這種存儲結構為「樹型」存儲結構。
使用樹結構存儲的每一個數據元素都被稱為「結點」。例如，圖 1中，數據元素 A 就是一個結點；
對於圖 1中的結點 A、B、C、D 來說，A 是 B、C、D 結點的父結點（也稱為「雙親結點」），而 B、C、D 都是 A 結點的子結點（也稱「孩子結點」）。對於 B、C、D 來說，它們都有相同的父結點，所以它們互為兄弟結點。
每一個非空樹都有且只有一個被稱為根的結點。圖 1中，結點A就是整棵樹的根結點。
樹根的判斷依據為：如果一個結點沒有父結點，那麼這個結點就是整棵樹的根結點。
如果結點沒有任何子結點，那麼此結點稱為葉子結點（葉結點）。例如圖 1中，結點 K、L、F、G、M、I、J 都是這棵樹的葉子結點。
如圖 1中，整棵樹的根結點為結點 A，而如果單看結點 B、E、F、K、L 組成的部分來說，也是棵樹，而且節點 B 為這棵樹的根結點。所以稱 B、E、F、K、L 這幾個結點組成的樹為整棵樹的子樹；同樣，結點 E、K、L 構成的也是一棵子樹，根結點為 E。
注意：單個結點也是一棵樹，只不過根結點就是它本身。圖 1中，結點 K、L、F 等都是樹，且都是整棵樹的子樹。
知道了子樹的概念後，樹也可以這樣定義：樹是由根結點和若干棵子樹構成的。
如果集合本身為空，那麼構成的樹就被稱為空樹。
空樹中沒有結點。
補充：在樹結構中，對於具有同一個根結點的各個子樹，相互之間不能有交集。例如，圖 1中，除了根結點 A，其餘元素又各自構成了三個子樹，根結點分別為 B、C、D，這三個子樹相互之間沒有相同的結點。如果有，就破壞了樹的結構，不能算做是一棵樹。結點的度和層次
對於一個結點，擁有的子樹數（結點有多少分支）稱為結點的度（Degree）。例如，圖 1中，根結點 A 下分出了 3 個子樹，所以，結點 A 的度為 3。
一棵樹的度是樹內各結點的度的最大值。圖 1表示的樹中，各個結點的度的最大值為 3，所以，整棵樹的度的值是 3。
從一棵樹的樹根開始，樹根所在層為第一層，根的孩子結點所在的層為第二層，依次類推。對於圖 1來說，A 結點在第一層，B、C、D 為第二層，E、F、G、H、I、J 在第三層，K、L、M 在第四層。
一棵樹的深度（高度）是樹中結點所在的最大的層次。圖 1樹的深度為 4。
如果兩個結點的父結點雖不相同，但是它們的父結點處在同一層次上，那麼這兩個結點互為堂兄弟。例如，圖 1中，結點 G 和 E、F、H、I、J 的父結點都在第二層，所以之間為堂兄弟的關系。
如果樹中結點的子樹從左到右看，誰在左邊，誰在右邊，是有規定的，這棵樹稱為有序樹；反之稱為無序樹。
在有序樹中，一個結點最左邊的子樹稱為"第一個孩子"，最右邊的稱為"最後一個孩子"。
圖 1來說，如果是其本身是一棵有序樹，則以結點 B 為根結點的子樹為整棵樹的第一個孩子，以結點 D 為根結點的子樹為整棵樹的最後一個孩子。
由 m（m >= 0）個互不相交的樹組成的集合被稱為森林。圖 1中，分別以 B、C、D 為根結點的三棵子樹就可以稱為森林。
樹可以理解為是由根結點和若乾子樹構成的，而這若乾子樹本身是一個森林，所以，樹還可以理解為是由根結點和森林組成的。用一個式子表示為：
Tree =（root,F），其中，root 表示樹的根結點，F 表示由 m（m >= 0）棵樹組成的森林。
數據結構中為了存儲和查找的方便，用各種樹結構來存儲文件，我們首先介紹下基本的樹的種類：二叉查找樹（二叉排序樹）、平衡二叉樹（AVL樹）、紅黑樹、B-樹、B+樹、字典樹（trie樹）、後綴樹、廣義後綴樹。
二叉查找樹是一種動態查找表，具有這些性質：
（1）若它的左子樹不為空，則左子樹上的所有節點的值都小於它的根節點的值；
（2）若它的右子樹不為空，則右子樹上所有節點的值都大於它的根節點的值；
（3）其他的左右子樹也分別為二叉查找樹；
（4）二叉查找樹是動態查找表，在查找的過程中可見添加和刪除相應的元素，在這些操作中需要保持二叉查找樹的以上性質。
含有相同節點的二叉查找樹可以有不同的形態，而二叉查找樹的平均查找長度與樹的深度有關，所以需要找出一個查找平均長度最小的一棵，那就是平衡二叉樹，具有以下性質：
（1）要麼是棵空樹，要麼其根節點左右子樹的深度之差的絕對值不超過1；
（2）其左右子樹也都是平衡二叉樹；
（3）二叉樹節點的平衡因子定義為該節點的左子樹的深度減去右子樹的深度。則平衡二叉樹的所有節點的平衡因子只可能是-1,0,1。
紅黑樹是一種自平衡二叉樹，在平衡二叉樹的基礎上每個節點又增加了一個顏色的屬性，節點的顏色只能是紅色或黑色。具有以下性質：
（1）根節點只能是黑色；
（2）紅黑樹中所有的葉子節點後面再接上左右兩個空節點，這樣可以保持演算法的一致性，而且所有的空節點都是黑色；
（3）其他的節點要麼是紅色，要麼是黑色，紅色節點的父節點和左右孩子節點都是黑色，及黑紅相間；
（4）在任何一棵子樹中，從根節點向下走到空節點的路徑上所經過的黑節點的數目相同，從而保證了是一個平衡二叉樹。
B-樹是一種平衡多路查找樹，它在文件系統中很有用。一棵m階B-樹（圖為4階B-樹），具有下列性質：
（1）樹中每個節點至多有m棵子樹；
（2）若根節點不是葉子節點，則至少有2棵子樹；
（3）除根節點之外的所有非終端節點至少有 m/2 棵子樹；
（4）每個節點中的信息結構為（A0,K1,A1,K2......Kn,An），其中n表示關鍵字個數，Ki為關鍵字，Ai為指針；
（5）所有的葉子節點都出現在同一層次上，且不帶任何信息，也是為了保持演算法的一致性。
B+數是B-樹的一種變形，它與B-樹的差別在於（圖為3階B+樹）：
（1）有n棵子樹的節點含有n個關鍵字；
（2）所有的葉子節點包含了全部關鍵字的信息，及指向這些關鍵字記錄的指針，且葉子節點本身按關鍵字大小自小到大順序鏈接；
（3）所有非終端節點可以看成是索引部分，節點中僅含有其子樹（根節點）中最大（或最小）關鍵字，所有B+樹更像一個索引順序表；
（4）對B+樹進行查找運算，一是從最小關鍵字起進行順序查找，二是從根節點開始，進行隨機查找。
字典樹是一種以樹形結構保存大量字元串。以便於字元串的統計和查找，經常被搜索引擎系統用於文本詞頻統計。它的優點是：利用字元串的公共前綴來節約存儲空間，最大限度地減少無謂的字元串比較，查詢效率比哈希表高。具有以下特點：
（1）根節點為空；
（2）除根節點外，每個節點包含一個字元；
（3）從根節點到某一節點，路徑上經過的字元連接起來，為該節點對應的字元串。
（4）每個字元串在建立字典樹的過程中都要加上一個區分的結束符，避免某個短字元串正好是某個長字元串的前綴而淹沒。
所謂後綴樹，就是包含一則字元串所有後綴的壓縮了的字典樹。先說說後綴的定義。給定一長度為n的字元串S=S 1 S 2 ..S i ..S n ，和整數i，1 <= i <= n，子串S i S i+1 ...S n 都是字元串S的後綴。以字元串S=XMADAMYX為例，它的長度為8，所以S[1..8], S[2..8], ... , S[8..8]都算S的後綴，我們一般還把空字串也算成後綴。這樣，我們一共有如下後綴。對於後綴S[i..n]，我們說這項後綴起始於i。
所有這些後綴字元串組成一棵字典樹：
上圖，我們可以看到不少值得壓縮的地方。比如藍框標注的分支都是獨苗，沒有必要用單獨的節點同邊表示。如果我們允許任意一條邊里包含多個字母，就可以把這種沒有分叉的路徑壓縮到一條邊。另外每條邊已經包含了足夠的後綴信息，我們就不用再給節點標注字元串信息了。我們只需要在葉節點上標註上每項後綴的起始位置。於是我們得到下圖：
這樣的結構丟失了某些後綴。比如後綴X在上圖中消失了，因為它正好是字元串XMADAMYX的前綴。為了避免這種情況，我們也規定每項後綴不能是其它後綴的前綴。要解決這個問題其實挺簡單，在待處理的子串後加一個空字串就行了。例如我們處理XMADAMYX前，先把XMADAMYX變為 XMADAMYX$，於是就得到suffix tree。
這就形成一棵後綴樹了。關於如何建立一棵後綴樹，已有很成熟的演算法，能在o(n)時間內解決。
廣義後綴樹是好幾個字元串的的所有後綴組成的字典樹，同樣每個字元串的所有後綴都具有一個相同的結束符，不同字元串的結束符不同。
傳統的後綴樹只能處理一個單詞的所有後綴。廣義後綴樹存儲任意多個單詞的所有後綴。例如字元串「abab」和「baba」，首先將它們使用特殊結束符鏈接起來，如表示成"ababbaba#",然後求連接後的新字元的後綴樹，遍歷所得後綴樹，如遇到特殊字元，如"baba#",然後求連接後的新字元的後綴樹，遍歷所得後綴樹，如遇到特殊字元，如"","#"等則去掉以該節點為跟的子樹，最後所得後綴樹即為原字元串組的廣義後綴樹。其實質是將兩個字元串的所有後綴，即：abab,bab,bab,ab,b,b,baba#,aba#,ba#,a#,組成字典樹，再進行壓縮處理。
廣義後綴樹的一個常應用就是判斷兩個字元串的相識度。
簡單地理解，滿足以下兩個條件的樹就是二叉樹：
二叉樹的性質經過前人的總結，二叉樹具有以下幾個性質：
性質 3 的計算方法為：對於一個二叉樹來說，除了度為 0 的葉子結點和度為 2 的結點，剩下的就是度為 1 的結點（設為 n1），那麼總結點 n=n 0 +n 1 +n 2 。
同時，對於每一個結點來說都是由其父結點分支表示的，假設樹中分枝數為 B，那麼總結點數 n=B+1。而分枝數是可以通過 n1 和 n2 表示的，即 B=n 1 +2 n 2 。所以，n 用另外一種方式表示為 n=n 1 +2 n 2 +1。
兩種方式得到的 n 值組成一個方程組，就可以得出 n 0 =n 2 +1。
二叉樹還可以繼續分類，衍生出滿二叉樹和完全二叉樹。
如果二叉樹中除了葉子結點，每個結點的度都為 2，則此二叉樹稱為滿二叉樹。
滿二叉樹除了滿足普通二叉樹的性質，還具有以下性質：
如果二叉樹中除去最後一層節點為滿二叉樹，且最後一層的結點依次從左到右分布，則此二叉樹被稱為完全二叉樹。
如圖 3a) 所示是一棵完全二叉樹，圖 3b) 由於最後一層的節點沒有按照從左向右分布，因此只能算作是普通的二叉樹。
完全二叉樹除了具有普通二叉樹的性質，它自身也具有一些獨特的性質，比如說，n 個結點的完全二叉樹的深度為 [log 2 n ]+1。
[log 2 n ]表示取小於[log 2 n ]的最大整數。例如，[[log 2 4 ]] = 2，而 [[log 2 5 ]] 結果也是 2。
對於任意一個完全二叉樹來說，如果將含有的結點按照層次從左到右依次標號（如圖 3a)），對於任意一個結點 i ，完全二叉樹還有以下幾個結論成立：
7. 二叉樹的存儲結構是怎樣的有哪些類型的存儲結構對應的c語言描述是
樓上回答的是樹的存儲，不是二叉樹的存儲，主要如下：
1、順序存儲：適用於完全二叉樹，如果根從1開始編號，則第i結點的左孩子編號為2i，右孩子為2i+1，雙親編號為(i/2）下取整，空間緊密
2、二叉鏈表：適用於普通二叉樹，每個結點除了數據外，還有分別指向左右孩子結點的指針，存儲n個結點有n+1個空指針域，存儲密度小於順序存儲，但是適用范圍廣，缺陷是正常遍歷只能從雙親向孩子，退回來一般需要藉助棧（或者用遞歸，其實也是棧）
3、三叉鏈表：同樣適用於普通二叉樹，結點除了數據外，還有左右孩子與雙親的指針，存儲密度低於二叉鏈表，但是可以非常方便地在二叉樹中遍歷，不需要其他輔助工具