新建 文本文档 (10).txt

该软件会在用户的使用过程中自动进行调整达到最佳状态

二叉树递归遍历算法
 
 
先序遍历递归算法
 
void    PreOrder(BiTree *T)
{   if(T==NULL)
        return ;
    Visit(T);  //访问根结点
    PreOrder(T->left); //递归遍历左子树
    PreOrder(T->right);//递归遍历右子树
 }
 
中序递归遍历算法
 
void    InOrder(BiTree *T)
{    if(T==NULL)
        return;
     InOrder(T->left); //递归遍历左子树
       Visit(T);  //访问根结点
     InOrder(T->right);//递归遍历右子树
 
 }
 
后序递归遍历算法
 
void    PostOrder(BiTree *T)
{   if(T==NULL)
        return;
    PostOrder(T->left); //递归遍历左子树
    PostOrder(T->right);//递归遍历右子树
      Visit(T);  //访问根结点
 }
 
二叉树非递归遍历算法
 
 
先序遍历非递归算法
 
【思想一】

    访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
 
    基于【思想一】的二叉树非递归遍历算法实现如下：

void    PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{   
   InitStack(S);   //初始化工作栈
   BiTree p=T;
   while ( p!=NULL || !StackEmpty(S)) //二叉树不空或者工作栈不空
   {
      while ( p != NULL )
      {
         Visit(p) ;  //访问根结点
         Push(S,p);    //将二叉树的根（包括左子树）结点进栈
         p = p->lchild;  //向左依次遍历
       }
      if( !StackEmpty(S) )  //如果栈不空，则回溯遍历右子树
      {
         Pop(S,T);  //根结点（包括子树的根结点）出栈
         p = p->rchild; //向右依次遍历右子树结点
       }
   }
}
 
【思想二】

    访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。
 
    基于【思想二】的二叉树非递归遍历算法实现如下：

void    PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{    
   InitStack(S);  //初始化工作栈
   BiTree p=T;
   while ( p!=NULL || !StackEmpty(S) )  //二叉树不空或者工作栈不空
   {
      while ( p != NULL )
      {
         Visit(p);  //访问根结点（进栈时先依次访问左子树的根结点；出栈时再依次访问右子树的根结点）
         Push(S, p->rchild);//右子树进栈，等待遍历左子树完成后弹出以至于被访问
         p = p->lchild; //左子树进栈
       }
      if ( !StackEmpty(S) ) //如果栈不空
      {
         Pop(S,p);  //依次出栈
       }
    }
}
中序遍历非递归算法

【思想】

    先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

void    InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{   InitStack(S);    //初始化工作栈
    BiTree p=T;
    while ( p!=NULL || !StackEmpty(S) )

    { 
        while ( p != NULL )

        {
            Push(S,p);
            p = p->lchild;
         }
        if( !StackEmpty(S) )

        {
            Pop(S, p);
            Visit(T->data);
            p = p->rchild;
        }
    }
}

后序遍历非递归算法

【思想】

    T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
    可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
    首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。


typedef struct stackElement{
BiTree    data;
char        tag;
}stackElemType;

void    PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{    

   InitStack(S);

   BiTree p=T;
   while ( p!=NULL || !StackEmpty(S) )

   {
       while ( p != NULL )

       {
             Push(S,p,0);
             p = p->lchild;
        }
       while ( !StackEmpty(S) && GetTopTag(S)==1)

       {
             pop(S, p);
             Visit(p);
       }
       if ( !StackEmpty(S) )

       {
             SetTopTag(S, 1);        // 设置栈顶标记
             p = GetTopPointer(S);    // 取栈顶保存的指针
             p = p->rchild;
        }

        else 

             break;
        }
 }

二叉树层次遍历算法

void LayerOrder(BiTree T)

{

    if(T==NULL)

        return;  

     InitQueue(Q); //建立工作队列

     BiTree p=T;

     EnQueue(Q,p);//根结点入队

     while(QueueEmpty(Q))

     {

           DeQueue(Q,p);

           Visit(p->data);

           if(p->lchild)

               EnQueue(Q,p->lchild);

          if(p->rchild)

               EnQueue(Q,p->rchild);

       }

 }