二叉樹遍歷的概念

二叉樹遍歷是指按照一定次序訪問二叉樹中所有結點，並且每個結點僅被訪問一次的過程。

設N為根結點，L、R分別為左、右子樹，這6種遍歷方法是NLR、LNR、LRN、NRL、RNL、RLN），若再規定先遍歷左子樹，後遍歷右子樹，則對於非空二叉樹，可得到如下3種遞迴的遍歷方法（即NLR、LNR和LRN）。

1）先序遍歷

① 訪問根結點。

② 先序遍歷左子樹。

2）中序遍歷

① 中序遍歷左子樹。

② 訪問根結點。

3）後序遍歷

① 後序遍歷左子樹。

② 後序遍歷右子樹。

先序、中序和後序遍歷遞迴演算法

1）先序遍歷的遞迴演算法

2）中序遍歷的遞迴演算法

3）後序遍歷的遞迴演算法

遞迴遍歷演算法的應用

假設二叉樹採用二叉鏈儲存結構儲存，設計一個演算法求一棵給定二叉樹中的結點個數。

解：求一棵二叉樹中的結點個數是以遍歷演算法為基礎的，任何一種遍歷演算法都可以出一棵二叉樹中的結點個數。

也可以從遞迴演算法設計的角度來求解。設f(b)求二叉樹b中所有結點個數，它是"大問題"，f(b.lchild)和f(b.rchild)分別求左、右子樹的結點個數。

假設二叉樹採用二叉鏈儲存結構儲存，設計一個演算法按從左到右輸出一棵二叉樹中所有葉子結點值。

解：由於先序、中序和後序遞迴遍歷演算法都是按從左到右的順序訪問葉子結點的，所以本題可以基於這三種遞迴遍歷演算法求解。

也可以直接採用遞迴演算法設計方法求解。

設f(b)的功能是從左到右輸出以b為根結點的二叉樹的所有葉子結點值，為"大問題"，顯然f(b.lchild)和f(b.rchild)是兩個"小問題"。

當b不是葉子結點時，先呼叫f(b.lchild)再呼叫f(b.rchild)。

對應的遞迴模型f(b)如下：

從上述兩例看出，基於遞迴遍歷思路和直接採用遞迴演算法設計方法完全相同。實際上，當求解問題較複雜時，直接採用遞迴演算法設計方法更加簡單方便。

僅從遞迴遍歷角度看，上述兩例基於3種遞迴遍歷思路中任意一種都是可行的，但有些情況並非如此。

一般地，二叉樹由根、左右子樹3部分構成，但可以看成兩類，即根和子樹。

如果需要先處理根再處理子樹，可以採用先序遍歷思路。

如果需要先處理子樹，再處理根，可以採用後序遍歷思路。

假設二叉樹採用二叉鏈儲存結構儲存，設計一個演算法將二叉樹bt1複製到二叉樹bt2。

解：採用直接遞迴演算法設計方法。設f(t1，t2)是由二叉鏈t1複製產生t2，這是"大問題"。

也可以採用基於後序遍歷思路

假設一棵二叉樹採用二叉鏈儲存結構，且所有結點值均不相同，設計一個演算法求二叉樹中指定結點值的結點所在的層次（根結點的層次計為1）

解:

二叉樹中每個結點都有一個相對於根結點的層次，根結點的層次為1，那麼如何指定這種情況呢？

可以採用遞迴演算法引數賦初值的方法，即設f(b，x，h)為"大問題"，增加第3個引數h表示第一個引數b指向結點的層次，在初始呼叫時b指向根結點，h對應的實參為1，從而指定了根結點的層次為1的情況。

遞迴演算法引數賦初值問題

假設二叉樹採用二叉鏈儲存結構，且所有結點值均不相同，設計一個演算法輸出值為x的結點的所有祖先。

解法1

根據二叉樹中祖先的定義可知，若一個結點的左孩子或右孩子值為x時，則該結點是x結點的祖先結點；若一個結點的左孩子或右孩子為x結點的祖先結點時，則該結點也為x結點的祖先結點。

設f(t，x)表示t結點是否為x結點的祖先結點。

解法2

二叉樹中x結點的祖先恰好是根結點到x結點的路徑上除了x結點外的所有結點，用全域性變數res列表表示。

改進演算法2：

改為用path[0..d]存放根到x結點的路徑