二叉樹的理論基礎

二叉樹的種類

滿二叉樹：如果一棵樹只有度(表示節(jié)點擁有的子節(jié)點數(shù))為0的結(jié)點和度為2的節(jié)點，并且度為0的節(jié)點在同一層上

完全二叉樹：在完全二叉樹中，除了底層節(jié)點可能沒有填滿外，其余每層節(jié)點數(shù)都達到最大值，并且最下面一層的節(jié)點都集中在該層最左邊的若干位置。若底層為第h層（h從1開始），則該層包含1~2^（h-1）個節(jié)點。

二叉搜索樹：它是一個有序數(shù)。

若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值。left.val < root.val

若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根節(jié)點的值。right.val > root.val

它的左、右子樹也分別為二叉排序樹

二叉樹的存儲方式

鏈式存儲使用指針，順序存儲使用數(shù)組

用數(shù)組存儲如何遍歷：

若父節(jié)點的數(shù)組下標是i,那么左孩子是 i*2+1,右孩子是1*2+2

二叉樹的遍歷方式

深度優(yōu)先遍歷

前中后指的是中間節(jié)點的位置

前序遍歷（遞歸法，迭代法）：

中序遍歷（遞歸法，迭代法）

后序遍歷（遞歸法，迭代法）

廣度優(yōu)先遍歷

層序遍歷（迭代法）一般使用隊列來實現(xiàn)

二叉樹的定義

二叉樹的定義和鏈表差不多，相對于鏈表，二叉樹的節(jié)點里多了一個指針，其有兩個指針，指向左右孩子。

二叉樹的遞歸遍歷

遞歸三要素：

1.確定遞歸函數(shù)的參數(shù)和返回值

2.確定終止條件

3.確定單層遞歸的邏輯

二叉樹的前序遍歷

遞歸遍歷

迭代遍歷

統(tǒng)一迭代

二叉樹的后序遍歷

遞歸遍歷

前序遍歷是中左右，后序遍歷是左右中，把后序遍歷反轉(zhuǎn)一下，你發(fā)現(xiàn)是中右左，因此我們自遍歷的時候按照前序遍歷的那樣，只不過先要將左孩子放入，再放右孩子，最終返回結(jié)果的時候直接反轉(zhuǎn)

迭代遍歷

統(tǒng)一迭代

二叉樹的中序遍歷

遞歸遍歷

迭代遍歷

統(tǒng)一迭代