二叉樹定義

二叉樹（Binary Tree）是 n（n >= 0）個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的、分別
稱為根結點的左子樹和右子樹的二叉樹組成。

二叉樹的特點：

• 每個結點最多有兩棵子樹
• 左子樹和右子樹有順序
• 樹中某個結點只有一棵子樹，也要區(qū)分是左子樹還是右子樹。樹1和樹2是同一棵樹，但它們卻是不同的二叉樹。

[圖片上傳失敗...(image-20814c-1652521949356)]

二叉樹的五種基本形態(tài)：

• 空二叉樹
• 只有一個根結點
• 根結點只有左子樹
• 根結點只有右子樹
• 根結點既有左子樹又有右子樹

特殊二叉樹

1.斜樹

所有的結點都只有左子樹的二叉樹叫左斜樹。所有結點都是只有右子樹的二叉樹叫右斜樹。統(tǒng)稱斜樹。

線性表結構可以理解為是樹的一種極其特殊的表現(xiàn)形式。（斜樹）

2.滿二叉樹

在一棵二叉樹中，所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。

滿二叉樹特點：

• 葉子只能出現(xiàn)在最下一層
• 非葉子結點的度一定是2
• 同樣深度的二叉樹中，滿二叉樹的結點個數(shù)最多，葉子數(shù)最多。

完全二叉樹

對一棵具有n個結點的二叉樹按層序編號，如果編號為i（1 <= i <= n）的結點與==同樣深度的滿二叉樹==中編號為i的結點在二叉樹中位置
完全相同，則這棵二叉樹稱為完全二叉樹。

==滿二叉樹一定是一棵完全二叉樹，但完全二叉樹不一定是滿二叉樹。==

完全二叉樹如下圖：
[圖片上傳失敗...(image-583a7a-1652521949356)]

非完全二叉樹如下圖：
[圖片上傳失敗...(image-7313b4-1652521949356)]

完全二叉樹特點：

• 葉子結點只能出現(xiàn)在最下兩層。
• 最下層的葉子一定集中在左部連續(xù)位置。
• 倒數(shù)第二層，如果有葉子結點，一定在右部連續(xù)位置。
• 如果結點度為1，則該結點只有左孩子，即不存在只有右子樹的情況。
• 同樣結點數(shù)的二叉樹，完全二叉樹的深度最小。

二叉樹性質

1. 在二叉樹的==第i層==上至多有2^(i-1)個結點（i>=1）
2. 深度為k的二叉樹至多有2^k - 1個結點（深度為k意思就是有k層的二叉樹）
3. ==對任何一棵二叉樹T，如果終端結點數(shù)為n0，度為2的結點數(shù)為n2，則n0 = n2 + 1==
4. 具有n個結點的完全二叉樹的最大深度為log2 n + 1 （取最大整數(shù)） （==這里有個疑問？是不是log2(2n+1)？==）