樹
樹型結構是以分支關係定義的層次結構，它是一種重要的非線性結構。
樹形結構在客觀世界中廣泛存在，例如人類的家庭族譜以及各種社會組織機構都可以用樹形結構來表示，又如在計算機檔案管理和信息組織方面也用到樹形結構。
樹是由一個或多個結點組成的有限集合 T 。 其中：
（ 1 ）一個特定的結點稱為該樹的根（ root ）結點 ;
（ 2 ）結點之外的其餘結點可分為 m （m ≥ 0 ）個互不相交的有限集合 T 1 ,T 2 ,......,T m ，且其中每一個集合本身又是一棵樹，稱之為根的子樹（ subtree ）。
（1） 結點的度(Degree)
樹中的一個結點擁有的子樹數稱為該結點的度(Degree)。
一棵樹的度是指該樹中結點的最大度數。
度為零的結點稱為葉子(Leaf)或終端結點。
度不為零的結點稱分支結點或非終端結點。
除根結點之外的分支結點統稱為內部結點。
根結點又稱為開始結點。
（2） 孩子(Child)和雙親(Parents)
樹中某個結點的子樹之根稱為該結點的孩子(Child)或兒子，相應地，該結點稱為孩子的雙親(Parents)或父親。
同一個雙親的孩子稱為兄弟(sibling)。
（3）祖先(Ancestor)和子孫(descendant)
①路徑（path）
若樹中存在一個結點序列k1，k2，…，ki，使得ki是ki+1的雙親(1≤i<j)，則稱該結點序列是從kl到kj的一條
路徑(Path)或道路。
路徑的長度指路徑所經過的邊(即連線兩個結點的線段)的數目，等於j-1。
注意：
若一個結點序列是路徑，則在樹的樹形圖表示中，該結點序列"自上而下"地通過路徑上的每條邊。
從樹的根結點到樹中其餘結點均存在一條惟一的路徑。
②祖先(Ancestor)和子孫(Descendant)
若樹中結點k到ks存在一條路徑，則稱k是ks的祖先(Ancestor)，ks是k的子孫(Descendant)。
一個結點的祖先是從根結點到該結點路徑上所經過的所有結點，而一個結點的子孫則是以該結點為根的
子樹中的所有結點。
約定：
結點k的祖先和子孫不包含結點k本身。
（4）結點的層數(Level)和樹的高度（Height）
結點的層數(Level)從根起算：
根的層數為1
其餘結點的層數等於其雙親結點的層數加1。
雙親在同一層的結點互為堂兄弟。
樹中結點的最大層數稱為樹的高度(Height)或深度(Depth)。
注意，
很多文獻中將樹根的層數定義為0。
（5）有序樹(OrderedTree)和無序樹(UnoderedTree)
若將樹中每個結點的各子樹看成是從左到右有次序的(即不能互換)，則稱該樹為有序樹(OrderedTree)；
否則稱為無序樹(UnoderedTree)。
注意：
若不特別指明，一般討論的樹都是有序樹。
（6）森林(Forest)
森林(Forest)是m(m≥0)棵互不相交的樹的集合。
樹和森林的概念相近。刪去一棵樹的根，就得到一個森林；反之，加上一個結點作樹根，森林就變為一
棵樹。
有序樹、無序樹
若將樹中每個結點的各子樹看成是從左到右有次序的(即不能互換)，則稱該樹為有序樹(OrderedTree)；
否則稱為無序樹(UnorderedTree)。
注意：若不特別指明，一般討論的樹都是有序樹。
樹中任意節點的子結點之間有順序關係，這種樹稱為有序樹
無序樹樹中任意節點的子結點之間沒有順序關係，這種樹稱為無序樹,也稱為自由樹，
