• <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 閱讀(1612) 評論(1)  編輯 收藏 引用  所屬分類: DataStructure 
		
            
	
            
	
	


	


            
	    
    


            

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

            




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2012年11月>
            
	
            日一二三四五六
            28293031123
            45678910
            11121314151617
            18192021222324
            2526272829301
            2345678
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿
            


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



            搜索
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久国产亚洲精品|
久久久久99精品成人片|
欧美激情一区二区久久久|
国产精品嫩草影院久久|
久久精品亚洲男人的天堂|
人妻无码久久精品|
亚洲va久久久噜噜噜久久天堂|
99久久国产亚洲综合精品|
久久亚洲精品国产精品|
亚洲天堂久久精品|
亚洲国产高清精品线久久|
天天躁日日躁狠狠久久|
欧美777精品久久久久网|
欧美日韩精品久久久久|
国产成人久久精品一区二区三区|
国产精品久久波多野结衣|
久久精品国产清自在天天线|
99久久夜色精品国产网站|
热久久国产精品|
性欧美丰满熟妇XXXX性久久久
|
久久久久人妻一区二区三区vr|
精品无码久久久久国产|
免费一级做a爰片久久毛片潮|
久久国产免费观看精品3|
久久国产成人精品国产成人亚洲|
久久中文骚妇内射|
亚洲国产成人久久综合碰|
亚洲综合婷婷久久|
激情伊人五月天久久综合|
久久婷婷色综合一区二区|
狠狠色综合网站久久久久久久|
人妻精品久久无码区|
综合久久精品色|
久久久久国产|
久久久久久国产精品无码下载
|
久久精品www人人爽人人|
一本色道久久99一综合|
国内精品久久久久影院老司|
精品久久久久一区二区三区
|
成人精品一区二区久久久|
国产精品禁18久久久夂久|