遍歷一棵樹是指訪問樹的每個節點並對它們進行某種操作的過程。但是我們應該怎麼去做呢？應該從樹的頂端還是底端開始呢？從左開始還是從右開始呢？訪問樹的所有節點有三種方式：中序、先序和後序。
在後面的小節中，我們將會深入瞭解這三種遍歷方式的用法和實現。
8.4.1 中序遍歷
中序遍歷是一種以上行順序訪問BST所有節點的遍歷方式，也就是以從最小到最大的順序訪問所有節點。中序遍歷的一種應用就是對樹進行排序操作。我們來看它的實現：
this.inOrderTraverse = function(callback){
inOrderTraverseNode(root, callback); //{1}
};
inOrderTraverse方法接收一個回調函數作為參數。回調函數用來定義我們對遍歷到的每個節點進行的操作（這也叫作訪問者模式，要瞭解更多關於訪問者模式的信息，請參考http://en.wikipedia.org/wiki/Visitor_pattern）。由於我們在BST中最常實現的算法是遞歸，這裡使用了一個私有的輔助函數，來接收一個節點和對應的回調函數作為參數（行{1}）。
var inOrderTraverseNode = function (node, callback) {
if (node !== null) { //{2}
inOrderTraverseNode(node.left, callback); //{3}
callback(node.key); //{4}
inOrderTraverseNode(node.right, callback); //{5}
}
};
要通過中序遍歷的方法遍歷一棵樹，首先要檢查以參數形式傳入的節點是否為null（這就是停止遞歸繼續執行的判斷條件——行{2}——遞歸算法的基本條件）。
然後，遞歸調用相同的函數來訪問左側子節點（行{3}）。接著對這個節點進行一些操作（callback），然後再訪問右側子節點（行{5}）。
我們試著在之前展示的樹上執行下面的方法：
function printNode(value){ //{6}
console.log(value);
}
tree.inOrderTraverse(printNode); //{7}
但首先，需要創建一個回調函數（行{6}）。我們要做的，是在瀏覽器的控制台上輸出節點的值。然後，調用inOrderTraverse方法並將回調函數作為參數傳入（行{7}）。當執行上面的代碼後，下面的結果將會在控制台上輸出（每個數字將會輸出在不同的行）：
3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
下面的圖描繪了inOrderTraverse方法的訪問路徑：
8.4.2 先序遍歷
先序遍歷是以優先於後代節點的順序訪問每個節點的。先序遍歷的一種應用是打印一個結構化的文檔。
我們來看實現：
this.preOrderTraverse = function(callback){
preOrderTraverseNode(root, callback);
};
preOrderTraverseNode方法的實現如下：
var preOrderTraverseNode = function (node, callback) {
if (node !== null) {
callback(node.key); //{1}
preOrderTraverseNode(node.left, callback); //{2}
preOrderTraverseNode(node.right, callback); //{3}
}
};
先序遍歷和中序遍歷的不同點是，先序遍歷會先訪問節點本身（行{1}），然後再訪問它的左側子節點（行{2}），最後是右側子節點（行{3}），而中序遍歷的執行順序是：{2}、{1}和{3}。
下面是控制台上的輸出結果（每個數字將會輸出在不同的行）：
11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
下面的圖描繪了preOrderTraverse方法的訪問路徑：
8.4.3 後序遍歷
後序遍歷則是先訪問節點的後代節點，再訪問節點本身。後序遍歷的一種應用是計算一個目錄和它的子目錄中所有文件所佔空間的大小。
我們來看它的實現：
this.postOrderTraverse = function(callback){
postOrderTraverseNode(root, callback);
};
postOrderTraverseNode方法的實現如下：
var postOrderTraverseNode = function (node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback); //{1}
postOrderTraverseNode(node.right, callback); //{2}
callback(node.key); //{3}
}
};
這個例子中，後序遍歷會先訪問左側子節點（行{1}），然後是右側子節點（行{2}），最後是父節點本身（行{3}）。
你會發現，中序、先序和後序遍歷的實現方式是很相似的，唯一不同的是行{1}、{2}和{3}的執行順序。
下面是控制台的輸出結果（每個數字將會輸出在不同行）：
3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
下面的圖描繪了postOrderTraverse方法的訪問路徑：
