層次遍歷過程

若二叉樹非空（假設其高度為h），則層次遍歷的過程如下：

① 訪問根結點（第1層）。

② 從左到右訪問第2層的所有結點。

層次遍歷演算法設計

在二叉樹層次遍歷中，對一層的結點訪問完後，再按照它們的訪問次序對各個結點的左、右孩子順序訪問，這樣一層一層進行，先訪問的結點其左、右孩子也要先訪問，這樣與佇列的先進先出特點吻合。因此層次遍歷演算法採用一個佇列qu來實現。

思路：先將根結點b進隊，在隊不空時迴圈：從佇列中出隊一個結點p，訪問它；若它有左孩子結點，將左孩子結點進隊；若它有左孩子結點，將左孩子結點進隊。如此操作直到隊空為止。

由先序/中序序列或後序/中序序列構造二叉樹

一棵所有結點值不同的二叉樹，其先序、中序、後序和層次遍歷都是唯一的，也就是說一棵這樣的二叉樹，不可以有兩種不同的先序遍歷序列，也不可能有兩種不同的中序序列。

二叉樹的構造就是給定某些遍歷序列，反過來唯一地確定該二叉樹。

從中看到，對於不同形態的二叉樹：

先序遍歷序列可能相同（圖中5棵二叉樹的先序遍歷序列均相同）。

中序遍歷序列可能相同。

後序遍歷序列可能相同（圖(b)～(e)的後序遍歷序列均相同）

先序遍歷序列和後序遍歷序列可能都相同（圖(d)和(e)的先序遍歷序列和後序遍歷序列均相同）。

實際上，對於含2個或者以上結點的二叉樹，在先序、中序和後序遍歷序列中：

由先序遍歷序列和中序遍歷序列能夠唯一確定一棵二叉樹。

由後序遍歷序列和中序遍歷序列能夠唯一確定一棵二叉樹。

由先序遍歷序列和後序遍歷序列不能唯一確定一棵二叉樹。

定理6.1 任何n（n≥0）個不同結點的二又樹，都可由它的中序序列b和先序序列a唯一地確定。

由a0（根結點）找到bk。

若bk前面有k個結點，則左子樹有k個結點，右子樹有n-k-1個結點。

可以求出左右子樹的中序序列和先序序列。

這樣根結點是確定的，左右子樹也是確定的，則該二叉樹是確定的。

已知先序序列為ABDGCEF，中序序列為DGBAECF，則構造二叉樹的過程：

定理6.2 任何n（n≥0）個不同結點的二叉樹，都可由它的中序序列和後序序列唯一地確定。

由an-1（根結點）找到bk。

若bk前面有k個結點，則左子樹有k個結點，右子樹有n-k-1個結點。

可以求出左右子樹的中序序列和後序序列。

這樣根結點是確定的，左右子樹也是確定的，則該二叉樹是確定的。

已知中序序列為DGBAECF，後序序列為GDBEFCA，則構造二叉樹的過程

由後序序列posts[i..i+n-1]和中序序列ins[j..j+n-1]建立二叉鏈t

若某非空二叉樹的先序序列和後序序列正好相同，則該二叉樹的形態是什麼？

二叉樹的先序序列是NLR，後序序列是LRN。

N L R = L R N

則L和R均為空。所以滿足條件的二叉樹只有一個根結點。

序列化和反序列化