二叉树递归和非递归遍历 (一)

1、递归遍历

[java]
// 先序遍历（递归实现）-------------------------------------------------------------
/*
1. Visit the node.
1. Call itself to traverse the node’s left subtree.
3. Call itself to traverse the node’s right subtree.
4. base case: there is no node
*/
private void preOrder(Node localRoot){
if(localRoot != null)
{
visit(localRoot); // System.out.print(localRoot.iData + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
// 中序遍历（递归实现）-------------------------------------------------------------
private void inOrder(Node localRoot){
if(localRoot != null)
{
inOrder(localRoot.leftChild);
visit(localRoot); //System.out.print(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
// 后序遍历（递归实现）-------------------------------------------------------------
private void postOrder(Node localRoot){
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
visit(localRoot); //System.out.print(localRoot.iData + " ");
}
}
// -------------------------------------------------------------

// 先序遍历（递归实现）-------------------------------------------------------------
/*
1. Visit the node.
1. Call itself to traverse the node’s left subtree.
3. Call itself to traverse the node’s right subtree.
4. base case: there is no node
*/
private void preOrder(Node localRoot){
if(localRoot != null)
{
visit(localRoot); // System.out.print(localRoot.iData + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
// 中序遍历（递归实现）-------------------------------------------------------------
private void inOrder(Node localRoot){
if(localRoot != null)
{
inOrder(localRoot.leftChild);
visit(localRoot); //System.out.print(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
// 后序遍历（递归实现）-------------------------------------------------------------
private void postOrder(Node localRoot){
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
visit(localRoot); //System.out.print(localRoot.iData + " ");
}
}
// -------------------------------------------------------------
2、非递归遍历

[java]
/*
总体思想是：因为递归的本质是用栈实现的，所以写出非递归的形式要用到栈。入栈的顺序与访问的顺序相反，如中序遍历访问顺序是left,current,right,所以入栈的顺序相反是right,current,left
steo0:初始化当前节点current
step1:初始化栈
step3:出栈,并访问
Note：中序遍历和后序遍历需要先判断bPushed为true时访问）
step2:入栈
循环结束条件是：栈为空
*/

//算法框架 pushNode是入栈的方式
public void templet(Node root){
//special case
if(root==null)
return;

//inital current node
Node current=root;

//initial stack
Stack s=new Stack();
pushNode(current,s);

//loop: base case is stack is empty
while( !s.empty() ){
//pop
current=s.pop();

//visit or push
}//end while
}//end templet()

// 先序遍历-深度优先搜索（递归实现）-------------------------------------------------------------
//current left right
//step1:pop curr