解題時(shí)的二叉樹分類：滿二叉樹和完全二叉樹。

滿二叉樹：只有度為0和度為2的結(jié)點(diǎn)，且所有度為零的結(jié)點(diǎn)都在二叉樹的同一層。而對(duì)于深度為k的滿二叉樹，其結(jié)點(diǎn)個(gè)數(shù)為2^k-1。

完全二叉樹：只有最底層可能沒有被填滿，其余每層的結(jié)點(diǎn)數(shù)都達(dá)到了最大值，而最底層(第k層)可能包含的結(jié)點(diǎn)數(shù)為1-2^(k-1)。而完全二叉樹中最底層的結(jié)點(diǎn)必須是從左到右添加的，若最底層的葉子節(jié)點(diǎn)的位置中，某個(gè)位置沒有結(jié)點(diǎn)，而該位置的右側(cè)仍然有葉子節(jié)點(diǎn)，則表明該樹不是完全二叉樹。

二叉搜索樹：二叉搜索樹中的每個(gè)結(jié)點(diǎn)都是有數(shù)值的，所以二叉搜索樹是一個(gè)有序樹。

根節(jié)點(diǎn)的左子樹上的結(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值。而這個(gè)原則在二叉搜索樹的左右子樹上仍然遞歸成立。

平衡二叉搜索樹(AVL)：它是一個(gè)空樹或其左右兩個(gè)子樹的高度差的絕對(duì)值小于等于1。且其左右子樹也遞歸滿足這一要求。

二叉樹的存儲(chǔ)方式：既可以通過鏈?zhǔn)酱鎯?chǔ)(指針)實(shí)現(xiàn)，也可以通過順序存儲(chǔ)(數(shù)組)實(shí)現(xiàn)。使用順序存儲(chǔ)實(shí)現(xiàn)時(shí)，若父節(jié)點(diǎn)的下標(biāo)為i，則其左孩子結(jié)點(diǎn)的下標(biāo)為2*i+1，其右孩子節(jié)點(diǎn)的下標(biāo)為2*i+2。而鏈?zhǔn)酱鎯?chǔ)二叉樹是更常見的方法。

二叉樹的遍歷方式：二叉樹的遍歷方式包括：深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種。而前序中序后序遍歷屬于深度優(yōu)先遍歷，層序遍歷屬于廣度優(yōu)先遍歷。前序中序后序遍歷的區(qū)別在于，遍歷時(shí)中間結(jié)點(diǎn)相對(duì)于其左右孩子節(jié)點(diǎn)的位置。中左右為前序遍歷，左中右為中序遍歷，左右中為后序遍歷。

二叉樹的遞歸遍歷：

在寫遞歸算法時(shí)需要注意的三要素：①確定遞歸參數(shù)和返回值，②確定終止條件，③確定單層遞歸的邏輯。

二叉樹的迭代遍歷：利用了棧對(duì)二叉樹進(jìn)行遍歷。