前言
二叉樹作為一種非畴时迹基礎(chǔ)但十分重要的數(shù)據(jù)結(jié)構(gòu)，在排序预吆、搜索龙填、編碼、甚至文件系統(tǒng)管理等方面都有廣泛應(yīng)用拐叉。今天岩遗，我想講講關(guān)于二叉樹遍歷的那些事兒。為了大家可以清晰地看懂下文中的代碼凤瘦，在此先定義二叉樹的數(shù)據(jù)結(jié)構(gòu)（使用java語言）宿礁。
/**
* 二叉樹數(shù)據(jù)結(jié)構(gòu)
*/
private static class TreeNode {
int val;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
深度優(yōu)先VS廣度優(yōu)先
大的方面來講呢，二叉樹有兩種遍歷方法——深度優(yōu)先遍歷和廣度優(yōu)先遍歷蔬芥。
深度優(yōu)先：對每一個可能的分支路徑深入到不能再深入為止梆靖，而且每個結(jié)點只能訪問一次。要特別注意的是笔诵，二叉樹的深度優(yōu)先遍歷比較特殊返吻，可以細分為先序遍歷、中序遍歷乎婿、后序遍歷测僵。深度優(yōu)先遍歷非遞歸的通用做法是采用棧。
廣度優(yōu)先：從上往下對每一層依次訪問谢翎，在每一層中捍靠，從左往右（也可以從右往左）訪問結(jié)點，訪問完一層就進入下一層岳服，直到?jīng)]有結(jié)點可以訪問為止。廣度優(yōu)先遍歷非遞歸的通用做法是采用隊列希俩。
深度優(yōu)先遍歷
深度優(yōu)先遍歷根據(jù)根節(jié)點和左右子樹訪問的順序可以分為先序吊宋、中序和后序遍歷。
先序遍歷
先序遍歷：對任一子樹颜武，先訪問根璃搜，然后遍歷其左子樹，最后遍歷其右子樹鳞上。按照這個規(guī)則这吻，可以很容易的寫出先序遍歷的遞歸方法。
/**
* 先序遍歷二叉樹篙议，遞歸
* @param root
*/
public static void preOrderTraverse(TreeNode root){
if(root == null){
return;
}
System.out.print(root.val + " ");
preOrderTraverse(root.left);
preOrderTraverse(root.right);
}
對于非遞歸方法唾糯，可以描述為：由根節(jié)點開始怠硼，不斷將二叉樹的節(jié)點壓入棧中，然后由棧中取出棧頂節(jié)點移怯，并且將該節(jié)點的右香璃、左（順序不可顛倒）子節(jié)點壓入棧中，循環(huán)此過程直至棧為空舟误。 該方法的java代碼如下：
/**
* 先序遍歷二叉樹葡秒，非遞歸
* @param root
*/
public static void preOrderTraverseNoRecursion(TreeNode root){
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode currentNode = stack.pop();
System.out.print(currentNode.val + " ");
if (currentNode.right != null){
stack.push(currentNode.right);
}
if (currentNode.left != null){
stack.push(currentNode.left);
}
}
System.out.print("\n");
}
中序遍歷
中序遍歷：對任一子樹，先遍歷其左子樹嵌溢，然后訪問根眯牧，最后遍歷其右子樹。按照這個規(guī)則赖草，可以很容易的寫出中序遍歷的遞歸方法秒梳。
/**
* 中序遍歷二叉樹，遞歸
* @param root
*/
public static void inOrderTraverse(TreeNode root){
if(root == null){
return;
}
inOrderTraverse(root.left);
System.out.print(root.val + " ");
inOrderTraverse(root.right);
}
而對于中序遍歷届巩，算法可描述為：首先峦朗，找到二叉樹中最左邊的子節(jié)點，并依次將節(jié)點壓入棧中腿堤，然后取出棧頂節(jié)點阀坏，并將該節(jié)點的右節(jié)點視為新的根節(jié)點，重復(fù)上述過程笆檀，直至節(jié)點為空或者棧為空忌堂，java代碼如下：
/**
* 中序遍歷二叉樹，非遞歸
* @param root
*/
public static void inOrderTraverseNoRecursion(TreeNode root){
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode currentNode = root;
while (currentNode != null || !stack.isEmpty()){
// 一直循環(huán)到二叉樹最左端的葉子結(jié)點（currentNode是null）
if (currentNode != null){
stack.push(currentNode);
currentNode = currentNode.left;
} else{
currentNode = stack.pop();
System.out.print(currentNode.val + " ");
currentNode = currentNode.right;
}
}
System.out.print("\n");
}
后序遍歷
后序遍歷：對任一子樹酗洒，先遍歷其左子樹士修，然后遍歷其右子樹，最后再訪問根樱衷。按照這個規(guī)則棋嘲，可以很容易的寫出后序遍歷的遞歸方法。
/**
* 后序遍歷二叉樹矩桂，遞歸
* @param root
*/
public static void postOrderTraverse(TreeNode root){
if(root == null){
return;
}
postOrderTraverse(root.left);
postOrderTraverse(root.right);
System.out.print(root.val + " ");
}
對于后序遍歷的非遞歸算法沸移，可描述如下：首先，找到二叉樹中最左邊的子節(jié)點侄榴，并依次將節(jié)點壓入棧中雹锣，然后取出棧頂節(jié)點，判斷該節(jié)點是否存在右子節(jié)點或者該節(jié)點是否為其父節(jié)點的右子節(jié)點癞蚕，如果為真蕊爵，則輸出節(jié)點元素，并更新當(dāng)前節(jié)點和右子節(jié)點桦山，循環(huán)該過程直至判斷條件不滿足攒射，然后將該節(jié)點的右節(jié)點視為新的根節(jié)點醋旦，重復(fù)上述過程，直至節(jié)點為空或者棧為空匆篓，java代碼如下：
/**
* 后序遍歷二叉樹浑度，非遞歸
* @param root
*/
public static void postOrderTraverseNoRecursion(TreeNode root){
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode currentNode = root;
TreeNode rightNode = null;
while (currentNode != null || !stack.isEmpty()){
// 一直循環(huán)到二叉樹最左端的葉子結(jié)點（currentNode是null）
while (currentNode != null){
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
// 當(dāng)前結(jié)點沒有右結(jié)點或上一個結(jié)點（已經(jīng)輸出的結(jié)點）是當(dāng)前結(jié)點的右結(jié)點，則輸出當(dāng)前結(jié)點
while (currentNode.right == null || currentNode.right == rightNode){
System.out.print(currentNode.val + " ");
rightNode = currentNode;
if(stack.isEmpty()){
System.out.println();
return;
}
currentNode = stack.pop();
}
stack.push(currentNode);
currentNode = currentNode.right;
}
}
廣度優(yōu)先遍歷
層次遍歷
層次遍歷指的是將二叉樹按層輸出鸦概。借助隊列可以很容易的實現(xiàn)層次優(yōu)先遍歷箩张。算法描述為：由根節(jié)點開始，不斷將二叉樹的節(jié)點送至隊列中窗市，然后由隊列中取出隊列頭節(jié)點先慷，并且將該節(jié)點的左、右子節(jié)點分別送至隊列中咨察，循環(huán)此過程直至隊列為空论熙。java代碼如下：
/**
* 普通層次遍歷
* @param root
*/
public static void levelTraverse(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()){
TreeNode currentNode = queue.poll();
System.out.print(currentNode.val + " ");
if (currentNode.left != null){
queue.add(currentNode.left);
}
if (currentNode.right != null){
queue.add(currentNode.right);
}
}
System.out.println();
}
層次遍歷進階
除了一般的層次遍歷，這里再介紹一種面試中成阌考的層次遍歷——按二叉樹的層次結(jié)構(gòu)分行輸出元素脓诡。要實現(xiàn)這種需求，只需要兩個指針記錄當(dāng)前行和下一行最右的節(jié)點即可媒役。java代碼如下：
/**
* 按行打印二叉樹
* 算法描述：
* 1. 初始化：將根節(jié)點傳入隊列祝谚，last、nlast指針均指向根節(jié)點酣衷，
* 其中交惯，last指針指向當(dāng)前行最右側(cè)的元素，nlast指針指向下一行最右側(cè)的元素
* 2. 循環(huán)判斷隊列是否為空穿仪，如果不為空席爽，則：
* 2.1: 獲取隊列頭元素p（將其在隊列內(nèi)刪除）并打印
* 2.2: 將該節(jié)點的左右子樹分別壓入隊列，并更新nlast指針
* 2.3: 判斷l(xiāng)ast指針與p是否相等啊片，如果相等只锻，則換行，并且更新last = nlast
* @param root
* @return
*/
public static void printTreeByRow(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
TreeNode last = root;
TreeNode nLast = null;
while (!queue.isEmpty()){
TreeNode p = queue.poll();
System.out.print(p.val + " ");
if (p.left != null){
queue.add(p.left);
nLast = p.left;
}
if (p.right != null){
queue.add(p.right);
nLast = p.right;
}
// 當(dāng)last == p時代表該換行了
if(last == p){
last = nLast;
System.out.print("\n");
}
}
}
總結(jié)
本篇博文主要介紹了二叉樹的遍歷方法——深度優(yōu)先和廣度優(yōu)先紫谷，掌握二叉樹的遍歷方法對于棧和隊列的使用也很有幫助齐饮。
推薦閱讀
- 數(shù)據(jù)結(jié)構(gòu)之二叉樹(三)——二叉查找樹
- 數(shù)據(jù)結(jié)構(gòu)之二叉樹(四)——AVL樹
- 數(shù)據(jù)結(jié)構(gòu)之二叉樹(五)——紅黑樹(待更新)
寫在最后
歡迎大家關(guān)注我的個人博客復(fù)旦猿。
