• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            jake1036

            樹的前中序遞歸非遞歸遍歷

                                                樹的前序與中序遍歷遞歸非遞歸遍歷

                 1樹的中序遍歷非遞歸算法思想:

                     每次都將左子樹入棧,一旦發現左子樹為空,則作出棧處理。打印該節點的值,然后右節點若不為空,則入棧處理。   
                 具體偽代碼如下:


               void BT_InOrderNoRec(pTreeT root)
            {
                stack
            <treeT *> s;
                
            while ((NULL != root) || !s.empty())
                
            {
                    
            if (NULL != root)
                    
            {
                        s.push(root);
                        root 
            = root->left;
                    }

                    
            else
                    
            {
                        root 
            = s.top();
                        visit(root);
                        s.pop();
                        root 
            = root->right;
                    }

                }

            }





            自己實現代碼(比較粗糙):

              void midStack(const int * a , int n)
              
            {
                 
            int i = 1 , top = 0;
                 
            int stack[n] ;
                 memset(stack , 
            0 , sizeof(stack)) ;   
                 stack[top
            ++= 1 ; 
                 
            while(top > 0)
                 
            {
                   
            int j = i * 2 ;                                      
                   
            while(j <= n && a[j] != 0)
                   
            {       
                     stack[top
            ++= j ; //左子樹入棧     
                     j *= 2 ;   
                   }
                                                            
                    i 
            = stack[--top] ;  
                    
            if(i <= n && a[i] !=  0)  
                      cout
            <<a[i]<<" " ; //輸出根 
                    
                    
            if(a[2 * i + 1 ] !=0 && 2 * i + 1 <= n)                 
                      stack[top
            ++= 2 * i + 1 ;
                    
                      i 
            = 2 * i + 1 ; //轉向右子樹 
                                                             
                        
                 }
              
                   
                   
              }



            2 非遞歸前序遍歷

            算法思想:


            順序訪問每個節點,然后將右節點插入棧中。然后將當前節點變換為左節點。知道當前節點為空,才會作出棧操作。
            偽代碼如下:
             void BT_PreOrderNoRec(pTreeT root)
            {
                stack
            <treeT *> s;

                
            while ((NULL != root) || !s.empty())
                
            {
                    
            if (NULL != root)
                    
            {
                        visit(root);
                        s.push(root);
                        root 
            = root->left;
                    }

                    
            else
                    
            {
                        root 
            = s.top();
                        s.pop();
                        root 
            = root->right;
                    }

                }

            }


            自己實現的代碼:

              void preStack(const int * a , int n)
              
            {
                 
            int i = 1 , top = 0;  
                 
            int stack[n] ;
                 stack[top
            ++= 1 ; 
                  
              
            while(top > 0)
              
            {    
                 i 
            = stack[--top] ;   
                 
            while( i <= n && a[i] != 0)
                 
            {
                   cout
            <<a[i]<<" " ; //輸出跟節點                                
                    i = i * 2 ; //轉到左節點     
                    stack[top++= i + 1 ;           // 將左右子樹入棧                     
                 }
                  
               }

                              
              }





             



             

            posted on 2011-04-10 10:42 kahn 閱讀(312) 評論(0)  編輯 收藏 引用 所屬分類: 算法相關

            狠色狠色狠狠色综合久久| 久久成人国产精品| 欧美激情精品久久久久久久九九九 | 久久久无码精品午夜| 久久精品中文字幕大胸| 久久99中文字幕久久| 久久99精品九九九久久婷婷| 色8激情欧美成人久久综合电| 婷婷久久久亚洲欧洲日产国码AV| 久久精品国产一区| 777午夜精品久久av蜜臀| 久久精品国产一区| 亚洲第一极品精品无码久久| 伊人久久大香线蕉影院95| 精品国产乱码久久久久久人妻 | 久久久久久av无码免费看大片| 久久久久久久波多野结衣高潮 | 久久婷婷成人综合色综合| 久久精品国产亚洲5555| 久久久久99精品成人片试看| 久久99热这里只有精品66| 人人狠狠综合久久亚洲| 韩国免费A级毛片久久| 天堂无码久久综合东京热| 99久久精品免费看国产免费| 精品无码久久久久国产| 亚洲国产精品无码久久久蜜芽| 亚洲国产成人久久精品99 | 日韩中文久久| 久久精品女人天堂AV麻| 色综合久久精品中文字幕首页| 久久99精品久久只有精品| 亚洲精品乱码久久久久久久久久久久| 久久99久久无码毛片一区二区| 韩国无遮挡三级久久| 国产精品视频久久| 久久这里只有精品久久| 色成年激情久久综合| 久久久WWW成人免费毛片| 久久一区二区免费播放| 亚洲欧美国产精品专区久久|