溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
前言
三種遍歷的遞歸寫法都很好寫，所以總結一下非遞歸寫法。
先貼一張圖復習一下三種遍歷方式就進入正文啦~
【注：本文所有代碼實現中樹的結點定義如下：
public class Node {
int val;
Node left;
Node right;
Node parent;
Node() {}
Node(int val) {
this.val = val;
}
}
1.前序遍歷
實現思路：
前序遍歷的順序是：根結點 -> 左孩子 -> 右孩子
借助一個棧結構先將根結點壓入棧，然后循環每次取出棧頂元素，直到棧為空。如果當前結點有右孩子就先將右孩子壓入棧中，如果當前結點有左孩子就將左孩子壓入棧中，這里注意順序，因為棧的結構是先進后出的，為了保證先遍歷到左孩子就應該后壓左孩子~
代碼實現：
【代碼使用直接輸出的方式打印中序遍歷結果，也可以放入一個list中存儲~】
public void preOrder(Node head) {
System.out.println("pre-order:");
if(head != null) {
Stack<Node> stack = new Stack<>();
stack.push(head);
while(!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.val + " ");
if (head.right != null)
stack.push(head.right);
if (head.left != null)
stack.push(head.left);
}
}
}
2.中序遍歷
實現思路：
中序遍歷的順序：左孩子 -> 根結點 -> 右孩子
借助棧結構，將當前結點的左孩子依次入棧直到沒有左孩子了就彈出棧頂元素并打印，如果彈出的結點有右孩子就將右孩子的左邊界依次入棧，循環…
比如文章開始的那個圖中，先將A，B，D依次入棧，此時棧頂元素是D，彈出并打印，D結點有右孩子，將D的右孩子的左邊界依次入棧，壓入結點G，結點G沒有左孩子所以彈出并打印G，此時棧頂元素是B，循環…直到棧中為空且當前結點為空時遍歷結束。
代碼實現：
public static void inOrderTraverse(Node head) {
System.out.println("in-order:");
if(head != null) {
Stack<Node> stack = new Stack<>();
while(!stack.isEmpty() || head != null) {
if(head != null) {
// 當前節點不為空, 將自己壓進棧并將自己的左孩子作為當前節點（壓入左邊界）
stack.push(head);
head = head.left;
}else {
// 當前節點為空（沒有左孩子了）, 將棧頂元素彈出作為當前節點, 并將當前節點的右孩子壓進棧
head = stack.pop();
System.out.print(head.val + " ");
head = head.right;
}
}
}
}
3.后序遍歷
實現思路：
后序遍歷的順序：左孩子 -> 右孩子 -> 根結點
仔細想一下，打印每個結點需要訪問根結點三次，先從根結點開始找到左孩子，返回再找到右孩子，再返回到根結點，需要訪問根結點三次，直接按照當前順序進行遍歷不知如何下手，那么我們可以換一個角度去考慮。
棧結構是先進后出的，那我們不妨借助一個棧先存儲 根結點 -> 右孩子 -> 左孩子 的結果，再將其依次彈出就是后序遍歷的順序了。
那實現 根結點 -> 右孩子 -> 左孩子 的方法就很簡單了，回憶一下剛才說的前序遍歷的方式，前序遍歷是先要左孩子，就后壓入左孩子，反之，將前序遍歷的邏輯改寫為：彈出每個棧頂結點作為當前結點并存儲到一個輔助棧中，如果當前結點有左孩子就先壓入左孩子，如果有右孩子就后壓入右孩子，每次取棧頂彈出到輔助棧中。最后將得到的輔助棧中元素依次彈出得到的就是后序遍歷的結果。
代碼實現：
public static void posOrderTraverse(Node head) {
System.out.println("pos-order");
if(head != null) {
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>(); // 輔助棧，存儲 根 -> 右 -> 左 的結果
stack1.push(head);
while(!stack1.isEmpty()) {
head = stack1.pop();
stack2.push(head);
// 有左孩子就先壓入左孩子
if(head.left != null)
stack1.push(head.left);
// 有右孩子就后壓入右孩子
if(head.right != null)
stack1.push(head.right);
}
// 逆序打印 根 -> 右 -> 左 的結果，就是后序遍歷的結果
while(!stack2.isEmpty())
System.out.print(stack2.pop().val + " ");
}
}
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對億速云的支持。如果你想了解更多相關內容請查看下面相關鏈接
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
