二叉树的遍历算法（递归和迭代）

#include 
     
      #include 
      
       using namespace std;template 
       
        class BinaryTree{public:        BinaryTree(){}        class TreeNode        {        public:                TreeNode(){ visited = false;}                TreeNode* left;                TreeNode* right;                T value;                bool visited;        };        void Insert(T t);        void InorderTraverse(TreeNode * begin);        void PreorderTraverse(TreeNode * begin);        void PostorderTraverse(TreeNode * begin);        void InorderTraverse2();        void PreorderTraverse2();        void PostorderTraverse2();private:        TreeNode *root;        void Insert(TreeNode* root, T t);};template 
        
         void BinaryTree
         
          ::InorderTraverse(TreeNode * begin){        if(NULL != begin->left)                InorderTraverse(begin->left);        cout<
          
           value; if(NULL != begin->right) InorderTraverse(begin->right);}template 
           
            void BinaryTree
            
             ::PreorderTraverse( TreeNode * begin){ cout<
             
              value; if(NULL != begin->left) PreorderTraverse(begin->left); if(NULL != begin->right) PreorderTraverse(begin->right);}template 
              
               void BinaryTree
               
                ::PostorderTraverse(TreeNode * begin){ cout<
                
                 value; if(NULL != begin->left) PostorderTraverse(begin->left); if(NULL != begin->right) PostorderTraverse(begin->right);}template 
                 
                  void BinaryTree
                  
                   ::InorderTraverse2(){ stack
                   
                     treestack; treestack.push(root); TreeNode * tmpNode; while(!treestack.empty()) { tmpNode = treestack.top(); if(NULL == tmpNode->left || tmpNode->left->visited) { treestack.pop(); tmpNode->visited = true; cout<
                    
                     value; if(NULL != tmpNode->right) { treestack.push(tmpNode->right); } } else if(!(tmpNode->left->visited)) { treestack.push(tmpNode->left); } } cout<
                     
                      
                       void BinaryTree
                       
                        ::PreorderTraverse2(){ stack
                        
                          treestack; treestack.push(root); TreeNode * tmpNode; while(!treestack.empty()) { tmpNode = treestack.top(); treestack.pop(); cout<
                         
                          value; if(NULL != tmpNode->right) treestack.push(tmpNode->right); if(NULL != tmpNode->left ) { treestack.push(tmpNode->left); } } cout<
                          
                           
                            void BinaryTree
                            
                             ::PostorderTraverse2(){}template 
                             
                              void BinaryTree
                              
                               ::Insert(T t){ if(NULL == root) { root = new TreeNode(); root->value = t; } else { Insert(root,t); }}template 
                               
                                void BinaryTree
                                
                                 ::Insert(TreeNode *root, T t){ if(t >= root->value) { if(NULL != root->right) Insert(root->right, t); else { TreeNode *temp = new TreeNode(); temp->value = t; root->right = temp; } } else { if(NULL != root->left) Insert(root->left, t); else { TreeNode *temp = new TreeNode(); temp->value = t; root->left = temp; } }}int main(int argc, char **argv){ BinaryTree
                                 
                                   *bitree = new BinaryTree
                                  
                                    (); bitree->Insert(9); bitree->Insert(7); bitree->Insert(8); bitree->Insert(1); bitree->Insert(6); bitree->Insert(4); bitree->Insert(5); bitree->Insert(2); bitree->Insert(3); bitree->Insert(10); bitree->Insert(11); bitree->InorderTraverse2(); bitree->PreorderTraverse2();}
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

二叉查找

深度优选遍历

DFS需要对每个节点保存一个状态，而这个状态可能是3个值：White(没有发现的)， Gray（被发现，正在遍历的）， Black（以遍历完成的）. 所以DFS需要一个数据空间去存储每个节点的状态。就用2386为例子实现一个吧

 

广度优先遍历