二叉树常用操作

时间：2023-01-04 17:33:37
  • #include <iostream>
  • #include <string>
  • //using namespace std;
  • int n=0,dep1=0,dep2=0,m=0,n1=0,n2=0;
  • template <class T>
  • struct BiNode   //二叉树的结点结构
  • {
  •   T data;       
  •   BiNode<T> *lchild, *rchild;
  • };
  • template <class T>
  • class BiTree
  • {
  • public:
  •     BiTree() {root=NULL;}
  •     BiTree(T ch);             //构造函数，初始化一棵二叉树，其前序序列由键盘输入
  •     ~BiTree(void);         //析构函数，释放二叉链表中各结点的存储空间
  •     BiNode<T>* Getroot();  //获得指向根结点的指针
  •     void PreOrder(BiNode<T> *root);     //前序遍历二叉树
  •     void InOrder(BiNode<T> *root);      //中序遍历二叉树
  •     void PostOrder(BiNode<T> *root);    //后序遍历二叉树
  •     void LeverOrder(BiNode<T> *root);   //层序遍历二叉树
  •     int  Count(BiNode<T> *root);//计算结点个数
  •     int  Depth(BiNode<T> *root);//计算深度
  •     int  leafnum(BiNode<T> *root);//叶子节点个数
  •     int  full(BiNode<T> *root);
  • private:
  •     BiNode<T> *root;         //指向根结点的头指针
  •     BiNode<T> *Creat(T ch);     //有参构造函数调用
  •     void Release(BiNode<T> *root);   //析构函数调用 
  • };
  • template<class T>
  • BiTree<T>::BiTree(T ch)
  • {   cout<<"请输入创建一棵二叉树的结点数据"<<endl;
  •     this->root = Creat(ch);
  • }
  • template <class T>
  • BiNode<T>* BiTree<T>::Creat(T ch)
  • {
  •     BiNode<T>* root;
  •     //T ch;
  •     //cout<<"请输入创建一棵二叉树的结点数据"<<endl;
  •     cin>>ch;
  •     if (ch=="#") root = NULL;
  •     else{ 
  •          root = new BiNode<T>;       //生成一个结点
  •          root->data=ch;
  •          root->lchild = Creat(ch);    //递归建立左子树
  •          root->rchild = Creat(ch);    //递归建立右子树
  •     } 
  •     return root;
  • }
  • template<class T>
  • BiTree<T>::~BiTree(void)
  • {
  •     Release(root);
  • }
  • template<class T>
  • BiNode<T>* BiTree<T>::Getroot( )
  • {
  •     return root;
  • }
  • template<class T>
  • void BiTree<T>::PreOrder(BiNode<T> *root)
  • {
  •     if(root==NULL)  return;
  •     else{       
  •         cout<<root->data<<" ";
  •         PreOrder(root->lchild);
  •         PreOrder(root->rchild);
  •     }
  • }
  • template <class T>
  • void BiTree<T>::InOrder (BiNode<T> *root)
  • {
  •     if (root==NULL)  return;      //递归调用的结束条件             
  •     else{   
  •         InOrder(root->lchild);    //中序递归遍历root的左子树
  •         cout<<root->data<<" ";    //访问根结点的数据域
  •         InOrder(root->rchild);    //中序递归遍历root的右子树
  •     }
  • }
  • template <class T>
  • void BiTree<T>::PostOrder(BiNode<T> *root)
  • { 
  •     if (root==NULL)   return;       //递归调用的结束条件
  •     else{   
  •         PostOrder(root->lchild);    //后序递归遍历root的左子树
  •         PostOrder(root->rchild);    //后序递归遍历root的右子树
  •         cout<<root->data<<" ";      //访问根结点的数据域
  •     }
  • }
  • template <class T>
  • void BiTree<T>::LeverOrder(BiNode<T> *root)
  • {
  •     const int MaxSize = 100;
  •     int front = 0;
  •     int rear = 0;  //采用顺序队列，并假定不会发生上溢
  •     BiNode<T>* Q[MaxSize];
  •     BiNode<T>* q;
  •     if (root==NULL) return;
  •     else{
  •         Q[rear++] = root;
  •         while (front != rear)
  •         {
  •             q = Q[front++];
  •             cout<<q->data<<" ";         
  •             if (q->lchild != NULL)    Q[rear++] = q->lchild;        
  •             if (q->rchild != NULL)    Q[rear++] = q->rchild;
  •         }
  •     }
  • }
  • template<class T>
  • void BiTree<T>::Release(BiNode<T>* root)
  • {
  •   if (root != NULL){                  
  •       Release(root->lchild);   //释放左子树
  •       Release(root->rchild);   //释放右子树
  •       delete root;
  •   }
  • }
  • template<class T>
  • int BiTree<T>::Count(BiNode<T> *root)
  • { 
  •  if(root==NULL) return 0;
  •  else
  •  {
  •   Count(root->lchild);
  •   Count(root->rchild);
  •   n++;
  •  }
  •  return n;
  • }
  • template <class T>
  • int BiTree<T>::Depth(BiNode<T> *root)
  • {
  •  if (root==NULL) return 0;
  •    else
  •    {
  •      dep1=Depth(root->lchild);//计算左子树深度
  •      dep2=Depth(root->rchild);//计算右子树深度
  •      if(dep1>dep2) return dep1+1;
  •         else return dep2+1;
  •    }
  • }
  • template <class T>
  • int BiTree<T>::leafnum(BiNode<T> *root)//叶子节点个数
  • {
  •  if(root==NULL) return 0;
  •  else
  •  {
  •   if(root->lchild==NULL && root->rchild==NULL)
  •       m++;
  •   leafnum(root->lchild);
  •   leafnum(root->rchild);
  •  }
  •   return m;
  • }
  • template <class T>
  • int BiTree<T>::full(BiNode<T> *root)
  • {
  •   if(root==NULL) return 0;
  •     else 
  •     {
  •      if(root->lchild==NULL && root->rchild==NULL)
  •          return 1;
  •      else if (root->lchild==NULL || root->rchild==NULL)
  •          return 0;
  •         else return(full(root->lchild) && full(root->rchild));
  •     }
  • }
    • 标签：

    相关文章