遍历一棵树是指访问树的每个节点并对它们进行某种操作的过程。但是我们应该怎么去做呢？应该从树的顶端还是底端开始呢？从左开始还是从右开始呢？访问树的所有节点有三种方式：中序、先序和后序。
在后面的小节中，我们将会深入了解这三种遍历方式的用法和实现。
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方法的访问路径：