樹是n(n>=0)個節點的有限集合。當n=0時稱為空樹，當n>0 為非空樹，任何非空樹中，有且僅有一個根節點；其餘節點可分為m(m>=0)個互不相交的有限集合T1、T2 等，其中每一個集合都可以稱為一棵樹，稱為根節點的子樹。
雙親孩子、兄弟：節點的字數的根稱為該節點的孩子，該節點稱為其子節點的雙親。具有相同雙親的節點互為兄弟節點。如圖：A是根節點，B、C、D互為兄弟；B是E、F的父節點（雙親）；E、F 互為兄弟節點。
節點的度：一個節點下的子節點個數稱為節點的度。比如 A的度為3，D的度為1。
葉子節點：是指度為0的節點，也被稱為終端節點。比如 C、E、F、G都是葉子節點。
內部節點：度不為零的節點稱為分支節點或非終端節點。去掉根節點，分支節點稱為內部節點。比如：B、D。
節點的層次：根節點A屬於第一層，依次類推。B屬於第二層，E屬於第三層。
樹的高度：一棵樹的最大層次數稱為樹的高度或者樹的深度。
有序（無序）樹：樹中的節點的各個子樹看成是從左到右有次序的，即不能交換，則稱為有序樹，否則為無序樹。二叉樹是n(n>=0)個節點的有限集合，它或者是空樹（n=0），或者是由一個根節點及兩棵不相交的、分別稱為左子樹、右子樹的二叉樹所組成。二叉樹中節點區分左子樹、右子樹，即便只有一個子樹的情況下也有標明是左子樹還是右子樹，普通樹則不區分；二叉樹中節點最大度為2，普通樹則沒有限制節點的度數。3、對任何一棵二叉樹，若其終端節點數為n,度為2的節點數為n2，則n=n2+14、具有n個節點的完全二叉樹的深度為(log2^n)+11、滿二叉樹：深度為k的二叉樹有2^(k-1)個節點,是滿二叉樹2、完全二叉樹:高度為k的二叉樹，除了第k層都是滿的，稱為完全二叉樹。滿二叉樹也是完全二叉樹。具有n個節點的完全二叉樹高度為 (log2^n) +13、非完全二叉樹：不滿足完全二叉樹的稱為非完全二叉樹。用一組地址連續的存儲單元存儲二叉樹的節點，必須把節點排成一個適當的線性序列，並且節點在這個序列中的相互位置可以反映出節點之間的邏輯關係順序存儲適合對完全二叉樹的存儲方式，既簡單又節省空間。對於一般二叉樹而言，因為在順序存儲結構中，以節點在存儲單元中的位置來表示節點之間的關係，所以存儲方式也必須按照完全二叉樹的方式存儲，這樣會造成空間上的浪費。最壞的情況，一個深度為h且只有h個節點的二叉樹（也是單枝樹）需要(2^h) -1 存儲單元.由於二叉樹中節點包含數據、左子樹根、右子樹根、雙親信息，因此可以用三叉鍊表或二叉鍊表來 存儲二叉樹，鍊表的頭指針指向二叉樹的根節點。遍歷是按某種策略訪問樹中的每個節點，僅訪問一次。對於含有n個節點的二叉樹遍歷算法的時間複雜度都是O(n).節點的路徑：從樹的一個節點到另一個節點之前的通路。節點的帶權路徑：節點到樹根之間的路徑長度*該節點的權重值。樹的帶權路徑長度為樹種所有葉子節點的帶權路徑長度之和。數值最小的就是哈夫曼樹。
IT技術分享社區
個人博客網站：https://programmerblog.xyz
Long-press QR code to transfer me a reward
As required by Apple's new policy, the Reward feature has been disabled on Weixin for iOS. You can still reward an Official Account by transferring money via QR code.