当前位置：网站首页>Structure de l'arbre - - - arbre binaire 2 traversée non récursive

Structure de l'arbre - - - arbre binaire 2 traversée non récursive

2022-07-01 09:11:00 【Frère laugh errant】

Table des matières

 

Code complet（binTree.h）

Test de la fonction principale

 Traversée non récursive avant, milieu et arrière

Mise en œuvre du préambule：

Dans l'ordre 

Post - order 

 

Code complet（binTree.h）

#include"seqQueue.h"
#include<iostream>
#include<stdlib.h>
using namespace std;
template<class T>
class binTree{
     friend void printTree(const binTree<T>& t,T flag){
         // Parce que la valeur de sortie , Donc la file d'attente stocke la valeur 
         // Pour vérifier la fonction , Appel direct à une fonction implémentée 
         if(t.root==NULL) return;
         seqQueue<T> s;
         s.enQueue(t.root->data);//Valeur
         T tmp,lc,rc;
         while(!s.is_empty()){ 
              tmp=s.deQueue();
              // Appelez les enfants de gauche et de droite 
              lc=t.lchild(tmp,flag);
              rc=t.rchild(tmp,flag);
              cout<<"("<<tmp<<" "<<lc<<" "<<rc<<")"<<endl;
              if(lc!=flag) s.enQueue(lc);
              if(rc!=flag) s.enQueue(rc);}
     }
private:
   struct node{
       T data;
       node *lchild,*rchild;
       node():lchild(NULL),rchild(NULL){}
       node(const T& x,node* p=NULL,node* q=NULL):data(x),lchild(p),rchild(q){}
       ~node(){}
   };
   node* root;
   // Passer le paramètre pour une fonction publique sans paramètre 
   void preTraverse(node* t) const;
   void midTraverse(node* t) const;
   void postTraverse(node* t) const;
   int nodeSize(node* t) const;
   int treeHigh(node* t) const;
   void clear(node* &t);
   //Fonctions auxiliaires--- Pointeur de noeud pour une valeur de noeud donnée 
   node* find(T x,node* t) const{//Transmission de la valeurx Et le pointeur à retourner t
       node* tmp;
       if(t==NULL) return NULL;
       //Racine gauche et droite
       if(t->data==x) return t;
       tmp=find(x,t->lchild);
       if(tmp) return tmp;
       else return find(x,t->rchild);
   }
public:
   /*Constructeur*/
   binTree(){ root=NULL;}
   /* La hiérarchie traverse l'arbre de création + La hiérarchie traverse l'arbre existant */
   void createTree(T flag);//AvecflagReprésente un noeud vide
   void levelTraverse() const;//Traversée hiérarchique
   /* Itération récursive avant, milieu et arrière */
   void preTraverse() const;
   void midTraverse() const;
   void postTraverse() const;
   /*Hauteur de l'arbre+Nombre de noeuds foliaires*/
   int nodeSize() const;
   int treeHigh() const;
   /* Trouvez la valeur du noeud gauche et droit de l'enfant ---Passer le ginsengx Et représente un vide flag*/
   T lchild(T x,T flag) const;
   T rchild(T x,T flag) const;
   //Vide.+Couper
    void clear();
    void defLeft(T x);
    void defRight(T x);
};
//Créer un arbre+Traversée hiérarchique
template<class T>
void binTree<T>::createTree(T flag){
      seqQueue<node*> s;// Créer une file d'attente avec un pointeur de noeud 
      // Saisissez le noeud racine et filez d'attente 
      T x;
      cout<<"Saisissez le noeud racine:";
      cin>>x;
      s.enQueue(root=new node(x));
      //Accès aux noeuds, Et mettre les enfants à gauche et à droite dans l'équipe 
      node* tmp;
      T ldata,rdata;
      while(!s.is_empty()){
          tmp=s.deQueue();
          cout<<" Noeud d'entrée "<<tmp->data<<"Les enfants de gauche et de droite:";
          cin>>ldata>>rdata;
          if(ldata!=flag) s.enQueue(tmp->lchild=new node(ldata));
          if(rdata!=flag) s.enQueue(tmp->rchild=new node(rdata));
      }
      cout<<"create successful!\n";
}
template<class T>
void binTree<T>::levelTraverse() const{
    cout<<"\nTraversée hiérarchique:";
    if(root==NULL) return;
    seqQueue<node*> s;
    s.enQueue(root);
    while(!s.is_empty()){
        node* tmp=s.deQueue();
        cout<<tmp->data<<" ";//Produits
        if(tmp->lchild) s.enQueue(tmp->lchild);
        if(tmp->rchild) s.enQueue(tmp->rchild);
    }
}
// Itération récursive avant, milieu et arrière 
template<class T>
void binTree<T>::preTraverse(node* t) const{
     if(t==NULL) return;
     cout<<t->data<<" ";
     preTraverse(t->lchild);
     preTraverse(t->rchild);
}
template<class T>
void binTree<T>::preTraverse() const{
      cout<<"\nTraversée du préfixe:";
      preTraverse(root);
}
template<class T>
void binTree<T>::midTraverse(node* t) const{
     if(t==NULL) return;
     midTraverse(t->lchild);
     cout<<t->data<<" ";
     midTraverse(t->rchild);
}
template<class T>
void binTree<T>::midTraverse() const{
       cout<<"\nTraversée de l'ordre moyen:";
       midTraverse(root);
}
template<class T>
void binTree<T>::postTraverse(node* t) const{
     if(t==NULL) return;
     postTraverse(t->lchild);
     postTraverse(t->rchild);
     cout<<t->data<<" ";
}
template<class T>
void binTree<T>::postTraverse() const{
      cout<<"\nTraversée postérieure:";
      postTraverse(root);
}
// Trouver le nombre de noeuds +Hauteur de l'arbre
template<class T>
int binTree<T>::nodeSize(node* t) const{
     if(t==NULL) return 0;
     //Nombre de noeuds=Racine+Sous - arbre gauche+Sous - arbre droit
     else return nodeSize(t->lchild)+nodeSize(t->rchild)+1;
}
template<class T>
int binTree<T>::nodeSize() const{
     return nodeSize(root);
}
template<class T>
int binTree<T>::treeHigh(node* t) const{
     if(t==NULL) return 0;
     int L,R;
     L=treeHigh(t->lchild);
     R=treeHigh(t->rchild);
     return 1+(L>R?L:R);//Racine+max(Hauteur du sous - arbre gauche,Hauteur du sous - arbre droit)
}
template<class T>
int binTree<T>::treeHigh() const{
   return treeHigh(root);
}
// S'il vous plaît, les enfants de gauche et de droite 
template<class T>
 T binTree<T>::lchild(T x,T flag) const{
       node* tmp=find(x,root);
       if(tmp==NULL||tmp->lchild==NULL) return flag;
       else return  tmp->lchild->data;
 }
 template<class T>
 T binTree<T>::rchild(T x,T flag) const{
       node* tmp=find(x,root);
       if(tmp==NULL||tmp->rchild==NULL) return flag;
       else return  tmp->rchild->data;
 }
 //Vide.+Couper
 template<class T>
  void binTree<T>::clear(node* &t){
     if(t==NULL) return;
     clear(t->lchild);
     clear(t->rchild);
     delete t;
     t=NULL;// Laissez le noeud racine vide 
  }
 template<class T>
  void binTree<T>::clear(){
       clear(root);
  }
template<class T>
void binTree<T>::defLeft(T x){
    node* tmp=find(x,root);
    if(tmp==NULL) return;
    clear(tmp->lchild);
}
template<class T>
void binTree<T>::defRight(T x){
    node* tmp=find(x,root);
    if(tmp==NULL) return;
    clear(tmp->rchild);
}

Test de la fonction principale

664ac8672cb9454f8e9b8a06492f98e2.png

#include"binTree.h"
#include<stdlib.h>
#include<iostream>
using namespace std;
int main(){
    binTree<char> bt;
    bt.createTree('#');
    printTree(bt,'#');
    cout<<bt.nodeSize()<<" "<<bt.treeHigh()<<endl;
    bt.defLeft('D');
    printTree(bt,'#');
    cout<<endl;
    cout<<bt.nodeSize()<<" "<<bt.treeHigh()<<endl;
    bt.defRight('B');
    printTree(bt,'#');
    cout<<endl;
    cout<<bt.nodeSize()<<" "<<bt.treeHigh()<<endl;
    return 0;
}

addaf12616e84e3a974e498bc3200281.png

 12de84bd294949ff8abc6f9e558d7761.png

 Traversée non récursive avant, milieu et arrière

  Importer un fichier Stack ----stack.h

template<class elemType>
class seqStack{
private:
  elemType* data;
  int maxsize;
  int top_s;
  void doublespace();//Expansion de la capacité
public:
  //Structure+Structure analytique
  seqStack(int initszie=10){
      data=new elemType[initszie];
      maxsize=initszie;
      top_s=-1;
  }
  ~seqStack(){ delete[] data;}
  //Fonctionnement de la fonction
  bool is_empty() const{  return top_s==-1;}
  elemType top() const{ return data[top_s];}
  elemType pop(){
      return data[top_s--];
  }
  void push(const elemType& x){
      data[++top_s]=x;
  }
};
//Expansion de la capacité
template<class elemType>
void seqStack<elemType>::doublespace(){
   elemType* tmp;
   maxsize*=2;
   data=new elemType[maxsize];
   for(int i=0;i<=top_s;i++){
       data[i]=tmp[i];
   }
   delete[] tmp;
}

Mise en œuvre du préambule：

void preTraverse() const{
          seqStack<node*> s;
          if(root==NULL) return;
          cout<<"Traversée du préfixe：";
          s.push(root);
          node* tmp;
          while(!s.is_empty()){
               tmp=s.pop();
               cout<<tmp->data<<" ";
               // Parce que la pile est entrée, sortie , Assurez - vous d'abord à droite, puis à gauche 
               if(tmp->rchild) s.push(tmp->rchild);
               if(tmp->lchild) s.push(tmp->lchild);
          }
   }

C'est plus simple., Traversée hiérarchique similaire , Il faut d'abord que l'enfant droit entre dans la pile , Puis l'enfant gauche est entré dans la pile

Dans l'ordre 

void midTraverse() const{//Ordre moyen non récursif
       /* Parce que le nombre de piles à enregistrer , Donc l'introduction de la structure elem*/
       if(root==NULL) return;
       struct elem{
           node* cur;
           int time;
           elem(node* p=NULL):cur(p),time(0){ }//Constructeur
       };
       cout<<"Traversée non récursive de l'ordre moyen：";
       //Initialisation---Avecelem Pile et elemVariables
       seqStack<elem> s;
       elem bt(root);
       s.push(bt);
       elem tmp;//Enregistrer la pile
       while(!s.is_empty()){
            tmp=s.pop();
            if(tmp.time==1){
                // Indique que la pile a été sortie une fois , C'est - à - dire que l'accès au noeud gauche est terminé 
                cout<<tmp.cur->data<<" ";
                // Ensuite, accédez au noeud enfant droit 
                if(tmp.cur->rchild) s.push(tmp.cur->rchild);
            }
            else{
                tmp.time+=1;
                s.push(tmp);// C'est ma première visite ,En pile,time+1
                // L'enfant gauche dans la pile 
                if(tmp.cur->lchild) s.push(tmp.cur->lchild);
            }
       }
       cout<<endl;
   }

 Attention!：elem(tmp.cur->lchild)------ Oui.elemType, Aucun nom de variable spécifié , Comme les variables temporaires

Attention!： Si vous sortez de la pile une fois ,Alorstime+1, Et en accédant au noeud gauche ,Assurez - vous que：Dans la pile.pushUne fois.

Post - order 

void postTraverse() const{//Post - ordre non récursif
       /* Parce que le nombre de piles à enregistrer , Donc l'introduction de la structure elem*/
       if(root==NULL) return;
       struct elem{
           node* cur;
           int time;
           elem(node* p=NULL):cur(p),time(0){ }//Constructeur
       };
       cout<<"Traversée post - ordre non récursive：";
        //Initialisation---Avecelem Pile et elemVariables
       seqStack<elem> s;
       elem bt(root);
       s.push(bt);
       elem tmp;//Enregistrer la pile
       // Ce qui précède correspond au Code de traversée de l'ordre du milieu 
       while(!s.is_empty()){
           tmp=s.pop();
          if(tmp.time==2){
               // Visité 2 fois , C'est - à - dire que les enfants de gauche et de droite ont traversé ,Résultats obtenus
               cout<<tmp.cur->data<<" ";
           }
           else{
               if(tmp.time==1){
                   // L'enfant de gauche a visité ,L'enfant droit dans la pile
                   tmp.time+=1;
                   s.push(tmp);//N'oublie pas, Quand l'enfant droit est entré dans la pile , Encore une fois dans la pile 
                   if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));//Type de note
               }
               else{
                   tmp.time+=1;
                   s.push(tmp);// Va dans la pile tout seul , Et traverser l'enfant de gauche 
                   if(tmp.cur->lchild) s.push(elem(tmp.cur->lchild));
               }
           }
       }
   }

  La différence par rapport à l'ordre du milieu est seulement dans ：

while(!s.is_empty()){

//La différence

}

           if(tmp.time==2){
               // Visité 2 fois , C'est - à - dire que les enfants de gauche et de droite ont traversé ,Résultats obtenus
               cout<<tmp.cur->data<<" ";
           }
           else{
               if(tmp.time==1){
                   // L'enfant de gauche a visité ,L'enfant droit dans la pile
                   tmp.time+=1;
                   s.push(tmp);//N'oublie pas, Quand l'enfant droit est entré dans la pile , Encore une fois dans la pile 
                   if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));//Type de note
               }
               else{
                   tmp.time+=1;
                   s.push(tmp);// Va dans la pile tout seul , Et traverser l'enfant de gauche 
                   if(tmp.cur->lchild) s.push(elem(tmp.cur->lchild));
               }
           }

Remarquez ce processus racinaire à gauche et à droite ：

if  Accès aux racines

else  if      Première fois---Enfant de gauche

        else  Deuxième fois---Enfant droit

Procédure complète 

#include<stdlib.h>
#include"seqStack.h"
#include<iostream>
using namespace std;
template<class T>
class binTree{
private:
   struct node{
       T data;
       node *lchild,*rchild;
       node():lchild(NULL),rchild(NULL){}
       node(const T& x,node* p=NULL,node* q=NULL):data(x),lchild(p),rchild(q){}
       ~node(){}
   };
   node* root;
public:
    binTree(){ root=NULL;}
    void createTree();// Arbre d'initialisation statique 
    void preTraverse() const{// Pré - ordre non récursif 
          if(root==NULL) return;
          cout<<"Traversée pré - ordonnée non récursive：";
          //Mettre le noeud racine sur la pile
          seqStack<node*> s;// Le type d'élément de la pile est --node*
          s.push(root);
          node* tmp;// Enregistrer les éléments de pile 
          while(!s.is_empty()){
              tmp=s.pop();//L'élément supérieur de la pile sort de la pile
              cout<<tmp->data<<" ";//Traversée du préfixe--Accéder d'abord à la racine
              // En raison du dernier entré premier sorti de la pile , L'enfant droit entre dans la pile avant l'enfant gauche 
              if(tmp->rchild) s.push(tmp->rchild);
              if(tmp->lchild) s.push(tmp->lchild);
          }
          cout<<endl;
   }
    void midTraverse() const{//Ordre moyen non récursif
       /* Parce que le nombre de piles à enregistrer , Donc l'introduction de la structure elem*/
       if(root==NULL) return;
       struct elem{
           node* cur;
           int time;
           elem(node* p=NULL):cur(p),time(0){ }//Constructeur
       };
       cout<<"Traversée non récursive de l'ordre moyen：";
       //Initialisation---Avecelem Pile et elemVariables
       seqStack<elem> s;
       elem bt(root);
       s.push(bt);
       elem tmp;//Enregistrer la pile
       while(!s.is_empty()){
            tmp=s.pop();
            if(tmp.time==1){
                // Indique que la pile a été sortie une fois , C'est - à - dire que l'accès au noeud gauche est terminé 
                cout<<tmp.cur->data<<" ";
                // Ensuite, accédez au noeud enfant droit 
                if(tmp.cur->rchild) s.push(tmp.cur->rchild);
            }
            else{
                tmp.time+=1;
                s.push(tmp);// C'est ma première visite ,En pile,time+1
                // L'enfant gauche dans la pile 
                if(tmp.cur->lchild) s.push(tmp.cur->lchild);
            }
       }
       cout<<endl;
   }
   void postTraverse() const{//Post - ordre non récursif
       /* Parce que le nombre de piles à enregistrer , Donc l'introduction de la structure elem*/
       if(root==NULL) return;
       struct elem{
           node* cur;
           int time;
           elem(node* p=NULL):cur(p),time(0){ }//Constructeur
       };
       cout<<"Traversée post - ordre non récursive：";
        //Initialisation---Avecelem Pile et elemVariables
       seqStack<elem> s;
       elem bt(root);
       s.push(bt);
       elem tmp;//Enregistrer la pile
       // Ce qui précède correspond au Code de traversée de l'ordre du milieu 
       while(!s.is_empty()){
           tmp=s.pop();
          if(tmp.time==2){
               // Visité 2 fois , C'est - à - dire que les enfants de gauche et de droite ont traversé ,Résultats obtenus
               cout<<tmp.cur->data<<" ";
           }
           else{
               if(tmp.time==1){
                   // L'enfant de gauche a visité ,L'enfant droit dans la pile
                   tmp.time+=1;
                   s.push(tmp);//N'oublie pas, Quand l'enfant droit est entré dans la pile , Encore une fois dans la pile 
                   if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));//Type de note
               }
               else{
                   tmp.time+=1;
                   s.push(tmp);// Va dans la pile tout seul , Et traverser l'enfant de gauche 
                   if(tmp.cur->lchild) s.push(elem(tmp.cur->lchild));
               }
           }
       }
   }
};
template<class T>
void binTree<T>::createTree(){
    node* f=new node('f');
    node* g=new node('g');
    node* k=new node('k');
    node* h=new node('h');
    node* e=new node('e',f,g);
    node* j=new node('j',NULL,k);
    node* d=new node('d',NULL,e);
    node* i=new node('i',j,NULL);
    node* b=new node('b',d,NULL);
    node* c=new node('c',h,i);
    root=new node('a',b,c);
}

Tester la fonction principale

 int main(){

    binTree<char> bt;

    bt.createTree();

    bt.preTraverse();

    bt.midTraverse();

    bt.postTraverse();

    return 0;

}

a3b83dd36bc049daa1250e0eafed91da.png

 

5bd709f2622340d095a9c0bdf2f530d2.png

 

 

原网站

版权声明
本文为[Frère laugh errant]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/182/202207010904487868.html

边栏推荐

猜你喜欢

随机推荐