Tree structure --- binary tree 1

Catalog

Class definition

Function function implementation

First, create the tree and traverse the hierarchy

Recursive implementation of the tree before, during and after traversal  

To achieve the number of leaf nodes and the height of the tree

  Find the left and right children of the node value

Friend function ---- Used to judge whether the current public function function is implemented  

  To clear and prune the left and right children

  Empty void clear()

---

take Chain store Store a binary tree

Class definition

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;
   // Pass parameters to public nonparametric functions 
public:
   // Constructors 
   binTree(){ root==NULL;}
};

class binTree The private data member of is ：

Structure node---- Storage Data carried by nodes , And with Two pointers , be used for Point to the left and right children node

The structure itself contains two constructors --- A no arguments , One with parameters

binTree Class also has a pointer to the root node

Function function implementation

First, create the tree and traverse the hierarchy

Because the hierarchy traversal needs to use the queue , First import ---seqQueue.h

#ifndef my_queue
#define my_queue
template<class elemType>
class seqQueue{
private:
    elemType* data;
    int maxsize;
    int front,rear;
    void doublespace();
public:
    seqQueue(int initsize=3){ 
        data=new elemType[initsize];
        maxsize=initsize;
        front=rear=0;
    }
    ~seqQueue(){}
    bool is_empty() const{ return front==rear;}
    elemType getHead() const {return data[(front+1)%maxsize];}
    elemType getTail() const {return data[rear];}
    void enQueue(const elemType& x){// in the light of rear
          if((rear+1)%maxsize==front) doublespace();
          rear=(rear+1)%maxsize;
          data[rear]=x;
    }
    elemType deQueue(){
        front=(front+1)%maxsize;
        return data[front];
    }
};
template<class elemType>
void seqQueue<elemType>::doublespace(){
    elemType* tmp=data;
    data=new elemType[maxsize*2];
    for(int i=1;i<maxsize;i++){//0 Location does not store elements 
       data[i]=tmp[(front+1)%maxsize];
       front++;
    }
    front=0;
    rear=maxsize-1;
    maxsize*=2;
    delete[] tmp;
}
#endif

  Hierarchical traversal creates a tree

template<class T>
void binTree<T>::createTree(T flag){
      seqQueue<node*> s;// Create a queue with node pointers 
      // Enter the root node and join the queue 
      T x;
      cout<<" Enter the root node :";
      cin>>x;
      s.enQueue(root=new node(x));
      // access node , And join the children around Feikong 
      node* tmp;
      T ldata,rdata;
      while(!s.is_empty()){
          tmp=s.deQueue();
          cout<<" Input node "<<tmp->data<<" Right and left :";
          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";
}

Be careful ---- Queue load pointer to node , So the data type is node*

s.enQueue(root=new node(x))

The code starts with two steps ：

1. Create a node ----root=new node(x)
2. Join the team ----s.enQueue(root)

Level traversal  

template<class T>
void binTree<T>::levelTraverse() const{
    cout<<"\n Level traversal :";
    if(root==NULL) return;
    seqQueue<node*> s;
    s.enQueue(root);
    while(!s.is_empty()){
        node* tmp=s.deQueue();
        cout<<tmp->data<<" ";// Output 
        if(tmp->lchild) s.enQueue(tmp->lchild);
        if(tmp->rchild) s.enQueue(tmp->rchild);
    }
}

As opposed to creating , You only need to visit here , Therefore, there is no node creation step

Every time Current outgoing node Of The left and right children who are not empty join the team

Recursive implementation of the tree before, during and after traversal  

The former sequence traversal

Since the pointer to the root node is our private member , Users do not need and should not call , So public functions have no parameters , Add an overloaded function with root node to the private member , Help complete the traversal process

namely ：

private:

void preTraverse(node* t) const;

public:

void preTraverse() const;

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<<"\n The former sequence traversal :";
      preTraverse(root);
}

  It's simple ----- Recursive export （ The pointer is null ）+ traversal order --- Root left and right

Empathy ：

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<<"\n In the sequence traversal :";
       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<<"\n After the sequence traversal :";
      postTraverse(root);
}

To achieve the number of leaf nodes and the height of the tree

template<class T>
int binTree<T>::nodeSize(node* t) const{
     if(t==NULL) return 0;
     // Number of nodes = root + The left subtree + Right subtree 
     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);// root +max( Height of left subtree , Height of right subtree )
}
template<class T>
int binTree<T>::treeHigh() const{
   return treeHigh(root);
}

  It's simple , Still use pass parameter

private：

 int nodeSize(node* t) const;

 int treeHigh(node* t) const;

public：

 int nodeSize() const;

 int treeHigh() const;

  Find the left and right children of the node value

  When the user asks for the left and right children of a node :

          Only know the nodes of the left and right children data value , Also pass in the empty flag

namely ;

   public:

   T lchild(T x,T flag) const;

   T rchild(T x,T flag) const;

But actually , Find the node to pass the pointer , And it is from the root node , So add find Internal tool function

// Auxiliary function --- Find the node pointer of the given node value 
   node* find(T x,node* t) const{// Pass value x And the pointer to return t
       node* tmp;
       if(t==NULL) return NULL;
       // Root left and right 
       if(t->data==x) return t;
       tmp=find(x,t->lchild);
       if(tmp) return tmp;
       else return find(x,t->rchild);
   }

  Parameter is --- Pointer and what you want x value

Here we take the first order traversal to find ：

The node pointer is not empty ：

Access the root first data, Consistent return

Then apply for assistance node Go to the left subtree , Find and go back

Finally, only the right subtree can be accessed , Direct Recursion

// Ask for the right child 
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;
 }

  It's simple --- Judge the condition ： The access node is not empty , The left or right child cannot be empty

Finally, the return value data--- Don't forget ： The pointer ->data

Friend function ---- Used to judge whether the current public function function is implemented  

friend void printTree(const binTree<T>& t,T flag){
         // Due to the output value , So the queue stores values 
         // To test the function , Call the implemented function directly 
         seqQueue<T> s;
         s.enQueue(t.root->data);// value 
         T tmp,lc,rc;
         while(!s.is_empty()){ 
              tmp=s.deQueue();
              // Call the left and right children 
              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);}
     }

  What's coming in is ：const binTree<T>& t Of quote , That is, the value of the initialization tree

Such as ：

    binTree<char> bt;

    printTree(bt,'#');

Be careful ：

seqQueue<T> s;

 s.enQueue(t.root->data)------ Because the queue is stored T, And it is used for application . Don't forget ->data

Use the functions that have been implemented to get the results that are worth controlling children

lc=t.lchild(tmp,flag);--- Parameters should be passed correctly
rc=t.rchild(tmp,flag);

  To clear and prune the left and right children

  Empty void clear()

template<class T>
  void binTree<T>::clear(node* &t){
     if(t==NULL) return;
     clear(t->lchild);
     clear(t->rchild);
     delete t;
     t=NULL;// Leave the root node empty 
  }
template<class T>
  void binTree<T>::clear(){
       clear(root);
  }

private:

 void clear(node* &t);

public:

 void clear(); 

Pay attention to the reference of the pointer , Because we want to change the value of the pointer

Finally, don't forget to set the empty node to null

Left and right pruning  

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

It's simple , Under the premise of pruning -- That is, the incoming node is not empty , Call directly clear that will do