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

    
            

            




            







												


        

            
	
            
		
			

            

            
	
            
		
			
            那誰的技術博客
            
			感興趣領域:高性能服務器編程,存儲,算法,Linux內核
		            		
	
            

            

            

            

            隨筆 - 210, 文章 - 0, 評論 - 1183, 引用 - 0
            

            


            		
	
            

            

            
	
            
		
			
            
				數據加載中……
			
            
		            		
		
			
            
				
					
	
            
		
            
			二叉樹遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)
		
            
		
            
		
		費了兩天時間寫的,包括前中后序遍歷的遞歸和非遞歸算法,還有層序遍歷總共2*3 + 1 = 7中遍歷二叉樹的算法,感覺其中后序遍歷的非遞歸算法比較困難,想了很久最后的實現還是不夠優雅,請大家指正~~

            總共三個文件,一個頭文件,一個對應的cpp文件,還有一個用于測試的文件.

            頭文件:
            /********************************************************************
            ????created:????2006/07/04
            ????filename:?????BinaryTree.h
            ????author:????????李創
            ????????????????            http://www.shnenglu.com/converse/

            ????purpose:????演示二叉樹的算法
            ********************************************************************            */

            #ifndef?BinaryTree_H
            #define?BinaryTree_H

            #include?            <stdlib.h>
            #include?            <stack>

            class?BinaryTree
            {
            private:
            ????typedef?            int?Item;
            ????typedef?            struct?TreeNode
            ????            {
            ????????Item????????Node;
            ????????TreeNode            *???pRight;
            ????????TreeNode            *???pLeft;

            ????????TreeNode(Item?node?            =?0,?TreeNode*?pright?=?NULL,?TreeNode*?pleft?=?NULL)
            ????????????:?Node(node)
            ????????????,?pRight(pright)
            ????????????,?pLeft(pleft)
            ????????            {
            ????????}

            ????}            TreeNode,?*PTreeNode;

            public:
            ????            enum?TraverseType
            ????            {
            ????????PREORDER????            =?0,????????//?前序
            ????????INORDER????????=?1,????????//?中序
            ????????POSTORDER????=?2,????????//?后序
            ????????LEVELORDER????=?3????????????//?層序
            ????}            ;

            ????BinaryTree(Item?Array[],?            int?nLength);
            ????            ~BinaryTree();

            ????PTreeNode?GetRoot()
            ????            {
            ????????            return?m_pRoot;
            ????}

            ????            //?遍歷樹的對外接口
            ????            //?指定遍歷類型和是否是非遞歸遍歷,默認是遞歸遍歷
            ????void?Traverse(TraverseType?traversetype,?bool?bRec?=?true);

            private:
            ????PTreeNode???CreateTreeImpl(Item?Array[],?            int?nLength);
            ????            void????????DetroyTreeImpl(PTreeNode?pTreenode);

            ????            void????????PreTraverseImpl(PTreeNode?pTreenode);????????//?遞歸前序遍歷樹
            ????void????????InTraverseImpl(PTreeNode?pTreenode);????????//?遞歸中序遍歷樹
            ????void????????PostTraverseImpl(PTreeNode?pTreenode);????????//?遞歸后序遍歷樹

            ????            void????????NoRecPreTraverseImpl(PTreeNode?pTreenode);????//?非遞歸前序遍歷樹
            ????void????????NoRecInTraverseImpl(PTreeNode?pTreenode);????//?非遞歸中序遍歷樹
            ????void????????NoRecPostTraverseImpl(PTreeNode?pTreenode);????//?非遞歸后序遍歷樹

            ????            void????????LevelTraverseImpl(PTreeNode?pTreenode);

            ????PTreeNode???m_pRoot;????????            //?根結點

            ????            //?采用STL里面的stack作為模擬保存鏈表結點的stack容器
            ????typedef?std::stack<BinaryTree::PTreeNode>?TreeNodeStack;
            }            ;

            #endif


            實現文件:
            /********************************************************************
            ????created:????2006/07/04
            ????filename:?????BinaryTree.cpp
            ????author:????????李創
            ????????????????            http://www.shnenglu.com/converse/

            ????purpose:????演示二叉樹的算法
            ********************************************************************            */

            #include?            <iostream>
            #include?            <assert.h>
            #include?            <queue>
            #include?            "BinaryTree.h"

            BinaryTree::BinaryTree(Item?Array[],?            int?nLength)
            ????:?m_pRoot(NULL)
            {
            ????assert(NULL?            !=?Array);
            ????assert(nLength?            >?0);

            ????m_pRoot?            =?CreateTreeImpl(Array,?nLength);
            }

            BinaryTree::            ~BinaryTree()
            {
            ????DetroyTreeImpl(m_pRoot);
            }

            //?按照中序遞歸創建樹
            BinaryTree::PTreeNode?BinaryTree::CreateTreeImpl(Item?Array[],?int?nLength)
            {
            ????            int?mid?=?nLength?/?2;
            ????PTreeNode?p?            =?new?TreeNode(Array[mid]);

            ????            if?(nLength?>?1)
            ????            {
            ????????p            ->pLeft????=?CreateTreeImpl(Array,?nLength?/?2);
            ????????p            ->pRight???=?CreateTreeImpl(Array?+?mid?+?1,?nLength?/?2?-?1);
            ????}

            ????            return?p;
            }

            void?BinaryTree::DetroyTreeImpl(PTreeNode?pTreenode)
            {
            ????            if?(NULL?!=?pTreenode->pLeft)
            ????            {
            ????????DetroyTreeImpl(pTreenode            ->pLeft);
            ????}
            ????            if?(NULL?!=?pTreenode->pRight)
            ????            {
            ????????DetroyTreeImpl(pTreenode            ->pRight);
            ????}

            ????delete?pTreenode;
            ????pTreenode?            =?NULL;
            }

            //?遍歷樹的對外接口
            //?指定遍歷類型和是否是非遞歸遍歷,默認是遞歸遍歷
            void?BinaryTree::Traverse(TraverseType?traversetype,?bool?bRec?/*=?true*/)
            {
            ????            switch?(traversetype)
            ????            {
            ????            case?PREORDER:????//?前序
            ????????{????????????
            ????????????            if?(true?==?bRec)
            ????????????            {
            ????????????????std::cout?            <<?"遞歸前序遍歷樹\n";
            ????????????????PreTraverseImpl(m_pRoot);
            ????????????}
            ????????????            else
            ????????????            {
            ????????????????std::cout?            <<?"非遞歸前序遍歷樹\n";
            ????????????????NoRecPreTraverseImpl(m_pRoot);
            ????????????}
            ????????}
            ????????            break;

            ????            case?INORDER:????//?中序
            ????????{????????????
            ????????????            if?(true?==?bRec)
            ????????????            {
            ????????????????std::cout?            <<?"遞歸中序遍歷樹\n";
            ????????????????InTraverseImpl(m_pRoot);
            ????????????}
            ????????????            else
            ????????????            {
            ????????????????std::cout?            <<?"非遞歸中序遍歷樹\n";
            ????????????????NoRecInTraverseImpl(m_pRoot);
            ????????????}
            ????????}
            ????????            break;

            ????            case?POSTORDER:????//?后序
            ????????{????????????
            ????????????            if?(true?==?bRec)
            ????????????            {
            ????????????????std::cout?            <<?"遞歸后序遍歷樹\n";
            ????????????????PostTraverseImpl(m_pRoot);
            ????????????}
            ????????????            else
            ????????????            {
            ????????????????std::cout?            <<?"非遞歸后序遍歷樹\n";
            ????????????????NoRecPostTraverseImpl(m_pRoot);
            ????????????}
            ????????}
            ????????            break;

            ????            case?LEVELORDER:????//?層序
            ????????{
            ????????????std::cout?            <<?"層序遍歷樹\n";
            ????????????LevelTraverseImpl(m_pRoot);
            ????????}
            ????}

            ????std::cout?            <<?std::endl;
            }

            //?遞歸前序遍歷樹
            void?BinaryTree::PreTraverseImpl(PTreeNode?pTreenode)
            {
            ????            if?(NULL?==?pTreenode)
            ????????            return;

            ????std::cout?            <<?"Item?=?"?<<?pTreenode->Node?<<?std::endl;

            ????PreTraverseImpl(pTreenode            ->pLeft);

            ????PreTraverseImpl(pTreenode            ->pRight);
            }

            //?非遞歸前序遍歷樹
            void?BinaryTree::NoRecPreTraverseImpl(PTreeNode?pTreenode)
            {
            ????            if?(NULL?==?pTreenode)
            ????????            return;

            ????TreeNodeStack?NodeStack;
            ????PTreeNode?pNode;
            ????NodeStack.push(pTreenode);

            ????            while?(!NodeStack.empty())
            ????            {
            ????????            while?(NULL?!=?(pNode?=?NodeStack.top()))????//?向左走到盡頭
            ????????{
            ????????????std::cout?            <<?"Item?=?"?<<?pNode->Node?<<?std::endl;????//?訪問當前結點
            ????????????NodeStack.push(pNode->pLeft);????????????????????//?左子樹根結點入棧
            ????????}
            ????????NodeStack.pop();????????????????????????????????????            //?左子樹根結點退棧
            ????????if?(!NodeStack.empty())
            ????????            {
            ????????????pNode?            =?NodeStack.top();
            ????????????NodeStack.pop();????????????????????????????????            //?當前結點退棧
            ????????????NodeStack.push(pNode->pRight);????????????????//?當前結點的右子樹根結點入棧
            ????????}
            ????}
            }

            //?中序遍歷樹
            //?中序遍歷輸出的結果應該和用來初始化樹的數組的排列順序一致
            void?BinaryTree::InTraverseImpl(PTreeNode?pTreenode)
            {
            ????            if?(NULL?==?pTreenode)
            ????????            return;

            ????            if?(NULL?!=?pTreenode->pLeft)
            ????            {
            ????????InTraverseImpl(pTreenode            ->pLeft);
            ????}

            ????std::cout?            <<?"Item?=?"?<<?pTreenode->Node?<<?std::endl;

            ????            if?(NULL?!=?pTreenode->pRight)
            ????            {
            ????????InTraverseImpl(pTreenode            ->pRight);
            ????}
            }

            //?非遞歸中序遍歷樹
            void?BinaryTree::NoRecInTraverseImpl(PTreeNode?pTreenode)
            {
            ????            if?(NULL?==?pTreenode)
            ????????            return;

            ????TreeNodeStack?NodeStack;
            ????PTreeNode?pNode;
            ????NodeStack.push(pTreenode);

            ????            while?(!NodeStack.empty())
            ????            {
            ????????            while?(NULL?!=?(pNode?=?NodeStack.top()))????//?向左走到盡頭
            ????????{
            ????????????NodeStack.push(pNode            ->pLeft);
            ????????}

            ????????NodeStack.pop();

            ????????            if?(!NodeStack.empty()?&&?NULL?!=?(pNode?=?NodeStack.top()))
            ????????            {
            ????????????std::cout?            <<?"Item?=?"?<<?pNode->Node?<<?std::endl;
            ????????????NodeStack.pop();
            ????????????NodeStack.push(pNode            ->pRight);
            ????????}
            ????}
            }

            //?后序遍歷樹
            void?BinaryTree::PostTraverseImpl(PTreeNode?pTreenode)
            {
            ????            if?(NULL?==?pTreenode)
            ????????            return;

            ????            if?(NULL?!=?pTreenode->pLeft)
            ????            {
            ????????PostTraverseImpl(pTreenode            ->pLeft);
            ????}

            ????            if?(NULL?!=?pTreenode->pRight)
            ????            {
            ????????PostTraverseImpl(pTreenode            ->pRight);
            ????}

            ????std::cout?            <<?"Item?=?"?<<?pTreenode->Node?<<?std::endl;
            }

            //?非遞歸后序遍歷樹
            void?BinaryTree::NoRecPostTraverseImpl(PTreeNode?pTreenode)
            {
            ????            if?(NULL?==?pTreenode)
            ????????            return;

            ????TreeNodeStack?NodeStack;
            ????PTreeNode?pNode1,?pNode2;
            ????NodeStack.push(pTreenode);
            ????pNode1?            =?pTreenode->pLeft;
            ????
            ????            bool?bVisitRoot?=?false;????????????//?標志位,是否訪問過根結點
            ????while?(!NodeStack.empty())
            ????            {
            ????????            while?(NULL?!=?pNode1)????????????//?向左走到盡頭
            ????????{
            ????????????NodeStack.push(pNode1);
            ????????????pNode1?            =?pNode1->pLeft;
            ????????}

            ????????pNode1?            =?NodeStack.top();
            ????????NodeStack.pop();

            ????????            if?(NULL?==?pNode1->pRight)????????????//?如果沒有右子樹就是葉子結點
            ????????{
            ????????????std::cout?            <<?"Item?=?"?<<?pNode1->Node?<<?std::endl;
            ????????????pNode2?            =?pNode1;
            ????????????pNode1?            =?NodeStack.top();

            ????????????            if?(pNode2?==?pNode1->pRight)????//?如果這個葉子結點是右子樹
            ????????????{
            ????????????????std::cout?            <<?"Item?=?"?<<?pNode1->Node?<<?std::endl;
            ????????????????NodeStack.pop();
            ????????????????pNode1?            =?NULL;
            ????????????}
            ????????????            else????????????????????????????//?否則訪問右子樹
            ????????????{
            ????????????????pNode1?            =?pNode1->pRight;
            ????????????}
            ????????}
            ????????            else????????????????????????????????//?訪問右子樹
            ????????{
            ????????????            if?(pNode1?==?pTreenode?&&?true?==?bVisitRoot)????//?如果已經訪問過右子樹那么就退出
            ????????????{
            ????????????????std::cout?            <<?"Item?=?"?<<?pNode1->Node?<<?std::endl;
            ????????????????            return;
            ????????????}
            ????????????            else
            ????????????            {
            ????????????????            if?(pNode1?==?pTreenode)
            ????????????????            {
            ????????????????????bVisitRoot?            =?true;
            ????????????????}

            ????????????????NodeStack.push(pNode1);
            ????????????????pNode1?            =?pNode1->pRight;
            ????????????}
            ????????}
            ????}
            }

            //?按照樹的層次從左到右訪問樹的結點
            void?BinaryTree::LevelTraverseImpl(PTreeNode?pTreenode)
            {
            ????            if?(NULL?==?pTreenode)
            ????????            return;

            ????            //?層序遍歷用于保存結點的容器是隊列
            ????std::queue<PTreeNode>?NodeQueue;
            ????PTreeNode?pNode;
            ????NodeQueue.push(pTreenode);

            ????            while?(!NodeQueue.empty())
            ????            {
            ????????pNode?            =?NodeQueue.front();
            ????????NodeQueue.pop();
            ????????std::cout?            <<?"Item?=?"?<<?pNode->Node?<<?std::endl;

            ????????            if?(NULL?!=?pNode->pLeft)
            ????????            {
            ????????????NodeQueue.push(pNode            ->pLeft);????
            ????????}
            ????????            if?(NULL?!=?pNode->pRight)
            ????????            {
            ????????????NodeQueue.push(pNode            ->pRight);
            ????????}            ????
            ????}
            }
            
		
            測試文件:
            /********************************************************************
            ????created:????2006/07/04
            ????filename:?????main.cpp
            ????author:????????李創
            ????????????????            http://www.shnenglu.com/converse/

            ????purpose:????測試二叉樹的算法
            ********************************************************************            */

            #include?            "BinaryTree.h"

            #include?            <stdio.h>
            #include?            <stdlib.h>
            #include?            <time.h>
            #include?            <iostream>

            void?DisplayArray(int?array[],?int?length)
            {
            ????            int?i;

            ????            for?(i?=?0;?i?<?length;?i++)
            ????            {
            ????????printf(            "array[%d]?=?%d\n",?i,?array[i]);
            ????}
            }

            void?CreateNewArray(int?array[],?int?length)
            {
            ????            for?(int?i?=?0;?i?<?length;?i++)
            ????            {
            ????????array[i]?            =?rand()?%?256?+?i;
            ????}
            }

            int?main()
            {
            ????            int?array[10];
            ????srand(time(NULL));

            ????            //?創建數組
            ????CreateNewArray(array,?10);
            ????DisplayArray(array,?            10);

            ????BinaryTree?            *pTree?=?new?BinaryTree(array,?10);

            ????            //?測試前序遍歷
            ????pTree->Traverse(BinaryTree::PREORDER);
            ????std::cout?            <<?"root?=?"?<<?pTree->GetRoot()->Node?<<?std::endl;
            ????std::cout?            <<?"root->left?=?"?<<?pTree->GetRoot()->pLeft->Node?<<?std::endl;
            ????std::cout?            <<?"root->right?=?"?<<?pTree->GetRoot()->pRight->Node?<<?std::endl;
            ????pTree            ->Traverse(BinaryTree::PREORDER,?false);
            ????
            ????            //?測試中序遍歷
            ????pTree->Traverse(BinaryTree::INORDER);
            ????std::cout?            <<?"root?=?"?<<?pTree->GetRoot()->Node?<<?std::endl;
            ????std::cout?            <<?"root->left?=?"?<<?pTree->GetRoot()->pLeft->Node?<<?std::endl;
            ????std::cout?            <<?"root->right?=?"?<<?pTree->GetRoot()->pRight->Node?<<?std::endl;
            ????pTree            ->Traverse(BinaryTree::INORDER,?false);
            ????            //?測試后序遍歷
            ????pTree->Traverse(BinaryTree::POSTORDER);
            ????std::cout?            <<?"root?=?"?<<?pTree->GetRoot()->Node?<<?std::endl;
            ????std::cout?            <<?"root->left?=?"?<<?pTree->GetRoot()->pLeft->Node?<<?std::endl;
            ????std::cout?            <<?"root->right?=?"?<<?pTree->GetRoot()->pRight->Node?<<?std::endl;
            ????pTree            ->Traverse(BinaryTree::POSTORDER,?false);
            ????            //?測試層序遍歷
            ????pTree->Traverse(BinaryTree::LEVELORDER);

            ????system(            "pause");
            ????
            ????delete?pTree;

            ????            return?0;
            }
            
		
            
		
            
			posted on 2006-07-08 15:21 那誰 閱讀(20249) 評論(9)  編輯 收藏 引用  所屬分類: 算法與數據結構 
		
            
	
            
	
	


	


            
	    
    


            

            評論
            
	
	
			
            
				
            
					# re: 二叉樹遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)  回復  更多評論
					  
				
            
				good
				
            
					2007-06-16 18:04 | superdaxia
				
            
			
            
		
			
            
				
            
					# re: 二叉樹遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)  回復  更多評論
					  
				
            
				你好,我是新手,在用VC調試時發現錯誤

            f:\hwh\二叉樹\binarytree.h(64) : error C2027: use of undefined type 'BinaryTree'

                    f:\hwh\二叉樹\binarytree.h(8) : see declaration of 'BinaryTree'

            main.cpp

            f:\hwh\二叉樹\binarytree.h(64) : error C2027: use of undefined type 'BinaryTree'

                    f:\hwh\二叉樹\binarytree.h(8) : see declaration of 'BinaryTree'

            執行 cl.exe 時出錯.

            

            二叉樹.exe - 1 error(s), 0 warning(s)

            為什么呢?
				
            
					2007-12-25 11:37 | tomy
				
            
			
            
		
			
            
				
            
					# re: 二叉樹遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)  回復  更多評論
					  
				
            
				@tomy

            你用的什么編譯器?我用的VS2003,其次,你的工程里面有幾個文件?這里一共有三個文件:binarytree.h,binarytree.cpp,main.cpp
				
            
					2007-12-26 11:18 | 創系
				
            
			
            
		
			
            
				
            
					# re: 二叉樹遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)[未登錄]  回復  更多評論
					  
				
            
				我用DEV C++編譯后報以下信息,請指教:

            

            C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp/cceIaaaa.o(.text+0x52d):main.cpp: undefined reference to `BinaryTree::Traverse(BinaryTree::TraverseType, bool)'

            C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp/cceIaaaa.o(.text+0x62f):main.cpp: more undefined references to `BinaryTree::Traverse(BinaryTree::TraverseType, bool)' follow

            C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp/cceIaaaa.o(.text+0x676):main.cpp: undefined reference to `BinaryTree::~BinaryTree()'

            collect2: ld returned 1 exit status
				
            
					2008-01-06 01:10 | ben
				
            
			
            
		
			
            
				
            
					# re: 二叉樹遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)  回復  更多評論
					  
				
            
				樓上的錯誤是DEV C++的工程文件/配置文件的問題吧?
				
			
            
		
			
            
				
            
					# re: 二叉樹遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)[未登錄]  回復  更多評論
					  
				
            
				已經解決了,謝謝指點!
				
            
					2008-01-06 15:19 | ben
				
            
			
            
		
			
            
				
            
					# re: 二叉樹遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)  回復  更多評論
					  
				
            
				請問，為什么我的窗口上什么都米有？只有一個“請按任意鍵繼續”，用的是VC++ 2008
				
            
					2008-07-09 07:03 | liuyu
				
            
			
            
		
			
            
				
            
					# re: 二叉樹遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)  回復  更多評論
					  
				
            
				其實如果不用 Stack 而改用 List 的話，三種非遞歸遍歷將變得更加簡單一致，一個 While 就夠了

            

                typedef std::list<BinaryTree::PTreeNode> TreeNodeList;

            

                typedef struct TreeNode

                {

                    Item        Node;

                    TreeNode*   pRight;

                    TreeNode*   pLeft;

                    bool	bVisited;       // 關鍵

            

                    TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)

                        : Node(node)

                        , pRight(pright)

                        , pLeft(pleft)

                        , bVisited(false)

                    {

                    }

            

                }TreeNode, *PTreeNode;

            

            

            

            

            // 非遞歸前序遍歷樹

            void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)

            {

                if (NULL == pTreenode)

                    return;

            

                TreeNodeList NodeList;

                PTreeNode pNode;

                NodeList.push_front(pTreenode);

            

                while (!NodeList.empty())

                {

            		pNode = NodeList.front();

            		NodeList.pop_front();

            

            		std::cout << "Item = " << pNode->Node << std::endl;

            

            		if(pNode->pRight != NULL) NodeList.push_front(pNode->pRight);

            		if(pNode->pLeft != NULL) NodeList.push_front(pNode->pLeft);

                }

            }

            

            

            // 非遞歸中序遍歷樹

            void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)

            {

                if (NULL == pTreenode)

                    return;

            

                TreeNodeList NodeList;

                PTreeNode pNode;

                NodeList.push_front(pTreenode);

            

                while (!NodeList.empty())

                {

            		pNode = NodeList.front();

            	

            		if(pNode->bVisited)

            		{

            			NodeList.pop_front();

            			pNode->bVisited = false;			// 為下一次遍歷做準備

            

            			std::cout << "Item = " << pNode->Node << std::endl;

            			

            			if(pNode->pRight != NULL) NodeList.push_front(pNode->pRight);

            		}

            		else

            		{

            			if(pNode->pLeft != NULL) NodeList.push_front(pNode->pLeft);

            			pNode->bVisited = true;

            		}

            

                }

            }

            

            // 非遞歸后序遍歷樹

            void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)

            {

                if (NULL == pTreenode)

                    return;

            

                TreeNodeList NodeList;

                PTreeNode pNode;

            	NodeList.push_front(pTreenode);

            

                while (!NodeList.empty())

                {

            		pNode = NodeList.front();

            	

            		if(pNode->bVisited)

            		{

            			NodeList.pop_front();

            			pNode->bVisited = false;			// 為下一次遍歷做準備

            

            			std::cout << "Item = " << pNode->Node << std::endl;

            		}

            		else

            		{

            			if(pNode->pRight != NULL) NodeList.push_front(pNode->pRight);

            			if(pNode->pLeft != NULL) NodeList.push_front(pNode->pLeft);

            			pNode->bVisited = true;

            		}

            

                }

            }

            

            

            
				
            
					2008-09-08 22:58 | Godspeed
				
            
			
            
		
			
            
				
            
					# re: 二叉樹遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)[未登錄]  回復  更多評論
					  
				
            
				非遞歸后續遍歷修改為：

            public static void iterativePostorder(BinaryTree boot) {

            		Stack<BinaryTree> stack = new Stack<BinaryTree>();

            		BinaryTree current, pointer=boot;

            		boolean bVisitRoot = false;//標志是否訪問過根節點

            		if (boot == null) {

            			return;

            		}

            		stack.push(boot);

            		current = boot.leftpoiter;

            		while (!stack.empty()) {

            			while (current != null) {//向左走到盡頭

            				stack.push(current);

            				current = current.leftpoiter;

            			}

            			current = stack.peek();

            			stack.pop();

            			if ((current.rightpoiter == null)||(pointer == current.rightpoiter)) {

            				visit(current);

            				pointer = current;

            				current = stack.peek();

            				if (pointer == current.rightpoiter) {

            					visit(current);

            					stack.pop();

            					pointer=current;

            					current = null;

            				} else {

            					current = current.rightpoiter;

            				}

            			} else {

            				if (current == boot && (bVisitRoot == true)) {

            					visit(current);

            					return;

            				} else {

            					if (current == boot) {

            						bVisitRoot = true;

            					}

            					stack.push(current);

            					current = current.rightpoiter;

            				}

            			}

            

            		}

            

            	}
				
            
					2011-07-07 11:12 | hepeng
				
            
			
            
		

            





            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



2022年国产精品久久久久|
久久亚洲电影|
国内精品久久国产|
午夜精品久久久久成人|
久久精品中文字幕久久|
亚洲成色999久久网站|
久久免费线看线看|
久久九九青青国产精品|
久久91综合国产91久久精品|
久久国产精品无码HDAV|
国产午夜精品久久久久免费视
|
久久狠狠爱亚洲综合影院|
亚洲人成无码久久电影网站|
无码精品久久一区二区三区|
久久免费视频6|
99久久做夜夜爱天天做精品|
亚洲综合日韩久久成人AV|
亚洲精品无码久久久久sm|
久久久久久久久无码精品亚洲日韩
|
久久九九精品99国产精品|
国产精品久久久久久久久免费|
99久久精品免费看国产免费|
久久成人18免费网站|
精品久久久久久中文字幕大豆网|
午夜久久久久久禁播电影|
伊人丁香狠狠色综合久久|
性做久久久久久久久久久|
久久综合狠狠综合久久|
国产精品九九久久免费视频
|
久久久久久久久久久久中文字幕
|
亚洲国产精品久久久久婷婷老年|
久久影院午夜理论片无码|
色偷偷88888欧美精品久久久|
久久久久综合网久久|
一本一道久久a久久精品综合
|
久久无码人妻一区二区三区午夜|
日本福利片国产午夜久久|
久久伊人五月丁香狠狠色|
伊人久久大香线焦综合四虎|
AV无码久久久久不卡蜜桃|
99久久精品国产综合一区|