投稿
  1. 首页
  2. C

树结构---二叉树2非递归遍历

word模板下载 • 2022-6-12 • C • 阅读 33

树结构---二叉树2非递归遍历,第1张

目录

 

完整代码（binTree.h）

主函数测试

 非递归的前中后遍历

前序实现：

中序 

后序 

 

完整代码（binTree.h） 
#include"seqQueue.h"
#include
#include
using namespace std;
template
class binTree{
     friend void printTree(const binTree& t,T flag){
         //由于要输出值，所以队列存值
         //为了检验函数功能，直接调用已实现函数
         if(t.root==NULL) return;
         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<<"("<data==x) return t;
       tmp=find(x,t->lchild);
       if(tmp) return tmp;
       else return find(x,t->rchild);
   }
public:
   /*构造函数*/
   binTree(){ root=NULL;}
   /*层次遍历创建树+层次遍历已有树*/
   void createTree(T flag);//用flag表示空结点
   void levelTraverse() const;//层次遍历
   /*递归实现前中后序遍历*/
   void preTraverse() const;
   void midTraverse() const;
   void postTraverse() const;
   /*求树的高度+叶子结点个数*/
   int nodeSize() const;
   int treeHigh() const;
   /*求左右孩子结点值---传参x和表示空的flag*/
   T lchild(T x,T flag) const;
   T rchild(T x,T flag) const;
   //清空+剪枝
    void clear();
    void defLeft(T x);
    void defRight(T x);
};
//创建树+层次遍历
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";
}
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);
    }
}
//递归实现前中后序遍历
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);
}
//求左右孩子
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;
 }
 //清空+剪枝
 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);
  }
template
void binTree::defLeft(T x){
    node* tmp=find(x,root);
    if(tmp==NULL) return;
    clear(tmp->lchild);
}
template
void binTree::defRight(T x){
    node* tmp=find(x,root);
    if(tmp==NULL) return;
    clear(tmp->rchild);
}
主函数测试 

#include"binTree.h"
#include
#include
using namespace std;
int main(){
    binTree bt;
    bt.createTree('#');
    printTree(bt,'#');
    cout<

 

 非递归的前中后遍历

 引入栈文件----stack.h

template
class seqStack{
private:
  elemType* data;
  int maxsize;
  int top_s;
  void doublespace();//扩容
public:
  //构造+析构
  seqStack(int initszie=10){
      data=new elemType[initszie];
      maxsize=initszie;
      top_s=-1;
  }
  ~seqStack(){ delete[] data;}
  //函数 *** 作
  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;
  }
};
//扩容
template
void seqStack::doublespace(){
   elemType* tmp;
   maxsize*=2;
   data=new elemType[maxsize];
   for(int i=0;i<=top_s;i++){
       data[i]=tmp[i];
   }
   delete[] tmp;
}
前序实现： 
void preTraverse() const{
          seqStack s;
          if(root==NULL) return;
          cout<<"前序遍历：";
          s.push(root);
          node* tmp;
          while(!s.is_empty()){
               tmp=s.pop();
               cout<data<<" ";
               //由于栈后进先出，一定要先右后左
               if(tmp->rchild) s.push(tmp->rchild);
               if(tmp->lchild) s.push(tmp->lchild);
          }
   }

比较简单，类似层次遍历，只是一定要先右孩子进栈，然后左孩子进栈

中序  
void midTraverse() const{//非递归中序
       /*由于要记录出栈次数，所以引入结构elem*/
       if(root==NULL) return;
       struct elem{
           node* cur;
           int time;
           elem(node* p=NULL):cur(p),time(0){ }//构造函数
       };
       cout<<"非递归中序遍历：";
       //初始化---装有elem的栈和elem变量
       seqStack s;
       elem bt(root);
       s.push(bt);
       elem tmp;//记录出栈
       while(!s.is_empty()){
            tmp=s.pop();
            if(tmp.time==1){
                //表明已经出栈过一次了，也就是左结点访问结束
                cout<data<<" ";
                //接下来访问右孩子节点
                if(tmp.cur->rchild) s.push(tmp.cur->rchild);
            }
            else{
                tmp.time+=1;
                s.push(tmp);//自己是第一次访问，入栈，time+1
                //左孩子进栈
                if(tmp.cur->lchild) s.push(tmp.cur->lchild);
            }
       }
       cout<

 注意：elem(tmp.cur->lchild)-----是elem类型，没有指定变量名，类似临时变量

注意：如果出栈过一次，那么time+1，而且在访问左结点，一定要：再进栈push一次

后序  
void postTraverse() const{//非递归后序
       /*由于要记录出栈次数，所以引入结构elem*/
       if(root==NULL) return;
       struct elem{
           node* cur;
           int time;
           elem(node* p=NULL):cur(p),time(0){ }//构造函数
       };
       cout<<"非递归后序遍历：";
        //初始化---装有elem的栈和elem变量
       seqStack s;
       elem bt(root);
       s.push(bt);
       elem tmp;//记录出栈
       //以上和中序遍历代码一致
       while(!s.is_empty()){
           tmp=s.pop();
          if(tmp.time==2){
               //已访问两次，也就是左右孩子都遍历了，输出结果
               cout<data<<" ";
           }
           else{
               if(tmp.time==1){
                   //左孩子已访问，右孩子进栈
                   tmp.time+=1;
                   s.push(tmp);//一定别忘了，右孩子进栈时，自己再进一次栈
                   if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));//注意类型
               }
               else{
                   tmp.time+=1;
                   s.push(tmp);//自己进栈，然后遍历左孩子
                   if(tmp.cur->lchild) s.push(elem(tmp.cur->lchild));
               }
           }
       }
   }

 与中序区别只在：

while(!s.is_empty()){

//区别

}

           if(tmp.time==2){
               //已访问两次，也就是左右孩子都遍历了，输出结果
               cout<data<<" ";
           }
           else{
               if(tmp.time==1){
                   //左孩子已访问，右孩子进栈
                   tmp.time+=1;
                   s.push(tmp);//一定别忘了，右孩子进栈时，自己再进一次栈
                   if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));//注意类型
               }
               else{
                   tmp.time+=1;
                   s.push(tmp);//自己进栈，然后遍历左孩子
                   if(tmp.cur->lchild) s.push(elem(tmp.cur->lchild));
               }
           }

注意这个根左右过程：

if  访问根

else  if      第一次---左孩子

        else  第二次---右孩子

完整程序 

#include
#include"seqStack.h"
#include
using namespace std;
template
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();//静态初始化树
    void preTraverse() const{//非递归前序
          if(root==NULL) return;
          cout<<"非递归前序遍历：";
          //将根节点入栈
          seqStack s;//栈的元素类型是--node*
          s.push(root);
          node* tmp;//记录出栈元素
          while(!s.is_empty()){
              tmp=s.pop();//栈顶元素出栈
              cout<data<<" ";//前序遍历--先访问根
              //由于栈的后进先出，右孩子先于左孩子进栈
              if(tmp->rchild) s.push(tmp->rchild);
              if(tmp->lchild) s.push(tmp->lchild);
          }
          cout< s;
       elem bt(root);
       s.push(bt);
       elem tmp;//记录出栈
       while(!s.is_empty()){
            tmp=s.pop();
            if(tmp.time==1){
                //表明已经出栈过一次了，也就是左结点访问结束
                cout<data<<" ";
                //接下来访问右孩子节点
                if(tmp.cur->rchild) s.push(tmp.cur->rchild);
            }
            else{
                tmp.time+=1;
                s.push(tmp);//自己是第一次访问，入栈，time+1
                //左孩子进栈
                if(tmp.cur->lchild) s.push(tmp.cur->lchild);
            }
       }
       cout< s;
       elem bt(root);
       s.push(bt);
       elem tmp;//记录出栈
       //以上和中序遍历代码一致
       while(!s.is_empty()){
           tmp=s.pop();
          if(tmp.time==2){
               //已访问两次，也就是左右孩子都遍历了，输出结果
               cout<data<<" ";
           }
           else{
               if(tmp.time==1){
                   //左孩子已访问，右孩子进栈
                   tmp.time+=1;
                   s.push(tmp);//一定别忘了，右孩子进栈时，自己再进一次栈
                   if(tmp.cur->rchild) s.push(elem(tmp.cur->rchild));//注意类型
               }
               else{
                   tmp.time+=1;
                   s.push(tmp);//自己进栈，然后遍历左孩子
                   if(tmp.cur->lchild) s.push(elem(tmp.cur->lchild));
               }
           }
       }
   }
};
template
void binTree::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);
}

测试主函数

 int main(){

    binTree bt;

    bt.createTree();

    bt.preTraverse();

    bt.midTraverse();

    bt.postTraverse();

    return 0;

}

 

 

 

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/1330690.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
word模板下载 word模板下载 一级用户组
0 0
上一篇 2022-06-12
下一篇 2022-06-12

发表评论

登录后才能评论

评论列表（0条）

Copyright © 2022 内存溢出 版权所有 湘ICP备2022025235号 Powered by outofmemory.cn

保存