有向樹

有向樹也許是圖論中使用最廣泛的一類圖形，特別是在計算機科學中數據庫的構造以及語言的編譯方面用途極廣。

在根樹T中，出度為零的點稱為樹葉，T中其他頂點稱為內點或支點。在根樹中，有時需要考慮同一層上結點的次序，規定了每一層上的結點的次序的根樹稱為有序樹。 ^[1] 

滿足下列條件的有向圖被稱為有向樹：

（1）有且僅有一個結點的入度為0；

（2）除樹根外的結點入度為1；

（3）從樹根到任一結點有一條有向通路。

如果有向圖在不考慮邊的方向時，是一棵樹，那麼這個有向圖稱為有向樹。進一步的，如果有一顆有向樹T，恰有一個頂點的入度為0，其餘頂點的入度都為1，則稱T為根樹。

如果有向圖在不考慮邊的方向時是一棵樹，那麼這個有向圖稱為有向樹，通常用T表示。在計算機科學中，常用的有向樹是根樹。

在根樹中，有向邊的方向都是一致的，自上而下，因此可以略去表示邊的方向的箭頭。 ^[2]