二叉樹
是啥就不用多說了吧芹关，续挟，，
但有一個(gè)性質(zhì)很重要:
記二叉樹中充边，度為0的結(jié)點(diǎn)數(shù)為n[0]庸推，度為1的結(jié)點(diǎn)數(shù)為n[1]，度為2的結(jié)點(diǎn)數(shù)為n[2]浇冰，那么總有n[0] = n[2] + 1
設(shè)該二叉樹總共有n個(gè)結(jié)點(diǎn)贬媒，結(jié)點(diǎn)等式為：n = n[0] + n[1] + n[2])
同時(shí)，該二叉樹總共會(huì)有n-1條邊肘习，其中度為2的結(jié)點(diǎn)延伸出兩條邊际乘，度為1的結(jié)點(diǎn)延伸出一條邊，度為0的結(jié)點(diǎn)不延伸漂佩，邊等式為：n -1 = 2*n[2] + 1*n[1] + 0*n[0]
結(jié)點(diǎn)等式和邊等式聯(lián)立可知 n[0] = n[2] + 1
滿二叉樹
滿二叉樹就是每一層都長(zhǎng)到爆滿的二叉樹脖含，如圖：
4層滿二叉樹.png
上面是一棵4層滿二叉樹
完全二叉樹
滿二叉樹 完全二叉樹 非完全二叉樹.png
完全二叉樹就是滿二叉樹按從右到左、從下到上的順序刪除若干葉子結(jié)點(diǎn)后形成的樹
也就是說投蝉，完全二叉樹的形態(tài)只有2種养葵。當(dāng)刪除偶數(shù)個(gè)葉子結(jié)點(diǎn)時(shí)，形成上圖第二棵樹那樣的完全二叉樹瘩缆；當(dāng)刪除奇數(shù)個(gè)葉子結(jié)點(diǎn)時(shí)关拒，形成上圖第三棵樹那樣的完全二叉樹
滿二叉樹和完全二叉樹的特性
實(shí)際上，滿二叉樹是特殊的完全二叉樹，因此完全二叉樹的特性更具有普適性着绊。我們由一般到特殊進(jìn)行研究谐算，由完全二叉樹到滿二叉樹這么個(gè)順序去看看
完全二叉樹幾個(gè)必須記住的重要特性
完全二叉樹.png
- 1.結(jié)點(diǎn)總數(shù)最多為2K-1，K為二叉樹的層數(shù)（高度）归露，當(dāng)且僅當(dāng)滿二叉樹時(shí)取等
- 2.第k層的結(jié)點(diǎn)數(shù)為2k-1（k<K）
- 3.每層最左邊的結(jié)點(diǎn)的編號(hào)永遠(yuǎn)是2k-1洲脂，如上圖完全二叉樹中的A，B剧包，D, H號(hào)節(jié)點(diǎn)恐锦。那么tips: 我們可以利用最后一層的排頭兵快速求解樹的高度
- 4.由3易得，結(jié)點(diǎn)數(shù)為n的完全二叉樹的高度是 [ log2 n ] + 1玄捕， [ log2 n ] 指第二層到最后一層的高度踩蔚，1指根結(jié)點(diǎn)所在的第一層
- 5.某結(jié)點(diǎn)的編號(hào)為i，則其左孩子編號(hào)為2*i枚粘，右孩子編號(hào)為2*i + 1
滿二叉樹自己的特點(diǎn)
- 結(jié)點(diǎn)總數(shù)為2K-1馅闽，K為滿二叉樹的層數(shù)（高度）
- 第k層的節(jié)點(diǎn)數(shù)為2k-1（k <= K）
訪問二叉樹的3種方式
前序遍歷DLR
def preOrder(Tree node):
if node == None:
return
visit(node.data)
preOrder(node.leftchild)
preOrder(node.rightchild)
中序遍歷LDR
def inOrder(Tree node):
if node == None:
return
preOrder(node.leftchild)
visit(node.data)
preOrder(node.rightchild)
后序遍歷LRD
def postOrder(Tree node):
if node == None:
return
preOrder(node.leftchild)
preOrder(node.rightchild)
visit(node.data)
