1：鄰接表模式（adjacency list model）

2：先根遍歷樹算法（modified PReorder tree traversal algorithm）

參考數據結構：

中國

|

|---陜西

| |

| |---渭南

| |

| |--- 西安

| |

| |--鐘樓

| | |

| | |--大雁塔

|

|---云南

| |

| |---麗江

1：鄰接目錄模式：

一般情況下，我們在數據庫中增加一個parent字段表示這個節點的父節點，從而將整個樹狀描述出來

如：

parent name

中國

中國 陜西

中國 云南

陜西 渭南

陜西 西安

云南 麗江

西安 鐘樓

西安 大雁塔

等這樣我們就能夠通過數據庫保存整個樹狀結構啦。

通過這種方法需要得到一個多級結構時候需要進行一個遞歸， 通過遞歸的方法我們可以得到任意節點的路徑。

這種方法的優點是簡單，容易理解。缺點是運行速度很慢。尤其是數據量很大的時候需要進行很多查詢時候才能完成一個樹， 效率很低。

2:先根遍歷樹算法

將多級數據按照下面的格式劃出來

1 中國 16

|

+------------------------+

2 陜西 11 12 云南 15

| |

+-------------+ 13 麗江 14

3 渭南 4 5 西安 10

|

+-----------+

6 鐘樓 7 8 大雁塔 9

我們給根節點“中國”左側標上1， 然后沿著這個樹向下在“陜西”左側標上2， 然后繼續前進， 向下在“渭南”左側標上3， 渭南沒有子節點，所以在“渭南”右側標上4， 然后繼續“渭南”的右側節點。。。沿著整個樹的給每個節點的左側和右側標上數字。最后一個數組標在“中國”右側為16。 你只要用手指從1指到16就知道怎么回事啦。

這些數字表明了各個節點之間的關系。我們可以看到， 所有左側大于2， 右側小于11的節點，都是“陜西”的子節點。

這樣我們可以在數據庫中用left, right表示左右數字。如：

我們給根節點“中國”左側標上1， 然后沿著這個樹向下在“陜西”左側標上2， 然后繼續前進， 向下在“渭南”左側標上3， 渭南沒有子節點，所以在“渭南”右側標上4， 然后繼續“渭南”的右側節點。。。沿著整個樹的給每個節點的左側和右側標上數字。最后一個數組標在“中國”右側為16。 你只要用手指從1指到16就知道怎么回事啦。

這些數字表明了各個節點之間的關系。我們可以看到， 所有左側大于2， 右側小于11的節點，都是“陜西”的子節點。

這樣我們可以在數據庫中用left, right表示左右數字。如：

name left right

中國 1 16

陜西 2 11

云南 12 15

渭南 3 4

西安 5 10

鐘樓 6 7

大雁塔 8 9

麗江 13 14

這樣我們如果想得到 "陜西"下的所有節點。只需要執行：

select * from table where left between 2 and 11;

要想知道“西安”的路徑只需要執行：

select * from table where left < 5 and right > 10;

計算某個節點有多少子孫節點： 子孫節點數＝（右值－左值－1）/2;

要算出所有節點的左右值， 數據庫中需要parent字段，然后編寫一個計算左右值遞歸函數執行。（這里略去不談）。

主要考慮如何進行一個子節點的增加，刪除。

◆方法1： 在數據庫中保留parent字段， 增加節點后，調用計算左右值遞歸函數重新計算左右值。 該方法不推薦用

◆方法2： 改變所有位于新節點右側的左右值。

比如：想添加“華清池”作為“西安”的最后一個節點，我們給它挪出一個空間，“西安”的右值改為12， “陜西”的右值改為13， “云南”及其子節點的左右值從“12－15”改為 “14－17”， “中國”的右值改為18。即給左右值大于9的所有節點加2 （9為西安最后一個子節點的右值）

update table set right=right+2 where right > 9;

update table set left=left+2 where left > 9;

這樣就給新節點騰出空間，它的左右值分別為 9+1, 9+2;

insert into table set left=10, right=11, name='華清池';

當然，刪除一個節點時候給左右值大于該節點右值的所有節點減2。

注釋：以上兩種方法的采用根據我們可以針對具體情況來酌情考慮，假如查詢量小但頻繁添加，刪除則建議采用第一種。假如查詢量偏大，我們可以考慮使用第二種方法。