上次分享了二叉树的数据结构，这次楠哥专门拿出一节来分析二叉树的遍历（Traverse）问题。事实上，二叉树的搜索（Search）问题和遍历问题非常相似，不同的是遍历问题会访问树的每一个节点，而搜索问题一旦找到了所需要的结点就停止操作了。搜索问题楠哥会在后续算法相关的文章当中详解，本次主要分析最常用的两种遍历方法。(楠哥计算机学习网www.liubonan.com)
深度优先遍历（Depth First）是指对于一颗树，首先访问其左节点，后访问右节点，再访问其根节点；对于节点本身是子树的情况，则按此规则继续深入，直到叶节点位置。这种方法有两种实现的思路。第一种是使用递归（Recursion）的方式，即如果该节点不是叶节点则访问其左子树、右子树，在访问节点本身；另外一种思路是递推（Iteration）的方式，这里需要定义一个栈（Stack），即LIFO队列，如果栈顶结点不是叶节点，就将其左右子树压入栈；循环的从栈顶取结点，再按此规则进行处理。栈的实现Java已经给出，当然也可以使用自定义的类型，具体方式详见《Java中栈的实现》。
广度优先遍历（Breadth First）是指对一棵树，首先访问第一层的结点，在访问第二层的结点，依次类推。这里我们需要用一个FIFO队列（Queue）来实现：将每一个结点的所有子结点加入到队列中，再从队列中选取队首元素出队，依次规则进行循环直到所有结点全部出队。队列的实现Java同样也有现成的类，如果想自定义该数据结构，可以参考《Java中队列的实现》。(楠哥计算机学习网www.liubonan.com)
下面的代码实现了两种深度优先遍历方式和一种广度优先遍历方式，因为树的具体代码已经在上次文章中给出，本文只列出遍历函数的代码。全部代码详见《Java中的二叉树》。(楠哥计算机学习网www.liubonan.com)
public void dfs_re(Node current)
{
if((current.getLeft() == null)&&(current.getRight() == null))
System.out.print(current.getData() + " ");
else
{
if(current.getLeft() != null)
dfs_re(current.getLeft());
if(current.getRight() != null)
dfs_re(current.getRight());
System.out.print(current.getData() + " ");
}
}
public void bfs()
{
Queue q = new LinkedList();
q.add(root);
while(!q.isEmpty())
{
Node temp = q.remove();
if(temp.getLeft()!=null)
q.add(temp.getLeft());
if(temp.getRight()!=null)
q.add(temp.getRight());
System.out.print(temp.getData() + " ");
}
}
public void dfs_it()
{
Stack s = new Stack();
s.push(root);
while(!s.isEmpty())
{
Node temp = s.pop();
if(((temp.getLeft() == null)&&(temp.getRight() == null)) || (temp.isVisited()))
System.out.print(temp.getData() + " ");
else
{
if(temp.getRight() == null)
{
Node left = temp.getLeft();
temp.setVisited(true);
s.push(temp);
s.push(left);
}
else
{
if(temp.getLeft() == null)
{
Node right = temp.getRight();
temp.setVisited(true);
s.push(temp);
s.push(right);
}
else
{
Node left = temp.getLeft();
Node right = temp.getRight();
temp.setVisited(true);
s.push(temp);
s.push(right);
s.push(left);
}
}
}
}
}