前言

二叉樹和鏈表在歷年春招筆試中，都是重點考核對象。鏈表由于算法簡單，一般考代碼實現(xiàn)能力。二叉樹考核遍歷。

二叉樹

二叉樹是樹形結(jié)構(gòu)中比較簡單的，它又可細(xì)分成完美二叉樹，斜二叉樹（相當(dāng)于鏈表），完全二叉樹。

二叉樹的幾個性質(zhì)

1. 第 i 層最大結(jié)點數(shù)為 2^(i-1)
2. 深度為 k 的二叉樹最大結(jié)點數(shù)為 2^k -1 (完美二叉樹)

二叉樹的遍歷

• 先序
• 中序
• 后序
• 層次遍歷

先序

從根節(jié)點->左子樹->右子樹

image.png

中序

先中序遍歷左子樹->根節(jié)點->中序遍歷右子樹

image.png

后序

先后序遍歷左子樹->再后序遍歷右 子樹->根節(jié)點

image.png

手寫

IMG_20180110_205719.jpg