在這篇部落格中（https://blog.csdn.net/qq_33432841/article/details/108081027）已經講解了二叉樹的一些特點、性質、周遊順序等。在這篇部落格中，準備寫點二叉樹的分類的相關知識。
二叉樹分類主要包括：斜樹、滿二叉樹、完全二叉樹、二叉查找樹、平衡二叉樹等（還會更新哦！）
斜樹：
- 所有的結點都隻有左子樹的二叉樹叫左斜樹；
- 所有結點都是隻有右子樹的二叉樹叫右斜樹；
上面的左斜樹和右斜樹統稱為斜樹。
滿二叉樹：
在一棵二叉樹中。如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。
滿二叉樹必須滿足：
- 總的結點個數2^k-1個結點;
- 第i層的結點個數數為2^(k-1)個結點;
- 具有n個節點的滿二叉樹的深度為
【算法】二叉樹_分類
滿二叉樹的特點：
- 葉子隻能出現在最下一層。出現在其它層就不可能達成平衡。
- 非葉子結點的度一定是2。
- 在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子數最多。
完全二叉樹：
其和滿二叉樹不同的是最後一層不是滿的，除了最了一層，其餘的k-1層是一個滿二叉樹，最後一層的結點是從左開始排列的。（滿二叉樹是特殊的完全二叉樹，但完全二叉樹不一定是滿二叉樹）。
完全二叉樹必須滿足：
- 某個節點沒有左子節點，那麼肯定也不能有右子節點
- 從第1層到第k-1層是一個滿二叉樹，最後一層的結點從左開始排列。
完全二叉樹的特點：
- 葉子結點隻能出現在最下層和次下層。
- 最下層的葉子結點集中在樹的左部。
- 倒數第二層若存在葉子結點，一定在右部連續位置。
- 如果結點度為1，則該結點隻有左孩子，即沒有右子樹。
- 同樣結點數目的二叉樹，完全二叉樹深度最小。
備注：滿二叉樹一定是完全二叉樹，但反過來不一定成立。
二叉查找樹：
二叉查找樹（Binary Search Tree）（又：二叉搜尋樹，二叉排序樹）它或者是一棵空樹，或者是具有下列性質的二叉樹： 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 它的左、右子樹也分别為二叉排序樹。
二叉查找樹必須滿足：
- 所有子樹上面的左節點的值都比根結點要小，右節點的值都比根結點要大
- 任意結點的左右子樹也都是二叉查找樹
- 通過中序周遊，将得到的是一個有序的數列
對其操作的最優的時間複雜度為O(log2n)，相當于對數列進行二分查找法。最壞的時間複雜度為O(n)，相當于線性查找。
平衡二叉樹：
平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有别于AVL算法），它是二叉查找樹最優的情況。它很好的解決了二叉查找樹退化成連結清單的問題，把插入，查找，删除的時間複雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉會使插入和删除犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩定了很多。
在AVL樹中，任一節點對應的兩棵子樹的最大高度差為1，是以它也被稱為高度平衡樹。
這種左右子樹的高度相差不超過 1 的樹為平衡二叉樹。
平衡二叉樹具有以下性質：
- 它是一個二叉查找樹
- 它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
- 當删除、新增、修改節點上的值時，它會通過左旋或右旋的操作使二叉樹保持平衡。
- 最壞的時間複雜度為O(log2n)
在平衡二叉樹裡面有一個隐含的知識點：平衡因子
定義：某節點的左子樹與右子樹的高度(深度)差即為該節點的平衡因子（BF,Balance Factor），平衡二叉樹中不存在平衡因子大于 1 的節點。在一棵平衡二叉樹中，節點的平衡因子隻能取 0 、1 或者 -1 ，分别對應着左右子樹等高，左子樹比較高，右子樹比較高。
下面一篇部落格寫平衡二叉樹（ALV樹）的一些插入相關的知識點。
不後悔過去，不幻想未來，把握好現在，就是對自己最好的交代!!!!!!!!!!!!