樹 (抽象資料類型)

樹係電腦科學上時常用到嘅數據結構。用較日常化嘅用語講，樹嘅重點特性係結構中嘅數據有「高低層」之分。樹狀數據有廣泛嘅應用價值，例如係教人工智能玩遊戲嘅程式，就成日都會用樹嚟表示遊戲狀態跟住會點樣變化。

定義

數據樹會^[1]^{:Ch. 6}

全部節點連通，即係是但搵兩個節點，都會有一條獨一無二嘅路徑連接住兩者；而且無環（acyclic）。
有若干個節點（node），每個節點都儲住咗件數據。
啲節點分層－除咗做起始點嗰個節點（根節點；root）之外，每個節點都有且只有一個母節點母節點（parent；指喺佢之上，連住嗰個節點嘅另一個節點）。
一個節點，可以有若干個子節點（child / children）；

於是，就形成呢拃節點喺起始點嗰度一層層噉分叉。

喺電腦科學上，通常會將數據樹畫做樹狀圖噉嘅樣，根節點畫喺最頂，根節點嘅子節點會並排噉列喺根節點下面，根節點嘅子節點嘅子節點會並排噉列喺下一層，如此類推。好似下圖噉，幅圖表示緊一樖數據樹，紅色係該數據樹嘅根，根下一層嘅係佢啲子節點，再下一層嗰啲係根嘅子節點嘅子節點，如此類推，而每個節點入面嗰個整數就係嗰個節點裝住嘅數據^[2]。

運算

對二元樹（指樖樹每個節點頂攏得兩個子節點，好似下圖噉^[3]）可以做嘅簡單運算有以下呢啲^[1]^{:Ch. 6}：

EmptyTree，出一樖空嘅數據樹；
MakeTree(v, l, r)，建立一樖二元樹，根節點係 v，由兩樖二元樹 l 同 r 組成；
Leaf(v) = MakeTree(v, EmptyTree, EmptyTree)－建立一樖得一個節點 v 嘅二元樹；
isEmpty(t)，如果 t 係樖空嘅數據樹，噉 isEmpty(t) 會出真，否則就出假。

應用

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

睇埋

引述

1 2 John Bullinaria, (2019). Lecture Notes for Data Structures and Algorithms (PDF). School of Computer Science, University of Birmingham.
↑ Susanna S. Epp (Aug 2010). Discrete Mathematics with Applications. Pacific Grove, CA: Brooks/Cole Publishing Co. p. 694.
↑ Rowan Garnier; John Taylor (2009). Discrete Mathematics:Proofs, Structures and Applications, Third Edition. CRC Press. p. 620.
↑ Monte Carlo Tree Search 互聯網檔案館嘅歸檔，歸檔日期2020年3月28號，.. Towards Data Science.
↑ Rossi, L., Winands, M.H. and Butenweg, C., 2022. Monte Carlo Tree Search as an intelligent search tool in structural design problems. Engineering with Computers, 38(4), pp.3219-3236，佢哋 2.1 嗰度第一句就噉講："MCTS is a search technique that works on a tree data structure."

拎

（英文）樹數據結構入門，GeeksForGeeks

[johnbull-1] 1 2 John Bullinaria, (2019). Lecture Notes for Data Structures and Algorithms (PDF). School of Computer Science, University of Birmingham.

[2] Susanna S. Epp (Aug 2010). Discrete Mathematics with Applications. Pacific Grove, CA: Brooks/Cole Publishing Co. p. 694.

[3] Rowan Garnier; John Taylor (2009). Discrete Mathematics:Proofs, Structures and Applications, Third Edition. CRC Press. p. 620.

[4] Monte Carlo Tree Search 互聯網檔案館嘅歸檔，歸檔日期2020年3月28號，.. Towards Data Science.

[5] Rossi, L., Winands, M.H. and Butenweg, C., 2022. Monte Carlo Tree Search as an intelligent search tool in structural design problems. Engineering with Computers, 38(4), pp.3219-3236，佢哋 2.1 嗰度第一句就噉講："MCTS is a search technique that works on a tree data structure."

[1]

[2]

[3]

[4]

[5]