• 热门专题

二叉树的递归遍历与非递归算法实现

作者:我非英雄  发布日期:2013-12-05 22:42:05
Tag标签:二叉树  递归  遍历  
  •        通过递归算法与非递归算法的比较,更好地理解各自的特点。非递归其实就是调用栈的基本操作,进栈,出栈等。 这里面也正好复习了下栈的基本算法的实现。   栈和队列的实现在我的前一篇博文里。   基本数据结构 typedef struct BiNode {       char data;   //此处,二叉树中节点值类型为字符型       struct BiNode *lchild,*rchild;     //左右孩子节点 }BiNode,*BiTree;      二叉树的创建 先申请根节点的空间,然后赋值,然后分别递归建立其左子树和右子树 //按照先序序列输入构建一棵二叉树
     1 //按照先序序列输入构建一棵二叉树
     2 void Create(BiTree &T)
     3 {
     4     char ch;
     5     scanf('%c',&ch);
     6     if( '#' == ch )
     7     {
     8         T = NULL;
     9     }
    10     else
    11     {
    12         T=(BiNode *)malloc(sizeof(BiNode));
    13         T->data=ch;
    14         Create(T->lchild);
    15         Create(T->rchild);
    16     }
    17 }
    View Code

     

    二叉树的递归遍历算法

    //二叉树的遍历,三种顺序的递归遍历,其实就是访问根节点的顺序不同,这里的访问操作是打印结点,也可以是对结点其他的操作  
     1 //二叉树的先序遍历
     2 
     3 void PreOrder(BiTree T)
     4 
     5 {
     6 
     7       if(T)
     8 
     9      {
    10 
    11            printf( '%c ',T->data);
    12 
    13            PreOrder(T->lchild);
    14 
    15            PreOrder(T->rchild);
    16 
    17      }
    18 
    19 }
    20 
    21 //二叉树的中序遍历
    22 
    23 void InOrder(BiTree T)
    24 
    25 {
    26 
    27       if(T)
    28 
    29      {
    30 
    31            InOrder(T->lchild);
    32 
    33            printf( '%c ',T->data);
    34 
    35            InOrder(T->rchild);
    36 
    37      }
    38 
    39 }
    40 
    41  
    42 
    43 //二叉树的后序遍历
    44 
    45 void PostOrder(BiTree T)
    46 
    47 {
    48 
    49       if(T)
    50 
    51      {
    52 
    53            PostOrder(T->lchild);
    54 
    55            PostOrder(T->rchild);
    56 
    57            printf( '%c ',T->data);
    58 
    59      }
    60 
    61 }
    View Code

     

      二叉树的非递归遍历算法   二叉树先序遍历的非递归算法
    /* 设置一个存放结点指针的栈 S ,从根结点开始,每访问一结点后,按先序规则走左子树,若右子树存在,
    
    则将右子树指针进栈,以便以后能正确地返回到该右子树上进行遍历访问。
    
    */
    
    void PreTraverse(BiTree T)
    
    {
    
         BiNode *p;
    
         Stack S;
    
         S=InitStack();
    
          if (T)
    
         {
    
               Push(S,T);  // 根结点指针进栈
    
                while (!StackEmpty(S))
    
               {
    
                    p=Pop(S);  // 出栈,栈顶元素赋给 p
    
                     while (p)
    
                    {
    
                         printf( '%c	' ,p->data);  // 访问 p结点
    
                          if (p->rchild)
    
                               Push(S,p->rchild);  // 右子树存在时,进栈
    
                         p=p->lchild;            // 继续沿着左子树往下走
    
                    }
    
               }
    
         }
    
    }

    /*

    说明:内部循环是从 p 结点出发一直走到最左,走的过程中保存了每一个右子树的地址, (因为右子树还没有被访问)而且是先进后出的,即先保存的比后保存的更先被用作返回地址, 所以是用栈。外循环正好是当内部循环不下去的时候,退一栈的情形。即换成他的右子树。 */   // 二叉树的中序遍历的非递归算法
    /*
    
    同前序遍历 , 栈S 存放结点指针。对每棵子树 ( 开始是整棵二叉树 ),沿左找到该子树在中序下的第一结点
    
    ( 但寻找路径上的每个结点指针要进栈 ), 访问之; 然后遍历该结点的右子树 ,
    
    又寻找该子树在中序下的第一结点, .. …直到栈S 空为止。
    
    */
    
    
    void InTraverse(BiTree T)
    
    {
    
         BiNode *p;
    
         Stack S;
    
         S=InitStack();
    
         Push(S,T);  // 根结点指针进栈
    
          while (!StackEmpty(S))
    
         {
    
                while ((p=GetsTop(S))&&p)  //取栈顶元素且存在,赋给 p
    
                    Push(S,p->lchild);    //p 的左子树进栈
    
               p=Pop(S);               // 去掉最后的空指针
    
                if (!StackEmpty(S))
    
               {
    
                    p=Pop(S);       // 弹出栈顶元素,赋给 p
    
                    printf( '%c	' ,p->data);   // 访问 p结点
    
                    Push(S,p->rchild);     // 右子树进栈,然后遍历右子树
    
               }
    
         }
    
    }

     /*

    说明:和前序不一样,这里的栈保存的是根结点的地址(因为中序遍历先访问左子树, 而根结点没有被访问到。而前序遍历不一样,他一开始就访问根结点, 所以他不保存根结点的地址而是保存右子树的地址,因为右子树还没有被访问。 总之,用栈就是为了帮我们保存还没有被访问的地址,以便将来我们能找到返回的地址)。 */   /* 后序遍历二叉树的非递归算法 */
    /* 对一个结点是否能访问,要看他的左、右子树是否遍历完, */
    
    /* 所以每一个结点对应一个标志位 -tag 。tag=0 ,表示该结点暂不能访问; tag=1 ,表示该结点可以访问 */
    
    /* 其实是区分这次返回是遍历完左子树返回的还是遍历完右子树返回的,如果是左子树返回的那么就不能访问根结点, */
    
    /* 如果是右子树返回的就能访问根结点。当搜索到某 P 结点时,先要遍历其左子树,因而将结点地址 P 及tag=0 进栈; */
    
    /* 当P 结点的左子树遍历完之后,再遍历其右子树,又将地址 P 及tag=1 进栈;当 P结点右子树遍历完之后( tag=1 ),便可对 P结点进行访问 */
    
    void PostTraverse(BiTree T)
    
    {
    
          int tag;
    
         BiNode *p;
    
         Stacks S;
    
         SNode sdata;
    
         S=InitStacks();
    
         p=T;
    
          while (p||!StacksEmpty(S))
    
         {
    
                while (p)
    
               {
    
                    sdata.q=p;
    
                    sdata.tag=0;
    
                    Pushs(S,&sdata);   //(p,0) 进栈
    
                    p=p->lchild;      // 遍历p 之左子树
    
               }
    
               sdata=*Pops(S);  // 退栈
    
               p=sdata.q;     // 取指针
    
               tag=sdata.tag; // 状态位
    
                if (tag==0)     //从左子树返回时,根的 tag=0
    
               {
    
                    sdata.q=p;
    
                    sdata.tag=1;      // 这时要进入根的右子树了,所以根的 tag=1 ,下次碰到根时就可以访问了
    
                    Pushs(S,&sdata);   //(p,1) 进栈,根还得进一次栈
    
                    p=p->rchild;     // 遍历右子树
    
               }
    
                else           //tag=1,这是说明了右子树访问完了返回,所以这次要对根进行访问了
    
               {
    
                    printf( '%c	' ,p->data);
    
                    p=NULL;
    
               }
    
         }
    
    }

     

    word-spacing: 0px; white-space: normal; orphans: 2; widows: 2; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;">二叉树的层次遍历
    // 二叉树的层次遍历
    
    void LevelTraverse(BiTree T)
    
    {
    
         BiNode *p;
    
         LinkQueue *Q;
    
         InitQueue(Q);
    
         EnQueue(Q,T);
    
          while (!QueueEmpty(Q))
    
         {
    
               p=DeQueue(Q);
    
               printf( '%c	' ,p->data);
    
                if (p->lchild!=NULL)
    
                    EnQueue(Q,p->lchild);
    
                if (p->rchild!=NULL)
    
                    EnQueue(Q,p->rchild);
    
         }
    
    }

     

    下面是完整代码:
      1 #include <stdio.h>
      2 
      3 #include <stdlib.h>
      4 
      5 #include <string.h>
      6 
      7 #include 'treenode.h'
      8 
      9 #include 'mystack.h'
     10 
     11 #include 'myqueue.h'
     12 
     13 #include 'newstack.h'
     14 
     15  
     16 
     17 //按照先序序列输入构建一棵二叉树
     18 
     19 void Create(BiTree &T)
     20 
     21 {
     22 
     23       char ch;
     24 
     25      scanf( '%c',&ch);
     26 
     27       if( '#' == ch )
     28 
     29      {
     30 
     31            T = NULL;
     32 
     33      }
     34 
     35       else
     36 
     37      {
     38 
     39            T=(BiNode *)malloc( sizeof(BiNode));
     40 
     41            T->data=ch;
     42 
     43            Create(T->lchild);
     44 
     45            Create(T->rchild);
     46 
     47      }
     48 
     49 }
     50 
     51  
     52 
     53 //二叉树的先序遍历
     54 
     55 void PreOrder(BiTree T)
     56 
     57 {
     58 
     59       if(T)
     60 
     61      {
     62 
     63            printf( '%c ',T->data);
     64 
     65            PreOrder(T->lchild);
     66 
     67            PreOrder(T->rchild);
     68 
     69      }
     70 
     71 }
     72 
     73  
     74 
     75 //二叉树先序遍历的非递归算法
     76 
     77 void PreTraverse(BiTree T)
     78 
     79 {
     80 
     81      BiNode *p;
     82 
     83      Stack S;
     84 
     85      S=InitStack();
     86 
     87       if(T)
     88 
     89      {
     90 
     91            Push(S,T);  //根结点指针进栈
     92 
     93             while(!StackEmpty(S))
     94 
     95            {
     96 
     97                 p=Pop(S);  //出栈,栈顶元素赋给p
     98 
     99                  while(p)
    100 
    101                 {
    102 
    103                      printf( '%c	',p->data);  // 访问p结点
    104 
    105                       if(p->rchild)
    106 
    107                            Push(S,p->rchild);  //右子树存在时,进栈
    108 
    109                      p=p->lchild;            //继续沿着左子树往下走
    110 
    111                 }
    112 
    113            }
    114 
    115      }
    116 
    117 }
    118 
    119  
    120 
    121 //二叉树的中序遍历
    122 
    123 void InOrder(BiTree T)
    124 
    125 {
    126 
    127       if(T)
    128 
    129      {
    130 
    131            InOrder(T->lchild);
    132 
    133            printf( '%c ',T->data);
    134 
    135            InOrder(T->rchild);
    136 
    137      }
    138 
    139 }
    140 
    141  
    142 
    143 //二叉树的中序遍历的非递归算法
    144 
    145 void InTraverse(BiTree T)
    146 
    147 {
    148 
    149      BiNode *p;
    150 
    151      Stack S;
    152 
    153      S=InitStack();
    154 
    155      Push(S,T);  //根结点指针进栈
    156 
    157       while(!StackEmpty(S))
    158 
    159      {
    160 
    161             while((p=GetsTop(S))&&p)  //取栈顶元素且存在,赋给 p
    162 
    163                 Push(S,p->lchild);    //p的左子树进栈
    164 
    165            p=Pop(S);               //去掉最后的空指针
    166 
    167             if(!StackEmpty(S))
    168 
    169            {
    170 
    171                 p=Pop(S);       //弹出栈顶元素,赋给p
    172 
    173                 printf( '%c	',p->data);   // 访问p结点
    174 
    175                 Push(S,p->rchild);     //右子树进栈,然后遍历右子树
    176 
    177            }
    178 
    179      }
    180 
    181 }
    182 
    183  
    184 
    185 //二叉树的后序遍历
    186 
    187 void PostOrder(BiTree T)
    188 
    189 {
    190 
    191       if(T)
    192 
    193      {
    194 
    195            PostOrder(T->lchild);
    196 
    197            PostOrder(T->rchild);
    198 
    199            printf( '%c ',T->data);
    200 
    201      }
    202 
    203 }
    204 
    205  
    206 
    207 void PostTraverse(BiTree T)
    208 
    209 {
    210 
    211       int tag;
    212 
    213      BiNode *p;
    214 
    215      Stacks S;
    216 
    217      SNode sdata;
    218 
    219      S=InitStacks();
    220 
    221      p=T;
    222 
    223       while(p||!StacksEmpty(S))
    224 
    225      {
    226 
    227             while(p)
    228 
    229            {
    230 
    231                 sdata.q=p;
    232 
    233                 sdata.tag=0;
    234 
    235                 Pushs(S,&sdata);   //(p,0)进栈
    236 
    237                 p=p->lchild;      //遍历p 之左子树
    238 
    239            }
    240 
    241            sdata=*Pops(S);  //退栈
    242 
    243            p=sdata.q;     //取指针
    244 
    245            tag=sdata.tag; //状态位
    246 
    247             if(tag==0)     //从左子树返回时,根的 tag=0
    248 
    249            {
    250 
    251                 sdata.q=p;
    252 
    253                 sdata.tag=1;      //这时要进入根的右子树了,所以根的 tag=1,下次碰到根时就可以访问了
    254 
    255                 Pushs(S,&sdata);   //(p,1)进栈,根还得进一次栈
    256 
    257                 p=p->rchild;     //遍历右子树
    258 
    259            }
    260 
    261             else          //tag=1,这是说明了右子树访问完了返回,所以这次要对根进行访问了
    262 
    263            {
    264 
    265                 printf( '%c	',p->data);
    266 
    267                 p=NULL;
    268 
    269            }
    270 
    271      }
    272 
    273 }
    274 
    275  
    276 
    277 //二叉树的层次遍历
    278 
    279 void LevelTraverse(BiTree T)
    280 
    281 {
    282 
    283      BiNode *p;
    284 
    285      LinkQueue *Q;
    286 
    287      InitQueue(Q);
    288 
    289      EnQueue(Q,T);
    290 
    291       while(!QueueEmpty(Q))
    292 
    293      {
    294 
    295            p=DeQueue(Q);
    296 
    297            printf( '%c	',p->data);
    298 
    299             if(p->lchild!=NULL)
    300 
    301                 EnQueue(Q,p->lchild);
    302 
    303             if(p->rchild!=NULL)
    304 
    305                 EnQueue(Q,p->rchild);
    306 
    307      }
    308 
    309 }
    310 
    311  
    312 
    313 int main()
    314 
    315 {
    316 
    317      BiTree T;
    318 
    319      Create(T);
    320 
    321      PostOrder(T);
    322 
    323      printf( '
    ');
    324 
    325      LevelTraverse(T);
    326 
    327      printf( '
    ');
    328 
    329      PostTraverse(T);
    330 
    331      printf( '
    ');
    332 
    333  
    334 
    335       return 0;
    336 
    337 }
    View Code

     

    /*测试数据*/ /* 分别是构建二叉树的输入数据以及先序、中序、后序、层次遍历序列: ABE##C#D##F#GH#I##J## ABECDFGHIJ EBCDAFHIGJ EDCBIGJGFA ABFECGDHJI  */ 图画得有点丑,见笑了。  
About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规