樹
非線性結構，每個元素可有多個前驅和后繼
樹是n（n>=0）個元素的集合，n=0時，稱為空樹，樹只有一個特殊的沒有前驅的元素，稱為樹的根root，樹中除了根結點外，其余元素只能有一個前驅，可以有零個和多個后繼，子樹也有自己的根
結點：樹中的數據元素
結點的度degree：結點擁有的子樹的數目稱為度，記作d（v）。樹的度是樹內各結點的度最大值
葉子結點：結點的度為零
分支結點：結點的度不為0
內部結點：除根結點外的分支結點，當然也不包括葉子結點
孩子結點：結點的子樹的根結點稱為該結點的孩子
雙親結點：一個結點是它各子樹的根結點的雙親
兄弟結點：具有相同雙親結點的結點
祖先結點：從根結點到該結點所經分支上所有的結點，A,B,D,都是G的祖先結點
結點的層次（level）：根結點為第一層，根的孩子結點為第二層，依次類推，記作l（v）
樹的深度（高度depth）：樹的層次的最大值，上圖的樹深度為4
堂兄弟：雙親在同一層的結點
樹分為有序樹和無序樹，有序樹有順序，不能交換，無序樹沒有順序，不能發生交換
路徑：樹中的k個結點n1，n2…nk,滿足ni是n（i+1）的雙親，稱為n1到nk的一條路徑，就是一條線串下來，前一個都是后一個的（前驅）結點
路徑長度=路徑上的結點數-1，也是分支數
森林：m（m>=0）棵不相交的數的集合，對結點而言，其子樹的集合可就是森林
二叉樹
二叉樹：每個結點最多2棵子樹，有序樹，左右子樹不能交換次序，即使某個結點只有一棵樹，也要確定他是左子樹還是右子樹
左斜樹，所有結點都只有左子樹，右子樹，所有結點都只有右子樹
滿二叉樹
一棵二叉樹的所有分支結點都存在左子樹和右子樹，且所有葉子結點只存在最下面一層，同樣深度的二叉樹中，滿二叉樹結點最多，k為深度，則結點總數為2**k-1
完全二叉樹
若二叉樹的深度為k，二叉樹的層數從1到k-1層的結點數都達到了最大數，在第k層的所有結點都集中在最左邊，就是完全二叉樹，k為深度，則結點的最大值為2**k-1，當達到最大值的時候就是滿二叉樹
二叉樹性質：
在二叉樹的第i層上至多有2**（i-1）個結點
深度為k的二叉樹，至多有2**k-1個結點
對任何一棵二叉樹T，如果其終端結點數為n0，度數為2的結點為n2，則有n0=n2+1，換句話說就是，葉子結點數-1=度數為2的結點數
高度為k的二叉樹，至少有k個結點
含有n個結點的二叉樹高度至多為n，最小為math.ceil（log2（n+1））
具有n個結點的完全二叉樹的深度為int（log2n）+1或者math.ceil(log2（n+1）)
本文來自投稿，不代表Linux運維部落立場，如若轉載，請注明出處：http://www.www58058.com/96308
