實現二叉樹的各種遍歷方法

　　n個結點的二叉連結串列中含有空指標域。利用二叉連結串列中的空指標域，存放指向結點在某種遍歷次序下的前驅和後繼結點的指標，這種附加的指標稱為"線索"。加上線索的二叉連結串列稱為線索連結串列，相應的二叉樹稱為線索二叉樹。根據線索性質的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和後序線索二叉樹三種。

　　二叉樹的遍歷本質上是將一個複雜的非線性結構轉換為線性結構，使每個結點都有了唯一前驅和後繼，第一個結點無前驅，最後一個結點無後繼。對於二叉樹的一個結點，其前驅後繼只有在遍歷中得到。為了容易找到前驅和後繼，

　　二叉樹遍歷是指沿著某條搜尋路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴於具體的應用問 題。 遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。

　　除了先序遍歷、中序遍歷、後序遍歷外，還可以對二叉樹進行層序遍歷。設二叉樹的根節點所在層數為：層序遍歷就是從所在二叉樹的根節點出發，首先訪問第一層的樹根節點，然後從左到右訪問第2層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的過程就是層序遍歷。

　　層次遍歷應該沒有遞迴演算法遞迴實際就是一種深度優先的演算法而層次遍歷實際是廣度優先的遍歷演算法，所以遞迴不適用比如假設有遞迴演算法，現遍歷i層的開始，對i層第一個元素遍歷後需呼叫遞迴函式遍歷其孩子，遞迴呼叫完成後才繼續遍歷i層第二個元素，這樣就不是層次遍歷了。