一、樹

遍歷是指對樹中所有結(jié)點(diǎn)信息的訪問，即依次對樹中每個(gè)結(jié)點(diǎn)訪問依次且僅訪問一次。

1.前序遍歷

也叫先根遍歷，按照先根后子的順序遍歷，字節(jié)點(diǎn)從左到右的順序遞歸遍歷。

2.后序遍歷

也叫后根遍歷，字節(jié)點(diǎn)從左到右的順序遞歸遍歷，最后訪問根，遞歸遍歷。

3.層次遍歷

從上到下，從左到右的順序遍歷。

注意：二叉樹才有中序遍歷！

二、二叉樹

①二叉樹結(jié)點(diǎn)最大度為2，而樹不限制結(jié)點(diǎn)的度。

②二叉樹的結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹。

二叉樹性質(zhì)

二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為2的i-1次方（i>=2）

深度為k的二叉樹至多有2的k次方-1個(gè)結(jié)點(diǎn)（k>=1）

在任意一棵二叉樹中，若終端結(jié)點(diǎn)樹為n0，度為2的結(jié)點(diǎn)樹為n2，則n0=n2+1

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n的下限+1

二叉樹遍歷：

①前序遍歷

②中序遍歷

? ? 先訪問左子樹，再訪問根，最后訪問右子樹

③后序遍歷