樹 (抽象資料類型)

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

定義

睇埋：數據結構

一樖數據樹都係會

• 有若干粒節點（node），每粒節點都儲住咗件數據；而且
• 啲節點分層－除咗做起始點嗰粒節點（根節點；root）之外，每粒節點有一粒（而且頂櫳一粒）母節點（parent；指喺嗰粒節點上面，連住嗰粒節點嘅另一粒節點）；
• 一粒節點可以有若干粒子節點（child / children）；

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

運算

睇埋：搜尋演算法

對樹型數據可以做嘅簡單運算有以下呢啲：

• EmptyTree，出一樖空嘅數據樹；
• MakeTree(v, l, r)，建立一樖二元樹（binary tree；指樖樹每粒節點頂攏得兩粒子節點，好似下圖噉），根節點係 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))))

應用

睇埋：人工智能

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

睇埋

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