遍歷(非遞歸)

• 先序遍歷算法

1. 首先申請一個新的棧，記為stack；
2. 然后將頭結(jié)點head壓入棧stack中；
3. 每次從stack中彈出棧頂節(jié)點，記為cur，然后打印cur節(jié)點的值。如果cur右孩子不為空的話，將cur的右孩子壓入stack中。最后如果cur的左孩子不為空的話，將cur的左孩子壓入stack中。
4. 不斷重復(fù)步驟3，直到stack為空，全部過程結(jié)束。

• 中序遍歷算法

1. 申請一個新的棧，記為stack，申請一個變量cur，初始時令cur等于頭結(jié)點；
2. 先把cur節(jié)點壓入棧中，對以cur節(jié)點為頭的整顆子樹來說，依次把整顆樹的左邊界壓入棧中，即不斷令cur==cur.left，然后重復(fù)步驟2；
3. 不斷重復(fù)步驟2，直到發(fā)現(xiàn)cur為空，此時從stack中彈出一個節(jié)點，記為node。打印node的值，并讓cur==node.right，然后繼續(xù)重復(fù)步驟2；
4. 當stack為空并且cur為空時，整個過程結(jié)束。

• 后序遍歷算法

方法一：使用兩個棧實現(xiàn)

1. 申請一個棧，記為s1，然后將頭節(jié)點壓入s1中；
2. 從s1中彈出的節(jié)點記為cur，然后先把cur的左孩子壓入s1中，然后把cur1的右孩子壓入s1中；
3. 在整個過程中，每一個從s1中彈出的節(jié)點都放進第二個棧s2中；
4. 不斷重復(fù)步驟2和步驟3，直到s1為空，過程停止。
5. 從s2中依次彈出節(jié)點并打印，打印的順序就是后續(xù)遍歷的順序了。

方法二：使用一個棧實現(xiàn)

1. 申請一個棧，記為stack，將頭節(jié)點壓入stack，同時設(shè)置兩個變量h和c。在整個流程中，h代表最近一次彈出并打印的節(jié)點，c代表當前stack的棧頂節(jié)點，初始時令h為頭節(jié)點，c為NULL；
2. 每次令c等于當前stack的棧頂節(jié)點，但是不從stack中彈出節(jié)點，此時分以下三種情況：
   (1)如果c的左孩子不為空，并且h不等于c的左孩子，也不等于c的右孩子，則把c的左孩子壓入stack中；
   (2)如果情況1不成立，并且c的右孩子不為空，并且h不等于c的右孩子，則把c的右孩子壓入stack中；
   (3)如果情況1和情況2都不成立，那么從stack中彈出c并打印，然后令h等于c。
3. 一直重復(fù)步驟2，直到stack為空，過程停止。