樹（Tree）是若干個結點組成的有限集合，其中必須有一個結點是根結點，其余結點劃分為若干個互不相交的集合，每一個集合還是一棵樹，但被稱為根的子樹。注意，當樹的結點個數為0時，我們稱這棵樹為空樹，記為Φ ### 樹的術語 1. 結點：表示樹中的元素，包括數據項及若干指向其子樹的分支； 2. 結點的度：結點所擁有的子樹的個數稱為該結點的度； 3. 葉子結點：度為0的結點稱為葉子結點，或者稱為終端結點； 4. 分支結點：度不為0的結點稱為分支結點，或者稱為非終端結點；一棵樹的結點除葉子結點外，其余的都是分支結點； 5. 孩子、雙親、兄弟：若在樹中一個結點A的子樹的根結點是B，則稱B為A的孩子（也稱子結點），稱A為B的雙親（也稱父節點）；具有同一個雙親的子結點互稱為兄弟； 6. 路徑、路徑長度：如果一棵樹的一串結點n1,n2,…,nk有如下關系，即結點ni是ni+1的父結點（1≤i<k），就把n1,n2,…,nk稱為一條由n1至nk的路徑；這條路徑的長度是k-1； 7. 祖先、子孫：在樹中，如果有一條路徑從結點M到結點N，那么M就稱為N的祖先，而N稱為M的子孫； 8. 結點的層數：規定樹的根結點的層數為1，其余結點的層數等于它的雙親結點的層數加1； 9. 樹的深度：樹中所有結點的最大層數稱為樹的深度； 10. 樹的度：樹中各結點度的最大值稱為該樹的度； 11. 有序樹和無序樹：如果一棵樹中結點的各子樹從左到右是有次序的，即若交換了某結點各子樹的相對位置，則構成不同的樹，稱這棵樹為有序樹；反之，則稱為無序樹； 12. 森林：零棵或有限棵不相交的樹的集合稱為森林；自然界中樹和森林是不同的概念，但在數據結構中，樹和森林只有很小的差別；任何一棵樹，刪去根結點就變成了森林；