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

/*
总体思想是：因为递归的本质是用栈实现的，所以写出非递归的形式要用到栈。入栈的顺序与访问的顺序相反，如中序遍历访问顺序是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 current node
//step2:visit current node
//step3:push current's right child
//step4:push current's left child
//step5: loop step1-step5

privete void pushPreOrderNode(Node current, Stack s){
if(current==null)
return ;
if(!s.empty()){
leftChild=current.leftChild;
rightChild=curret.rightChild;

if(rightChild!=null) //push rightChild
s.push(rightChild);
if(leftChild!=null) //push leftChild
s.push(leftChild):
visit(current); //current always first visit in preOrder
}//end if
}//end pushPreOrderNode()

public void preOrder(Node root){
//special case
if(root==null)
return ;

//inintial current node
Node current=root;
//inintial stack
Stack s=new Stack();
pushPreOrderNode(current,s);

//base case:stack is empty
while( !s.empty() ){
//pop
current=s.pop();
//push
pushPreOrderNode(current,s);
}//end while
}//end preOrder()

// 中序遍历（非递归实现）-------------------------------------------------------------
/*
left current right
*/

public void inOrder( Node root){
//special case
if(root==null)
return;

Node current=root;
//initial stack
Stack s=new Stack();
pushInOrderNode(current,s);

//pop and visit
while( !s.empty() ){
current=s.pop();
if(current.bPushed)
visit(current);
else
pushInOrderNode(current,s);
}//end while
}//end postOrder()

private void pushInOrderNode(Node current,Stack s){
if(current==null)
return;
if(!s.empty()){
leftChild=current.leftChild;
rightChild=curret.rightChild;

if(rightChild!=null){ //push rightChild
s.push(rightChild);
rightChild.bPushed=false;
}//end if

s.push(current); //push current



if(leftChild!=null){ //push leftChild
s.push(leftChild);
rightChild.bPushed=false;
}//end if

//set flag, ture present current's left and right has both pushed
current.bPushed=true;
}//end if
}//end if
}//end pushInOrderNode()
// --------------------------------------------------------