0x01概述
什么是二叉樹？
二叉樹是 n (n >= 0)個結(jié)構(gòu)的有限集合,改集合或者為空集(稱為空二叉樹),或者有一個根節(jié)點和兩棵互不相交的旦袋、分別稱為根節(jié)點的左子樹和右子樹的二叉樹組成。
0x02 特殊的二叉樹
這里主要記錄一下特殊的二叉樹，滿二叉樹和完全二叉樹酗宋，比較典型。
- 滿二叉樹
-
什么是滿二叉樹疆拘？
在一棵二叉樹中,如果所有的分支節(jié)點都存在左子樹和右子樹,并且所有葉子都在同一層面上,這樣的二叉樹成為滿二叉樹蜕猫。
滿二叉樹的特點
(1) 滿二叉樹的葉子只能出現(xiàn)在最下一層,出現(xiàn)在其它層就不可能達(dá)成平衡。
(2) 非葉子節(jié)點的度一定是2哎迄。
(3) 在同樣深度的熱茶樹中,滿二叉樹的節(jié)點個數(shù)最多,葉子數(shù)最多回右。
- 完全二叉樹
-
什么是完全二叉樹？
對于一棵具有 n 個節(jié)點的二叉樹按層序編號,如果編號為 i ( 1<= i <= n)的節(jié)點與同樣深度的滿二叉樹中編號為 i 的節(jié)點在二叉樹中位置完全相同,則這棵二叉樹成為完全二叉樹漱挚。
完全二叉樹的特點
(1) 完全二叉樹的葉子節(jié)點只能出現(xiàn)在最下面的兩層.
(2) 最下層的葉子一定集中在左部的連續(xù)位置.
(3) 倒數(shù)二層,若有葉子節(jié)點,則一定在右部的連續(xù)位置/
(4) 如果結(jié)點度為1,則該結(jié)點只有有孩子,即不存在只有右子樹的情況.
(5) 同樣結(jié)點書的二叉樹,完全二叉樹的深度最小.
0x03 二叉樹的性質(zhì)
在二叉樹的第i層上有至多2**(i-1) (i>=1)個節(jié)點翔烁。
深度為K的二叉樹至多有2**K - 1個節(jié)點
對于任意一顆二叉樹布蔗，如果其葉子結(jié)點數(shù)為N0泄伪，度為2的節(jié)點數(shù)為N2，那么N2=N0+1
具有N個節(jié)點的完全二叉樹的深度為[log2(n)]+1 （[X]為不大于X的最大整數(shù)）
如果對一棵有 n 個結(jié)點的完全二叉樹(其深度為[log (2) n] + 1) 的結(jié)點按層序編號(從第1層到第[log (2) n] + 1 層,每一層從左到右),對任一結(jié)點i (1 <= i <= n) 有:
- 如果 i = 1 ,則結(jié)點i是二叉樹的根,無雙親;如果i > 1,則其雙親是結(jié)點 [ i /2 ];
- 如果2i > n,則結(jié)點i無左孩子(結(jié)點i為葉子結(jié)點);否則其左孩子是結(jié)點2i;
- 如果2i +1 > n,則結(jié)點i無右孩子;否則其右孩子是結(jié)點2i +1;
0x04 二叉樹的遍歷
二叉樹的遍歷常用的有前序遍歷卸留，中序遍歷白华，后序遍歷
- 前序遍歷
前序遍歷就是先訪問根節(jié)點慨默，然后遍歷左子樹，再遍歷右子樹弧腥；在遍歷左子樹的時候也先訪問根節(jié)點厦取，然后左子樹，然后右子樹鸟赫。蒜胖。消别。
- 中序遍歷
中序遍歷就是先訪問左子樹，再訪問根節(jié)點台谢，最后訪問右子樹寻狂。
- 后序遍歷
后序遍歷就是先訪問左子樹，再訪問右子樹朋沮，最后訪問根節(jié)點蛇券。
