采用前序遍歷、中序遍歷、后續(xù)遍歷實(shí)現(xiàn)時(shí)，即便采用不同的實(shí)現(xiàn)方式（遞歸方式、非遞歸），它們的算法結(jié)構(gòu)是有很大的相似性。因而針對(duì)前三種的遍歷我們會(huì)總結(jié)出對(duì)應(yīng)通用的解決框架，便于在解決二叉樹問題時(shí)進(jìn)行使用。

遞歸方式遍歷二叉樹時(shí)，無論是 前序遍歷、中序遍歷 還是 后續(xù)遍歷 的方式，它們最大的區(qū)別就是對(duì)節(jié)點(diǎn)數(shù)據(jù)的訪問位置不同。除此之外其結(jié)構(gòu)完全一致，因而我們總結(jié)出如下的框架結(jié)構(gòu)：

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

對(duì)應(yīng)注釋的位置訪問數(shù)據(jù)就可以實(shí)現(xiàn)不同的遍歷方式。

例如，前序遍歷：

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);}

后續(xù)遍歷：

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

是否非常 easy！！

二叉樹非遞歸遍歷說實(shí)話有很多種實(shí)現(xiàn)方式，但本質(zhì)上都是模擬整個(gè)遍歷的過程來實(shí)現(xiàn)的。

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

整個(gè)算法框架如下：

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

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

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

實(shí)現(xiàn)代碼如下：

//使用雙棧來實(shí)現(xiàn)后序遍歷 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！！

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

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

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

此處我們借助 BFS 的框架，直接給出其實(shí)現(xiàn)方法：

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

較之于 BFS，我們會(huì)發(fā)現(xiàn)，層次遍歷，少了好多東西，比如不需要 visited 來標(biāo)記已訪問的節(jié)點(diǎn)（二叉樹本身結(jié)構(gòu)的特點(diǎn)，不可能出現(xiàn)重復(fù)遍歷），也不需要將隊(duì)列中的節(jié)點(diǎn)進(jìn)行擴(kuò)散等。

至此，二叉樹的四種遍歷方式總結(jié)完成。我們發(fā)現(xiàn)其實(shí)二叉樹所有的遍歷方式都有一種通用的算法框架，只要掌握算法本身的框架還是比較容易能夠?qū)懗鰧?shí)現(xiàn)代碼的。

以上就是Java 二叉樹遍歷的常用方法的詳細(xì)內(nèi)容，更多關(guān)于Java 二叉樹遍歷的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章！