術(shù)語
- 節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度驼壶；
- 葉節(jié)點或終端節(jié)點：度為零的節(jié)點氏豌；
- 非終端節(jié)點或分支節(jié)點：度不為零的節(jié)點；
- 父親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點热凹，則這個節(jié)點稱為其子節(jié)點的父節(jié)點泵喘；
- 兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點；
- 節(jié)點的層次：從根開始定義起般妙，根為第1層纪铺，根的子節(jié)點為第2層，以此類推碟渺；
- 樹的高度或深度：樹中節(jié)點的最大層次鲜锚；
- 堂兄弟節(jié)點：父節(jié)點在同一層的節(jié)點互為堂兄弟；
- 節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點苫拍；
- 孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫芜繁。
- 森林：由m（m>=0）棵互不相交的樹的集合稱為森林；
- 滿二叉樹：一棵深度為k绒极，且有2^k-1 (2的k次方減一)個節(jié)點稱之為滿二叉樹
- 完全二叉樹：完全二叉樹是由滿二叉樹而引出來的骏令。對于深度為K的，有n個結(jié)點的二叉樹垄提，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹榔袋。葉節(jié)點只能出現(xiàn)在最下層和次下層，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置的二叉樹
二叉樹的性質(zhì)
- 在非空二叉樹中铡俐，第i層的結(jié)點總數(shù)不超過2^(i-1),i>=1摘昌；
- 深度為h的二叉樹最多有2^h-1個結(jié)點(h>=1)，最少有h個結(jié)點高蜂；
- 對于任意一棵二叉樹聪黎，如果其葉結(jié)點數(shù)為N0，而度數(shù)為2的結(jié)點總數(shù)為N2，則N0=N2+1稿饰；
- 具有n個結(jié)點的完全二叉樹的深度為K =[log2n」+1(取下整數(shù))
- 有N個結(jié)點的完全二叉樹各結(jié)點如果用順序方式存儲锦秒，則結(jié)點之間有如下關(guān)系： 若I為結(jié)點編號則 如果I>1，則其父結(jié)點的編號為I/2喉镰；
- 完全二叉樹旅择，如果2I<=N，則其左兒子（即左子樹的根結(jié)點）的編號為2I侣姆；若2I>N生真，則無左兒子； 如果2I+1<=N捺宗，則其右兒子的結(jié)點編號為2I+1柱蟀；若2I+1>N，則無右兒子蚜厉。
- 給定N個節(jié)點长已，能構(gòu)成h(N)種不同的二叉樹。h(N)為卡特蘭數(shù)的第N項昼牛。h(n)=C(2*n术瓮，n)/(n+1)。
- 設(shè)有i個枝點贰健，I為所有枝點的道路長度總和胞四，J為葉的道路長度總和J=I+2i
二叉樹的遍歷三種方式，如下：
（1）前序遍歷（DLR）伶椿，首先訪問根結(jié)點撬讽，然后遍歷左子樹，最后遍歷右子樹悬垃。簡記根-左-右游昼。
（2）中序遍歷（LDR），首先遍歷左子樹尝蠕，然后訪問根結(jié)點烘豌，最后遍歷右子樹。簡記左-根-右看彼。
（3）后序遍歷（LRD）廊佩，首先遍歷左子樹，然后遍歷右子樹靖榕，最后訪問根結(jié)點标锄。簡記左-右-根。
