首页 > 代码库 > C++用非递归实现二叉树的前序排列,中序排列,后续排列

C++用非递归实现二叉树的前序排列,中序排列,后续排列

前序排列的非递归实现:
   Template<class T>
Void PreOrder(BinaryTreeNode<T> *t)
  {  
    stack <BinaryTreeNode<T> *> S(Maxlength);
     BinaryTreeNode<T> *p=t;
 do{
      while(p){
                 visit(p);//访问P
                  S.Add(p);
                  p=p->LeftChild;
              }
      If(!S.IsEmpty()){
         S.Delete(p);
         p=p->RightChild;
              }
  }while(p||!S.IsEmpty())
}




中序排列的非递归实现:
template<class T>
void InOrder(BinaryTreeNode<T> *t)     //对*t进行中序遍历
{  	stack  <BinaryTreeNode<T> *>   S(MaxLength);
    BinaryTreeNode<T> *p=t ;
   do {
		while (p)  
                 {S.Add(p);   p=p->LeftChild;}	
		  if (!S.IsEmpty()) 
                    {S.Delete(p);
                      Visit(p);				
		           p=p->RightChild;
                     }  	
	  } while (p||!S.IsEmpty())  
}
后续排列的非递归实现:
template<class T>
void PostOrder(BinaryTreeNode<T> *t)   
{  	stack  <BinaryTreeNode<T> *>   S(MaxLength);
    BinaryTreeNode<T> *p=t ;
   do {
		while (p)  
              {S.Add(p); p=p->LeftChild;}	
		  if (!S.IsEmpty()) 
       {
                    If(p->RightChild){ 
                    S.Delete(p);
                    S.Add(p);S.Add(p->RightChild);p=p->RightChild;}
      else{ S.Delete(p);visit(p);}
                 				
		                                }  	
	  } while (p||!S.IsEmpty())  
}



C++用非递归实现二叉树的前序排列,中序排列,后续排列