树结构---二叉树1

目录

类定义

函数功能实现

首先实现树的创建和层次遍历

递归实现树的前中后遍历 

实现求叶子的结点个数和树的高度

 求结点值的左右孩子

友元函数----用于判断当前公有函数功能是否实现 

 实现清空与左右孩子的剪枝操作

 清空 void clear()

---

采取链式存储存储一棵二叉树

类定义

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

类binTree的私有数据成员为：

结构体node----存储结点带有的数据，并且带有两个指针，用于指向左右孩子结点

结构体自身包含了两个构造函数---一个无参，一个带参数

binTree类还有指向根节点的指针

函数功能实现

首先实现树的创建和层次遍历

由于层次遍历需要用到队列，先导入---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){//针对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位置不存储元素
       data[i]=tmp[(front+1)%maxsize];
       front++;
    }
    front=0;
    rear=maxsize-1;
    maxsize*=2;
    delete[] tmp;
}
#endif

 层次遍历创建树

template<class T>
void binTree<T>::createTree(T flag){
      seqQueue<node*> s;//创建装有结点指针的队列
      //输入根节点并入队
      T x;
      cout<<"输入根节点:";
      cin>>x;
      s.enQueue(root=new node(x));
      //访问结点，并将非空左右孩子入队
      node* tmp;
      T ldata,rdata;
      while(!s.is_empty()){
          tmp=s.deQueue();
          cout<<"输入结点"<<tmp->data<<"的左右孩子:";
          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";
}

注意----队列装入指向结点的指针，所以数据类型是node*

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

该代码起始包含了两步：

1. 创建结点----root=new node(x)
2. 结点入队----s.enQueue(root)

层次遍历 

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

相对于创建，这里只需要访问即可，故而没有创建结点这一步

每次都将当前出队结点的不为空的左右孩子入队

递归实现树的前中后遍历 

前序遍历

由于指向根节点指针是我们的私有成员，用户不需要也不应该调用，所以公共函数无参数，在私有成员添加一个带有根节点的重载函数，帮助完成遍历过程

即：

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前序遍历:";
      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<<"\n中序遍历:";
       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后序遍历:";
      postTraverse(root);
}

实现求叶子的结点个数和树的高度

template<class T>
int binTree<T>::nodeSize(node* t) const{
     if(t==NULL) return 0;
     //结点数=根+左子树+右子树
     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);//根+max(左子树高度，右子树高度)
}
template<class T>
int binTree<T>::treeHigh() const{
   return treeHigh(root);
}

 很简单，依然采用传参

private：

 int nodeSize(node* t) const;

 int treeHigh(node* t) const;

public：

 int nodeSize() const;

 int treeHigh() const;

 求结点值的左右孩子

 用户去求某一个结点的左右孩子时候:

         只知道左右孩子的结点data值，还要传入表示空的flag

即;

   public:

   T lchild(T x,T flag) const;

   T rchild(T x,T flag) const;

但是实际上，在找到该节点要传指针，而且是从根节点找，所以增加find内部工具函数

//辅助函数---找给定结点值的结点指针
   node* find(T x,node* t) const{//传值x和要返回的指针t
       node* tmp;
       if(t==NULL) return NULL;
       //根左右
       if(t->data==x) return t;
       tmp=find(x,t->lchild);
       if(tmp) return tmp;
       else return find(x,t->rchild);
   }

 参数是---指针和想找的x值

这里采取先序遍历去找：

结点指针不空：

先访问根的data，一致即返回

然后申请辅助node去访问左子树，找到即返回

最后只能访问右子树，直接递归

//求左右孩子
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;
 }

 很简单---判断条件：访问节点不为空，其左或右孩子也不能空

最后返回值data---别忘了：指针->data

友元函数----用于判断当前公有函数功能是否实现 

friend void printTree(const binTree<T>& t,T flag){
         //由于要输出值，所以队列存值
         //为了检验函数功能，直接调用已实现函数
         seqQueue<T> s;
         s.enQueue(t.root->data);//值
         T tmp,lc,rc;
         while(!s.is_empty()){ 
              tmp=s.deQueue();
              //调用左右孩子
              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);}
     }

 传入的是：const binTree<T>& t的引用，也就是初始化树的值

如：

    binTree<char> bt;

    printTree(bt,'#');

注意：

seqQueue<T> s;

 s.enQueue(t.root->data)------由于队列存T,而且是应用所以用。别忘了->data

利用已经实现的函数来获得值得左右孩子

lc=t.lchild(tmp,flag);---参数要传对
rc=t.rchild(tmp,flag);

 实现清空与左右孩子的剪枝操作

 清空 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;//把根节点置空
  }
template<class T>
  void binTree<T>::clear(){
       clear(root);
  }

private:

 void clear(node* &t);

public:

 void clear(); 

注意要传指针的引用，因为我们要改变指针的值

最后别忘了置空结点为空

左右剪枝 

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

很简单，在符合剪枝前提--即传入的结点不为空，直接调用clear即可