C++实现树（前序，中序，后序，层序遍历）-白红宇

C++实现树（前序，中序，后序，层序遍历）

阅读量：6636 次

发布时间：2019-06-25

本文共 2431 字，大约阅读时间需要 8 分钟。

practice1.h文件

#ifndef PRACTICE_H_INCLUDED#define PRACTICE_H_INCLUDED#include 
     
      #include 
      
       template
       
           class  BinaryTree;template
        
         class  TreeNode{public:    TreeNode()    {        leftChild=NULL;        rightChild=NULL;    }    T data;    TreeNode
         
           *leftChild;    TreeNode
          
            *rightChild;};template
           
            class BinaryTree{public: //对二叉树进行的操作 void InOrder(); void InOrder(TreeNode
            
              * currentNode); void PreOrder(); void PreOrder(TreeNode
             
               * currentNode); void PostOrder(); void PostOrder(TreeNode
              
                * currentNode); void LevalOrder(); void Visit(TreeNode
               
                 *currentNode);public: TreeNode
                
                  *root;};template
                 
                  void BinaryTree
                  
                   ::InOrder()//中序遍历 左中右{ InOrder(root);}template 
                   
                    void BinaryTree
                    
                     ::Visit(TreeNode
                     
                      * currentNode){ std::cout<
                      
                       data;}template
                       
                        void BinaryTree
                        
                         ::InOrder(TreeNode
                         
                           *currentNode){ if(currentNode) { InOrder(currentNode->leftChild); Visit(currentNode); InOrder(currentNode->rightChild); }}template
                          
                           void BinaryTree
                           
                            ::PreOrder(){ PreOrder(root);}template
                            
                             void BinaryTree
                             
                              ::PreOrder(TreeNode
                              
                                *currentNode){ if(currentNode) { Visit(currentNode); PreOrder(currentNode->leftChild); PreOrder(currentNode->rightChild); }}template
                               
                                void BinaryTree
                                
                                 ::PostOrder()//后序遍历{ PostOrder(root);}template
                                 
                                  void BinaryTree
                                  
                                   ::PostOrder(TreeNode
                                   
                                     *currentNode){ if(currentNode) { PostOrder(currentNode->leftChild); PostOrder(currentNode->rightChild); Visit(currentNode); }}template
                                    
                                     void BinaryTree
                                     
                                      ::LevalOrder()//层序遍历 显示一个之前先把其左右孩子放到队列里{ std::queue
                                      
                                       
                                        *> q; //创建队列 队列中放的是树节点的指针 TreeNode
                                        
                                         * currentNode=root; while(currentNode) { Visit(currentNode); if(currentNode->leftChild) q.push(currentNode->leftChild); //入队列 if(currentNode->rightChild) q.push(currentNode->rightChild);//入队列 if(q.empty()) return; currentNode=q.front();//将队列头记下，将左右孩子入队列 q.pop();//出队头 }}#endif // PRACTICE_H_INCLUDED

practice.cpp

#include
     
      #include "practice1.h"using namespace std;int main(){    BinaryTree
      
        tree;    TreeNode
       
         f,g,h,i,a,b,c,d,e;    f.data='+';    g.data='-';    h.data='*';    i.data='/';    a.data='A';    b.data='B';    c.data='C';    d.data='D';    e.data='E';    tree.root=&f;    f.leftChild=&g;    f.rightChild=&e;    g.leftChild=&h;    g.rightChild=&d;    h.leftChild=&i;    h.rightChild=&c;    i.leftChild=&a;    i.rightChild=&b;   cout<<"中序遍历"<