樹 (抽象資料類型)

樹係一種喺電腦科學上好有用嘅數據結構，重點特性係拃數據有「高低層」之分。

定義

一樖數據樹都係會
有若干粒節點，每粒節點都儲住咗件數據；而且
啲節點分層－除咗做起始點嗰粒節點之外，每粒節點有一粒母節點；
一粒節點可以有若干粒子節點；

於是就形成拃節點喺起始點嗰度一層層噉每層都分叉嘅樣，而是但攞粒根節點以外嘅節點，粒節點同根節點之間都有條獨一無二嘅路徑連住兩點。喺電腦科學上，啲人通常會將數據樹畫做樹狀圖噉嘅樣，根節點畫喺最頂，根節點嘅子節點會並排噉列喺根節點下面，根節點嘅子節點嘅子節點會並排噉列喺下一層... 如此類推。好似下面幅圖噉，幅圖表示緊樖數據樹，嗰點係樖數據樹嘅根節點，根節點下一層嘅係佢啲子節點，再下一層嗰啲係根節點嘅子節點嘅子節點... 如此類推，而每粒節點入面嗰個整數就係粒節點裝住嗰件數據。

運算

對樹型數據可以做嘅簡單運算有以下呢啲：
EmptyTree，出一樖空嘅數據樹；
MakeTree(v, l, r)，建立一樖二元樹，根節點係 v，由兩樖二元樹 l 同 r 組成；
Leaf(v) = MakeTree(v, EmptyTree, EmptyTree)－建立一樖得一粒節點 v 嘅二元樹；
isEmpty(t)，如果 t 係樖空嘅數據樹，噉 isEmpty(t) 會出 1，否則就出 0；
建立一樖有咁上下複雜嘅二元樹可以用類似噉嘅碼：
t = MakeTree(8, MakeTree(3,Leaf(1),MakeTree(6,EmptyTree,Leaf(7))), MakeTree(11,MakeTree(9,EmptyTree,Leaf(10)),MakeTree(14,Leaf(12),Leaf(15))))

應用

喺實際應用上，樹呢款數據結構成日畀人攞嚟儲住一啲有關決策嘅資訊：想像家吓有人工智能研究者想教電腦玩遊戲，想部電腦識捉國際象棋；佢可以教部電腦將捉國際象棋嘅過程想像做一樖數據樹－捉國際象棋可以想像成喺每個時間點度揀其中一個可能選擇，跟住再行去下一個時間點嗰度，而每粒節點入面嗰件數據表示「揀呢個選擇嘅效益」。有關數據樹嘅具體應用例子，可以睇吓蒙地卡羅樹搜尋呢種演算法。

數據結構
二元搜尋樹
蒙地卡羅樹搜尋

攷

電腦科學