二叉樹的概念
二叉樹在實踐中用的很多。
一棵二叉樹是結點的一個有限集合，該集合：
- 或者為空；
- 由一個根結點加上兩棵別稱為左子樹和右子樹的二叉樹組成。
- 二叉樹最多兩個孩子。
這里注意：二叉樹并不是度為2的樹。
二叉樹的度最大值是2，并不是說它的度一定為2。所以一下這四種情況也均是二叉樹：
- 空樹
- 只有根節點
- 只有左子樹
- 只有右子樹
- 左右子樹均存在
二叉樹不存在度大于2的節點；
二叉樹的子樹有左右之分，次序是不能顛倒的，因此二叉樹是有序樹。
二叉樹通俗也可以理解為對樹進行了“計劃生育”。?“計劃生育”也就是生兩個小孩，但是是每一家來說都是生兩個嗎？
那么度為2的一定是二叉樹嗎？
- 度為2一定是二叉樹。度為2的話，那么所有節點的最大的度就是2，而二叉樹的概念是不存在度大于2的節點。
- 二叉樹是一個特殊的樹，它的度最大為2，但是并沒有說一定為2。
特殊的二叉樹
滿二叉樹
一個二叉樹，如果每一個層的結點數都達到最大值，那么這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的成熟為K，那么結點總數就是，那么它就是滿二叉樹。
根據上圖：
- 假設高度為h，那么就會有
的節點；
- 那么假設樹有N個節點的話，那就是?
；那么 高度就為
。
完全二叉樹
完全二叉樹，前h-1層都是滿的，最后一層不一定滿，但是從左到右必須連續。
完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深入為K的，有n個節點的二叉樹，當且僅當其每一個節點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。
這里注意二叉樹順序是固定的，必須是連續的。
假設完全二叉樹的高度為h，那么它的結點數量是多少呢？
完全二叉樹的最后一層的范圍：?
思路：
- 這里我們想在滿二叉樹中，結點數為
- 那么滿二叉樹中的上一層就是有
；
- 因為完全二叉樹就是滿二叉樹的基礎上，最后一層不滿，也就是最后一層的結點數最多有
，最少有1個；
- 所以根據等比公式可以求得出完全二叉樹最后一層的范圍為：?
。
