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

    
            

            




            







												


        

            
	
            
		
			

            

            
	
            
		
			
            那誰(shuí)的技術(shù)博客
            
			感興趣領(lǐng)域:高性能服務(wù)器編程,存儲(chǔ),算法,Linux內(nèi)核
		            		
	
            

            

            

            

            隨筆 - 210, 文章 - 0, 評(píng)論 - 1183, 引用 - 0
            

            


            		
	
            

            

            
	
            
		
			
            
				數(shù)據(jù)加載中……
			
            
		            		
		
			
            
				
					
	
            
		
            
			二叉樹(shù)遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)
		
            
		
            
		
		費(fèi)了兩天時(shí)間寫的,包括前中后序遍歷的遞歸和非遞歸算法,還有層序遍歷總共2*3 + 1 = 7中遍歷二叉樹(shù)的算法,感覺(jué)其中后序遍歷的非遞歸算法比較困難,想了很久最后的實(shí)現(xiàn)還是不夠優(yōu)雅,請(qǐng)大家指正~~

            總共三個(gè)文件,一個(gè)頭文件,一個(gè)對(duì)應(yīng)的cpp文件,還有一個(gè)用于測(cè)試的文件.

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

            ????purpose:????演示二叉樹(shù)的算法
            ********************************************************************            */

            #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;
            ????}

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

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

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

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

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

            ????PTreeNode???m_pRoot;????????            //?根結(jié)點(diǎn)

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

            #endif


            實(shí)現(xiàn)文件:
            /********************************************************************
            ????created:????2006/07/04
            ????filename:?????BinaryTree.cpp
            ????author:????????李創(chuàng)
            ????????????????            http://www.shnenglu.com/converse/

            ????purpose:????演示二叉樹(shù)的算法
            ********************************************************************            */

            #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);
            }

            //?按照中序遞歸創(chuàng)建樹(shù)
            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;
            }

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

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

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

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

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

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

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

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

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

            //?非遞歸前序遍歷樹(shù)
            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;????//?訪問(wèn)當(dāng)前結(jié)點(diǎn)
            ????????????NodeStack.push(pNode->pLeft);????????????????????//?左子樹(shù)根結(jié)點(diǎn)入棧
            ????????}
            ????????NodeStack.pop();????????????????????????????????????            //?左子樹(shù)根結(jié)點(diǎn)退棧
            ????????if?(!NodeStack.empty())
            ????????            {
            ????????????pNode?            =?NodeStack.top();
            ????????????NodeStack.pop();????????????????????????????????            //?當(dāng)前結(jié)點(diǎn)退棧
            ????????????NodeStack.push(pNode->pRight);????????????????//?當(dāng)前結(jié)點(diǎn)的右子樹(shù)根結(jié)點(diǎn)入棧
            ????????}
            ????}
            }

            //?中序遍歷樹(shù)
            //?中序遍歷輸出的結(jié)果應(yīng)該和用來(lái)初始化樹(shù)的數(shù)組的排列順序一致
            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);
            ????}
            }

            //?非遞歸中序遍歷樹(shù)
            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);
            ????????}
            ????}
            }

            //?后序遍歷樹(shù)
            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;
            }

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

            ????TreeNodeStack?NodeStack;
            ????PTreeNode?pNode1,?pNode2;
            ????NodeStack.push(pTreenode);
            ????pNode1?            =?pTreenode->pLeft;
            ????
            ????            bool?bVisitRoot?=?false;????????????//?標(biāo)志位,是否訪問(wèn)過(guò)根結(jié)點(diǎn)
            ????while?(!NodeStack.empty())
            ????            {
            ????????            while?(NULL?!=?pNode1)????????????//?向左走到盡頭
            ????????{
            ????????????NodeStack.push(pNode1);
            ????????????pNode1?            =?pNode1->pLeft;
            ????????}

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

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

            ????????????            if?(pNode2?==?pNode1->pRight)????//?如果這個(gè)葉子結(jié)點(diǎn)是右子樹(shù)
            ????????????{
            ????????????????std::cout?            <<?"Item?=?"?<<?pNode1->Node?<<?std::endl;
            ????????????????NodeStack.pop();
            ????????????????pNode1?            =?NULL;
            ????????????}
            ????????????            else????????????????????????????//?否則訪問(wèn)右子樹(shù)
            ????????????{
            ????????????????pNode1?            =?pNode1->pRight;
            ????????????}
            ????????}
            ????????            else????????????????????????????????//?訪問(wèn)右子樹(shù)
            ????????{
            ????????????            if?(pNode1?==?pTreenode?&&?true?==?bVisitRoot)????//?如果已經(jīng)訪問(wèn)過(guò)右子樹(shù)那么就退出
            ????????????{
            ????????????????std::cout?            <<?"Item?=?"?<<?pNode1->Node?<<?std::endl;
            ????????????????            return;
            ????????????}
            ????????????            else
            ????????????            {
            ????????????????            if?(pNode1?==?pTreenode)
            ????????????????            {
            ????????????????????bVisitRoot?            =?true;
            ????????????????}

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

            //?按照樹(shù)的層次從左到右訪問(wèn)樹(shù)的結(jié)點(diǎn)
            void?BinaryTree::LevelTraverseImpl(PTreeNode?pTreenode)
            {
            ????            if?(NULL?==?pTreenode)
            ????????            return;

            ????            //?層序遍歷用于保存結(jié)點(diǎn)的容器是隊(duì)列
            ????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);
            ????????}            ????
            ????}
            }
            
		
            測(cè)試文件:
            /********************************************************************
            ????created:????2006/07/04
            ????filename:?????main.cpp
            ????author:????????李創(chuàng)
            ????????????????            http://www.shnenglu.com/converse/

            ????purpose:????測(cè)試二叉樹(shù)的算法
            ********************************************************************            */

            #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));

            ????            //?創(chuàng)建數(shù)組
            ????CreateNewArray(array,?10);
            ????DisplayArray(array,?            10);

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

            ????            //?測(cè)試前序遍歷
            ????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);
            ????
            ????            //?測(cè)試中序遍歷
            ????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);
            ????            //?測(cè)試后序遍歷
            ????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);
            ????            //?測(cè)試層序遍歷
            ????pTree->Traverse(BinaryTree::LEVELORDER);

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

            ????            return?0;
            }
            
		
            
		
            
			posted on 2006-07-08 15:21 那誰(shuí) 閱讀(20249) 評(píng)論(9)  編輯 收藏 引用  所屬分類: 算法與數(shù)據(jù)結(jié)構(gòu) 
		
            
	
            
	
	


	


            
	    
    


            

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

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

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

            main.cpp

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

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

            執(zhí)行 cl.exe 時(shí)出錯(cuò).

            

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

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

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

            

            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: 二叉樹(shù)遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)  回復(fù)  更多評(píng)論
					  
				
            
				樓上的錯(cuò)誤是DEV C++的工程文件/配置文件的問(wèn)題吧?
				
			
            
		
			
            
				
            
					# re: 二叉樹(shù)遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)[未登錄](méi)  回復(fù)  更多評(píng)論
					  
				
            
				已經(jīng)解決了,謝謝指點(diǎn)!
				
            
					2008-01-06 15:19 | ben
				
            
			
            
		
			
            
				
            
					# re: 二叉樹(shù)遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)  回復(fù)  更多評(píng)論
					  
				
            
				請(qǐng)問(wèn)，為什么我的窗口上什么都米有？只有一個(gè)“請(qǐng)按任意鍵繼續(xù)”，用的是VC++ 2008
				
            
					2008-07-09 07:03 | liuyu
				
            
			
            
		
			
            
				
            
					# re: 二叉樹(shù)遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)  回復(fù)  更多評(píng)論
					  
				
            
				其實(shí)如果不用 Stack 而改用 List 的話，三種非遞歸遍歷將變得更加簡(jiǎn)單一致，一個(gè) While 就夠了

            

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

            

                typedef struct TreeNode

                {

                    Item        Node;

                    TreeNode*   pRight;

                    TreeNode*   pLeft;

                    bool	bVisited;       // 關(guān)鍵

            

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

                        : Node(node)

                        , pRight(pright)

                        , pLeft(pleft)

                        , bVisited(false)

                    {

                    }

            

                }TreeNode, *PTreeNode;

            

            

            

            

            // 非遞歸前序遍歷樹(shù)

            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);

                }

            }

            

            

            // 非遞歸中序遍歷樹(shù)

            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;			// 為下一次遍歷做準(zhǔn)備

            

            			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;

            		}

            

                }

            }

            

            // 非遞歸后序遍歷樹(shù)

            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;			// 為下一次遍歷做準(zhǔn)備

            

            			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: 二叉樹(shù)遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)[未登錄](méi)  回復(fù)  更多評(píng)論
					  
				
            
				非遞歸后續(xù)遍歷修改為：

            public static void iterativePostorder(BinaryTree boot) {

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

            		BinaryTree current, pointer=boot;

            		boolean bVisitRoot = false;//標(biāo)志是否訪問(wèn)過(guò)根節(jié)點(diǎn)

            		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
				
            
			
            
		

            





            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



国产精品综合久久第一页|
久久久久亚洲AV片无码下载蜜桃|
久久五月精品中文字幕|
国产亚洲精久久久久久无码77777|
久久久久久无码Av成人影院|
国产精品成人99久久久久|
久久精品国产2020|
成人精品一区二区久久|
亚洲精品高清国产一线久久|
色综合合久久天天综合绕视看|
中文精品99久久国产|
99久久免费国产特黄|
亚洲国产精品无码久久久久久曰|
日产精品久久久久久久|
久久综合久久性久99毛片|
av国内精品久久久久影院|
亚洲精品高清一二区久久
|
狠狠狠色丁香婷婷综合久久五月
|
久久久久波多野结衣高潮|
精品午夜久久福利大片|
久久九九兔免费精品6|
国产精品99久久久久久猫咪|
亚洲av日韩精品久久久久久a|
久久精品国产亚洲精品|
国产精品一久久香蕉国产线看观看|
色综合久久中文字幕综合网|
久久精品国产91久久综合麻豆自制
|
欧美久久一区二区三区|
久久成人国产精品二三区|
精品久久亚洲中文无码|
久久亚洲中文字幕精品一区|
久久综合综合久久狠狠狠97色88|
777午夜精品久久av蜜臀|
久久综合日本熟妇|
国产精品99久久久久久www|
91精品国产91久久久久福利|
东方aⅴ免费观看久久av|
久久乐国产综合亚洲精品|
久久精品成人欧美大片
|
91精品国产高清久久久久久io
|
偷偷做久久久久网站|