資料結構/樹公理
< 資料結構
對樹進行公理化的開發對於它們的系統化研究非常重要。
樹有兩種基本定義：集合論定義和圖論定義。它們並不等價。圖論定義將樹稱為“無環圖”或“頂點之間具有唯一路徑的圖”。在集合論中，樹只是一個帶有偏序的集合，使得總是存在一個“最小元素”；你可以在這個定義中想象一棵樹，它不符合圖論的定義。
在下文中，我採取了中間路線。我用構造性的方法定義樹，但採用與幾乎所有代數中歸納集的定義相同的方式。當然，透過避免將樹視為圖的子集，我忽略了關於樹與其他型別圖的關係的一些非常重要的結論；但這裡提出的狹義定義保持對樹的基本屬性的關注。為了彌補，開頭部分簡短介紹了我們將要研究的樹的圖論定義。
下面描述的樹是有向圖。它們是有根的：也就是說，存在一個元素，所有元素最終都源於該元素，並且沒有元素指向該元素。（圖論樹的通用定義也適用，即樹是一個無環圖）。