java算法：树遍历

在给定一棵树的前提下，系统的处理树中的每个结点。

在链表中，沿着单个指针从一个结点移动到另一个结点；但对于树，必须做出某种决策，因为有多个指针可走。

二叉树：

前序：先访问结点，再访问左子树和右子树。

中序：先访问左子树，在访问结点，然后访问右子树

后续：先访问左右子树，再访问结点。

例1：递归树遍历

privatevoidtraverseR(Nodeh){
if(h==null){
return;
}
h.item.visit();
traverseR(h.l);
traverseR(h.r);
}
voidtraverse(){
traverse(root);
}

private void traverseR(Node h){
	if(h == null){
		return;
	}
	h.item.visit();
	traverseR(h.l);
	traverseR(h.r);
}
void traverse(){
	traverse(root);
}

考虑使用明确堆栈的非递归实现也是很有用的。先考虑能存放项或树的抽象栈，用要被遍历的树进行初始化。然后，进入循环过程，在那里弹出并处理栈中的顶端元素，继续进行直到栈为空。如果弹出的实体是一项，对它访问；如果是一棵树，则执行一系列指定顺序的压入操作：

对于前序：压入右子树，然后是左子树，再后是结点。

对于中序：压入右子树，然后是结点，在后是左子树。

对于后序：压入结点，然后是右子树，在后是左子树。

例2：前序遍历（非递归）

privatevoidtraverseS(Nodeh){
NodeStacks=newNodeStack(max);
s.push(h);
while(!s.empty()){
h=s.pop();
h.item.visit();
if(h.r!=null){
s.push(h.r);
}
if(h.l!=null){
s.push(h.l);
}
}
}
voidtraverseS(){
traverseS(root);
}

private void traverseS(Node h){
	NodeStack s = new NodeStack(max);
	s.push(h);
	while(!s.empty()){
		h = s.pop();
		h.item.visit();
		if(h.r != null){
			s.push(h.r);
		}
		if(h.l != null){
			s.push(h.l);
		}
	}
}
void traverseS(){
	traverseS(root);
}

通过使用队列替代栈可以实现层序遍历，对于前序，使用LIFO数据结构，对于层序，使用FIFO数据结构。层序并不对于与树的递归结构有关的递归的实现。

例3：层序遍历

privatevoidtraverseQ(Nodeh){
NodeQueueq=newNodeQueue(max);
q.push(h);
while(!q.empty()){
h=q.get();
h.item.visit();
if(h.r!=null){
s.push(h.r);
}
if(h.l!=null){
s.push(h.l);
}
}
}
voidtraverseQ(){
traverseQ(root);
}

private void traverseQ(Node h){
	NodeQueue q = new NodeQueue(max);
	q.push(h);
	while(!q.empty()){
		h = q.get();
		h.item.visit();
		if(h.r != null){
			s.push(h.r);
		}
		if(h.l != null){
			s.push(h.l);
		}
	}
}
void traverseQ(){
	traverseQ(root);
}	

用前序、后序和层序对于森林遍历的定义是明确的。