• <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)  編輯 收藏 引用 所屬分類: 算法相關

            四虎国产精品免费久久5151| www性久久久com| 嫩草影院久久99| 久久97久久97精品免视看| 亚洲va久久久久| 久久国产精品无码一区二区三区 | 天天躁日日躁狠狠久久| 久久av无码专区亚洲av桃花岛| 996久久国产精品线观看| 色偷偷88欧美精品久久久| 久久人妻少妇嫩草AV无码专区| 狠狠色综合网站久久久久久久| 久久婷婷五月综合国产尤物app| 久久精品国产影库免费看| 欧美日韩久久中文字幕| 久久精品视频91| 久久国产精品一区二区| 亚洲国产精品无码久久一区二区| 国产精品99久久久久久董美香| 久久精品国产亚洲AV麻豆网站| 一本久久a久久精品综合香蕉| 亚洲国产成人久久综合碰碰动漫3d| 久久免费看黄a级毛片| 国内精品久久久久久久久电影网| 久久精品人人做人人爽97| 7777久久久国产精品消防器材| 久久综合伊人77777| 精品视频久久久久| 国产精品热久久毛片| 青青草国产精品久久久久| 久久偷看各类wc女厕嘘嘘 | 久久精品国产精品亚洲毛片 | 五月丁香综合激情六月久久| 午夜精品久久久久久影视riav| 一本一道久久精品综合| 91久久精品无码一区二区毛片| 成人久久综合网| 久久精品国产一区二区三区日韩| 国产精品久久久久影院色| 久久成人国产精品二三区| 91精品观看91久久久久久|