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

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿
            


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



            搜索
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



无码任你躁久久久久久|
国产精品无码久久久久久|
99久久国产综合精品成人影院|
伊人久久大香线蕉影院95|
天天影视色香欲综合久久|
久久精品国产色蜜蜜麻豆|
成人资源影音先锋久久资源网|
精品久久久久中文字|
久久综合九色综合网站|
韩国三级中文字幕hd久久精品|
中文字幕无码精品亚洲资源网久久|
久久久噜噜噜久久熟女AA片|
国产精品久久亚洲不卡动漫|
亚洲国产成人精品女人久久久|
97久久香蕉国产线看观看|
亚洲午夜精品久久久久久浪潮|
久久精品国产91久久麻豆自制|
国产精品乱码久久久久久软件|
久久99中文字幕久久|
伊人久久大香线蕉AV色婷婷色|
久久久久18|
国内精品久久久久久不卡影院|
a高清免费毛片久久|
久久亚洲欧美国产精品|
欧美伊人久久大香线蕉综合|
久久中文字幕视频、最近更新
|
久久精品国产亚洲精品|
婷婷久久久亚洲欧洲日产国码AV
|
久久人人爽人人爽人人片AV麻豆|
久久综合给合久久国产免费|
久久久久久久久66精品片|
久久久久婷婷|
久久综合精品国产一区二区三区|
久久亚洲欧美日本精品|
99久久免费国产精精品|
2021久久国自产拍精品|
久久狠狠色狠狠色综合|
久久亚洲国产中v天仙www|
久久精品中文字幕有码|
亚洲精品tv久久久久|
亚洲级αV无码毛片久久精品|