树结构---二叉树1

 层次遍历创建树

template
void binTree::createTree(T flag){
      seqQueue 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<<"输入结点"<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
void binTree::levelTraverse() const{
    cout<<"\n层次遍历:";
    if(root==NULL) return;
    seqQueue s;
    s.enQueue(root);
    while(!s.is_empty()){
        node* tmp=s.deQueue();
        cout<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
void binTree::preTraverse(node* t) const{
     if(t==NULL) return;
     cout<data<<" ";
     preTraverse(t->lchild);
     preTraverse(t->rchild);
}
template
void binTree::preTraverse() const{
      cout<<"\n前序遍历:";
      preTraverse(root);
}

 很简单-----递归出口（指针为空）+遍历顺序---根左右

同理：

template
void binTree::midTraverse(node* t) const{
     if(t==NULL) return;
     midTraverse(t->lchild);
     cout<data<<" ";
     midTraverse(t->rchild);
}
template
void binTree::midTraverse() const{
       cout<<"\n中序遍历:";
       midTraverse(root);
}
template
void binTree::postTraverse(node* t) const{
     if(t==NULL) return;
     postTraverse(t->lchild);
     postTraverse(t->rchild);
     cout<data<<" ";
}
template
void binTree::postTraverse() const{
      cout<<"\n后序遍历:";
      postTraverse(root);
}

template
int binTree::nodeSize(node* t) const{
     if(t==NULL) return 0;
     //结点数=根+左子树+右子树
     else return nodeSize(t->lchild)+nodeSize(t->rchild)+1;
}
template
int binTree::nodeSize() const{
     return nodeSize(root);
}
template
int binTree::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
int binTree::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
 T binTree::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
 T binTree::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 flag){
         //由于要输出值，所以队列存值
         //为了检验函数功能，直接调用已实现函数
         seqQueue 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<<"("<

template
  void binTree::clear(node* &t){
     if(t==NULL) return;
     clear(t->lchild);
     clear(t->rchild);
     delete t;
     t=NULL;//把根节点置空
  }
template
  void binTree::clear(){
       clear(root);
  }