您好,登錄后才能下訂單哦!
這篇文章主要介紹了java棧如何實現(xiàn)二叉樹的非遞歸遍歷,具有一定借鑒價值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
class Node{ public int val; public Node left; public Node right; public Node(int v) { val=v; left=null; right=null; } } public class Main { public static void main(String[] args) { Node head =new Node(0); Node node1=new Node(1); Node node2=new Node(2); Node node3=new Node(3); Node node4=new Node(4); Node node5=new Node(5); Node node6=new Node(6); head.left=node1; head.right=node2; node1.left=node3; node1.right=node4; node2.left=node5; node2.right=node6; pos2(head); pos1(head); in(head); }
思想和流程
彈出就打印
如果有右子樹,就壓入
如果有左子樹,就壓入
public static void pos1(Node h) { System.out.print("先序遍歷 "); if(h!=null) { Stack<Node>stack =new Stack<Node>(); stack.push(h); while(!stack.isEmpty()) { h=stack.pop(); System.out.print(h.val+" "); if(h.right!=null) { stack.push(h.right); } if(h.left!=null) { stack.push(h.left); } } } System.out.println(); }
后序遍歷
前序遍歷的順序是父節(jié)點,左,右,而后序遍歷的順序是左,右,父節(jié)點,也就是說前序遍歷左右替換之后就是后序遍歷的倒過來。所以只要把前序遍歷時候左右子節(jié)點壓棧的順序調換一下,再用另一個棧儲存,然后再彈出就是后序遍歷了。在此代碼就不多寫了。
中序遍歷
思路和流程
彈出就打印
整條左邊界依次入棧
上一條件無法繼續(xù),彈出打印,開始右子樹
public static void in(Node h) { System.out.print("中序遍歷 "); if(h!=null) { Stack<Node>stack =new Stack<Node>(); while(!stack.isEmpty()||h!=null) { if(h!=null) { stack.push(h); h=h.left; }else { h=stack.pop(); System.out.print(h.val+" "); h=h.right; } } } System.out.println(); }
后序遍歷變體
用一個Stack實現(xiàn)
思路是左節(jié)點沒處理就處理左節(jié)點,左節(jié)點處理過了就處理右節(jié)點,右節(jié)點處理完了就返回。
public static void pos2(Node h) { if(h!=null) { Stack<Node>stack =new Stack<Node>(); stack.push(h); Node c=null;//用c記錄上一次被打印的節(jié)點 while(!stack.isEmpty()) { c=stack.peek(); if(c.left!=null&&h!=c.left&&h!=c.right) { stack.push(c.left); }else if(c.right!=null&&h!=c.right) { stack.push(c.right); }else { System.out.print(stack.pop().val+" "); h=c;//記錄本次被打印的節(jié)點 } } } }
打印結果
感謝你能夠認真閱讀完這篇文章,希望小編分享的“java棧如何實現(xiàn)二叉樹的非遞歸遍歷”這篇文章對大家有幫助,同時也希望大家多多支持億速云,關注億速云行業(yè)資訊頻道,更多相關知識等著你來學習!
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經查實,將立刻刪除涉嫌侵權內容。