這里還是用到棧的思想,為了方便用了c++的一些內容,把出棧,進棧,讀棧頂元素用一個個函數封裝起來了,前面做了一些處理來使用這些函數。
前序非遞歸
思想:一直走左邊,依次進棧。等左邊為空的時候,返回,也就是讀棧頂元素,讀一個出一個,并讓cur指向它的右邊,把它的右邊的結點當作根結點,再走一邊上面的過程。
中序非遞歸
前序是在訪問根結點時打印,中序是先訪問左結點,所以在指向左結點時打印,也就是一直往左走依次入棧,走到頭返回讀棧頂元素并出棧時打印就行,然后cur等于當前棧頂元素的右子樹,再把這個結點當根結點,再走一邊這樣的過程。
后序非遞歸
比較難想,要有一個指針last指向上一次操作完整遍歷完的樹的結點也就是這個結點是當前最底下的那個結點。
一直往左并入棧,走到頭把top指上去,如果top的右邊為空,打印并出棧,否則看右邊是不是last如果是也打印出棧,
否則沒有跑到右邊最后一個,(如果跑到了,肯定是打印出棧,最后一個就變了)。cur就等于當前棧頂元素的右子樹。