采用前序遍歷、中序遍歷、后續遍歷實現時，即便采用不同的實現方式（遞歸方式、非遞歸），它們的算法結構是有很大的相似性。因而針對前三種的遍歷我們會總結出對應通用的解決框架，便于在解決二叉樹問題時進行使用。

遞歸方式遍歷二叉樹時，無論是 前序遍歷、中序遍歷 還是 后續遍歷 的方式，它們最大的區別就是對節點數據的訪問位置不同。除此之外其結構完全一致，因而我們總結出如下的框架結構：

void traverse(TreeNode root) { //終止條件 if(root == null) return; // 前序遍歷 traverse(root.left); // 中序遍歷 traverse(root.right); // 后序遍歷}

對應注釋的位置訪問數據就可以實現不同的遍歷方式。

例如，前序遍歷：

void traverse(TreeNode root) { if(root == null) return; visit(root); traverse(root.left); traverse(root.right);}

同樣的中序遍歷：

void traverse(TreeNode root) { if(root ==null) return; traverse(root.left); visit(root); traverse(root.right);}

后續遍歷：

void traverse(TreeNode root) { if(root ==null) return; traverse(root.left); traverse(root.right)}

是否非常 easy！！

二叉樹非遞歸遍歷說實話有很多種實現方式，但本質上都是模擬整個遍歷的過程來實現的。

為了便于理解，其中前序遍歷、中序遍歷、后序遍歷我們采用一套類似的算法框架。

整個算法框架如下：

public void traverse(TreeNode root) { // 邊界判斷 if (root == null) { return; } Stack<TreeNode> stack = new Stack<>(); TreeNode current = root; while (current != null || !stack.isEmpty()) { //節點非空時，證明父節點的左側節點非空，直接入棧 if (current != null) {//前序遍歷 visit(current)stack.push(current);current = current.left; } else {//節點為空，證明左側節點為空，出棧，更換游標節點方向current = stack.pop();//中續遍歷 visit(current);current = current.right; } } }

后序遍歷它的遍歷順序為**'左--> 右--> 根'，較之與前序遍歷的'根--> 左--> 右'，好像是有很大的相似性，我們能否針對上邊的框架進行修改，使由前序遍歷轉換成后序遍歷？？答案是肯定的，我們可以觀察到，可以先求出遍歷順序是'根--> 右--> 左'**'的節點序列，再倒序，便剛好是后序遍歷的順序：左右根。而遍歷順序是根右左的話，很好辦，從前序遍歷的代碼中改兩行就是了。

故而，可以選擇使用兩個棧，其中一個用于遍歷，另一個用于結果的倒序。

實現代碼如下：

//使用雙棧來實現后序遍歷 public void postOrderTraverse(TreeNode root){ Stack<TreeNode> stack = new Stack<>(); Stack<Integer> res = new Stack<>(); TreeNode cur = root; while (cur!=null || !stack.isEmpty()) { if (cur!=null){stack.push(cur);res.push(cur.val);cur = cur.right; //修改處 }else{cur = stack.pop();cur = cur.left; // 修改處 } } while (!res.isEmpty()){ visit(res.pop()); } }

至此，非遞歸遍歷完成，是不是也很 easy！！

下邊我們可以看一下最后一種層次遍歷

層次遍歷本質上就是閹割版廣度優先遍歷，我們此處就直接給出 BFS 算法的框架：

/*** 給定起始節點start和目標節點target，返回其最短路徑長度**/int BFS(Node start,Node target){ Queue<Node> q; //核心數據結構 Set<Node> visited: //某些情況下可以通過byte數組來進行代替 int step = 0; //記錄擴散步數 //起始節點入隊列 q.add(start); visited.offer(start); while(q not empty) {//必須要用sz來保存q.size()，然后擴散sz不能直接使用q.size()int sz = q.size();//將隊列中的節點進行擴散for(int i =0 ; i < sz; i++) { Node cur = q.poll(); // 目標節點判斷 if(cur is target) {return step; } // 鄰接結點入隊列 for(Node n:cur.adjs) {//未訪問節點入隊列if(n is not int visited) { visitd.add(n); q.offer(n);} }}// 更新步數step++; }}

此處我們借助 BFS 的框架，直接給出其實現方法：

void LevelOrder(TreeNode root){ //初始化棧，并放入 Queue<TreeNode> queue; queue.add(root); while( !queue.isEmpty()) {//出棧TreeNode cur = queue.poll();//訪問節點visit(cur);//向下一層級擴散if(cur.left !=null) queue.add(cur.left);if(cur.right !=null) queue.add(cur.right); }}

較之于 BFS，我們會發現，層次遍歷，少了好多東西，比如不需要 visited 來標記已訪問的節點（二叉樹本身結構的特點，不可能出現重復遍歷），也不需要將隊列中的節點進行擴散等。

至此，二叉樹的四種遍歷方式總結完成。我們發現其實二叉樹所有的遍歷方式都有一種通用的算法框架，只要掌握算法本身的框架還是比較容易能夠寫出實現代碼的。

以上就是Java 二叉樹遍歷的常用方法的詳細內容，更多關于Java 二叉樹遍歷的資料請關注好吧啦網其它相關文章！