• <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>
            

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			二叉樹前序，中序，后序遍歷的非遞歸實現（c++版）
		
            
		
            1. 二叉樹后序非遞歸遍歷：
            

             1#include <stack>
             2#include <iostream>
             3using namespace std;
             4
             5template <class T>
             6class TreeNode
             7{
             8  public:
             9    T data;
            10    TreeNode<T> *left; //left child
            11    TreeNode<T> *right; //right child
            12 
            13    TreeNode():left(NULL),right(NULL)
            14    {
            15    }
            16
            17    TreeNode(const T& t):data(t),left(NULL), right(NULL)
            18    {
            19    }
            20
            21    TreeNode(const T& t, TreeNode<T*> left, TreeNode<T*> right):data(t),left(left), right(right)
            22    {
            23    }
            24}            ;
            25
            26/**purpose: 對二叉樹進行后序遍歷（非遞歸算法）
            27 TreeNode<T> *root :the root of the binary tree
            28  */
            29template <class T>
            30void postOrder(TreeNode<T> *root)
            31{
            32  stack<TreeNode<T>*> st;
            33  TreeNode<T> *p = root;
            34  TreeNode<T> *pre = NULL;//pre表示最近一次訪問的結點
            35 
            36  while(p || st.size()!=0)
            37  {
            38    //沿著左孩子方向走到最左下 。
            39    while(p)
            40    {
            41      st.push(p);
            42      p = p->left;
            43    }
            44    //get the top element of the stack
            45    p = st.top();
            46    //如果p沒有右孩子或者其右孩子剛剛被訪問過，則訪問p節點，并從棧中刪除
            47   if(p->right == NULL || p->right == pre)
            48    {
            49      //visit this element and then pop it
            50      cout << "visit: " << p->data << endl;
            51      st.pop();
            52      pre = p; //標記最近被訪問的節點
            53      p = NULL; //這樣，接下來可以訪問父節點
            54     
            55    }
            56   else
            57   {
            58     p = p->right;
            59    
            60   }
            61  }            //end of while(p || st.size()!=0)
            62
            63}
            64
            65
            


            2.二叉樹前序非遞歸遍歷：
            

             1template <class T>
             2void PreOrder(TreeNode<T> *root)const
             3{
             4    stack<TreeNode<T>*> st;
             5    TreeNode<T>* p=root;
             6
             7    while (!st.empty()||p!=NULL)
             8    {
             9        while(p)   //沿左子樹到底，訪問途中結點并壓棧保存
            10        {
            11            cout<<"visit:"<<p->data<<endl;
            12            st.push(p);
            13            p=p->left;
            14        }
            15
            16        p=st.top(); //將父結點出棧，對右子樹訪問
            17        st.pop();
            18        p=p->right;        
            19
            20    }
            21
            22
            23}
            

            3.二叉樹中序非遞歸遍歷：
             
            

             1void InOrder(TreeNode<T>*root)const
             2{
             3    stack<TreeNode<T>*> st;
             4    TreeNode<T>* p=root;
             5    while (!st.empty()||p!=NULL)
             6    {
             7        while(p)//沿左子樹到底，將途中結點壓棧保存，不訪問
             8        {
             9            st.push(p);
            10            p=p->left;
            11        }
            12        p=st.top();
            13        cout<<"visit:"<<p->data<<endl; //此時訪問，實現中序
            14        st.pop();
            15        p=p->right;
            16
            17    }
            18
            19}
            

		
            
			posted on 2010-10-22 19:05 oliver 閱讀(1625) 評論(1)  編輯 收藏 引用  所屬分類: DataStructure 
		
            
	
            
	
	


	


            
	    
    


            

            評論
            
	
	
			
            
				# re: 二叉樹前序，中序，后序遍歷的非遞歸實現（c++版）
					
						2012-11-22 23:11
					
				missgya
			
            
			
            
				看了這么多，發現閣下的后序遍歷寫得最漂亮。  回復  更多評論
				  
			
            
		

            




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年10月>
            
	
            日一二三四五六
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿
            


		
            隨筆檔案
            
		
				
			
	
		
            文章分類
            
		
				
			
	
		
            文章檔案
            
		
				
			
	
		
            個人專欄
            
		
				
			
	
		
            技術網站
            
		
				
			
	



            搜索
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久久久久久综合日本|
久久中文骚妇内射|
日韩影院久久|
久久人人爽人人爽人人片AV不
|
91精品国产91久久综合|
国产成人综合久久久久久|
婷婷久久五月天|
一级做a爱片久久毛片|
亚洲熟妇无码另类久久久|
久久精品女人天堂AV麻|
久久久噜噜噜久久熟女AA片|
精品久久久久久国产三级|
久久超乳爆乳中文字幕|
日韩久久无码免费毛片软件|
久久99精品久久只有精品|
久久人人爽人人爽人人片AV东京热|
久久久久久综合一区中文字幕|
欧美伊人久久大香线蕉综合
|
伊人久久久AV老熟妇色|
久久无码国产|
国产视频久久|
99久久人妻无码精品系列蜜桃|
久久99精品久久久大学生|
久久亚洲av无码精品浪潮|
久久99精品免费一区二区|
亚洲狠狠综合久久|
久久线看观看精品香蕉国产|
久久国产精品77777|
国产精品美女久久久久|
三上悠亚久久精品|
久久精品无码午夜福利理论片|
久久精品人人做人人爽电影|
精品国产青草久久久久福利|
亚洲成av人片不卡无码久久|
欧美亚洲另类久久综合婷婷
|
午夜不卡久久精品无码免费|
亚洲色大成网站WWW久久九九|
亚洲精品无码久久久久久|
麻豆一区二区99久久久久|
久久99精品国产一区二区三区|
久久99国产亚洲高清观看首页|