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


	


            
	    
    


            

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

            




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2025年5月>
            
	
            日一二三四五六
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿
            


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



            搜索
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



青草国产精品久久久久久|
国产亚洲美女精品久久久久狼|
伊人久久大香线蕉av不卡|
99久久www免费人成精品|
嫩草伊人久久精品少妇AV|
久久婷婷色综合一区二区|
人人妻久久人人澡人人爽人人精品|
久久精品国产黑森林|
久久国产成人午夜AV影院|
久久久久九九精品影院|
精品视频久久久久|
久久久久久亚洲精品无码|
亚洲国产精品一区二区三区久久
|
久久嫩草影院免费看夜色|
国产综合成人久久大片91|
国产精品嫩草影院久久|
久久久久香蕉视频|
热久久最新网站获取|
日韩精品久久无码中文字幕|
久久国产精品成人影院|
久久精品三级视频|
亚洲中文字幕无码久久综合网|
亚洲精品蜜桃久久久久久|
久久婷婷久久一区二区三区|
久久国产精品免费|
综合久久国产九一剧情麻豆|
国产精品久久久久aaaa|
日韩久久久久中文字幕人妻|
国产成人精品久久|
久久久久久久国产免费看|
亚洲精品乱码久久久久久按摩
|
亚洲国产成人乱码精品女人久久久不卡
|
欧美激情精品久久久久久久|
老男人久久青草av高清|
国产精品福利一区二区久久|
青春久久|
久久亚洲国产中v天仙www|
精品综合久久久久久98|
亚洲国产成人久久综合碰碰动漫3d
|
久久天天躁狠狠躁夜夜2020|
最新久久免费视频|