線索二叉樹的遍歷

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

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

　　遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。

　　二叉樹有三種遍歷方法，先序遍歷，首先訪問根，再先序遍歷左子樹，最後先序遍歷右子樹。中序遍歷，首先中序遍歷左子樹，再訪問根，最後遍歷右子樹。後序遍歷，首先後序遍歷左子樹，再後序遍歷右子樹，最後訪問根。

　　後序遍歷是二叉樹遍歷的一種，也叫做後根遍歷、後序周遊，可記做左右根。後序遍歷有遞迴演算法和非遞迴演算法兩種。在二叉樹中，先左後右再根。巧記：左右根。序遍歷的非遞迴演算法是三種順序中最複雜的，原因在於，後序遍歷是先訪問左、右子樹,再訪問根節點，而在非遞迴演算法中，利用棧回退到時，並不知道是從左子樹回退到根節點，還是從右子樹回退到根節點，如果從左子樹回退到根節點，此時就應該去訪問右子樹，而如果從右子樹回退到根節點，此時就應該訪問根節點。所以相比前序和後序，必須得在壓棧時新增資訊，以便在退棧時可以知道是從左子樹返