[原创]12小时寻求帮助.. - 数据结构与算法

得分:0

template<typename T>class BTree
{private:
  BTreeNode<T> *root;
  void InOrder(BTreeNode<T> *);
  void PostOrder(BTreeNode<T> *);
  void PreOrder(BTreeNode<T> *);
  void NoReInOrder(BTreeNode<T> *);
  void NoRePreOrder(BTreeNode<T> *);
  void NoRePostOrder(BTreeNode<T> *);
  void LevelOrder(BTreeNode<T> *);
  void MakeEmpty(BTreeNode<T> *);
  void CountLeaf(BTreeNode<T> *,int &);
  void NoReCountLeaf(BTreeNode<T> *);
  int Depth(BTreeNode<T> *);

public:
BTree();
~BTree();
BTreeNode<T>* Search(T &);
void InsertNode(T &);
void DeNode(T &);
void LevelOrder(){LevelOrder(root);}
void InOrder(){InOrder(root);}
void PostOrder(){PostOrder(root);}
void PreOrder(){PreOrder(root);}
void NoReInOrder(){NoReInOrder(root);}
void NoRePreOrder(){NoRePreOrder(root);}
void NoRePostOrder(){NoRePostOrder(root);}
void CountLeaf();
void NoReCountLeaf();
int Depth(){return Depth(root);}
};
template<typename T>BTree<T>::BTree()
{
root=NULL;
}
template<typename T>BTree<T>::~BTree()
{
cout<<"析构函数执行!用非递归后序遍历删除所有节点:"<<endl;
MakeEmpty(root);
}
template<typename T>BTreeNode<T>* BTree<T>::Search(T & x)/*查找是否存在已插入节点*/
{
    BTreeNode<T> *p;
p=root;
while(p!=NULL&&p->data!=x)
{
   if(p->data>x)
   p=p->lchild;
  else
   p=p->rchild;
}
if(p==NULL)
  return NULL;
else
  return p;
}
template<typename T>void BTree<T>::InsertNode(T & x)/*生成二叉排序树*/
{
BTreeNode<T> *p,*ptr=NULL;
p=root;
if(Search(x)==NULL)
{
   while(p!=NULL)
     {
    ptr=p;
     if(p->data>x)
     p=p->lchild;
    else
     p=p->rchild;
}
     p=new BTreeNode<T>(x,NULL,NULL);
     if(p==NULL)
       {
        cout<<"内存不足!"<<endl;
         exit(1);
    }
     if(ptr==NULL)
     root=p;
     else if(ptr->data>x)
     ptr->lchild=p;
     else
     ptr->rchild=p;
}
else
  cout<<x<<"已经存在,重复插入!"<<endl;
}
template<typename T>void BTree<T>::InOrder(BTreeNode<T> *root)/*中序递归遍历*/
{
if(root!=NULL)
{
  InOrder(root->lchild);
        cout<<root->data<<" ";
     InOrder(root->rchild);
}
}
template<typename T>void BTree<T>::PreOrder(BTreeNode<T> *root)/*递归前序遍历*/
{
if(root!=NULL)
{
  cout<<root->data<<" ";
  PreOrder(root->lchild);
  PreOrder(root->rchild);
}
}
template<typename T>void BTree<T>::PostOrder(BTreeNode<T> *root)/*递归后序遍历*/
{
if(root!=NULL)
{
  PostOrder(root->lchild);
  PostOrder(root->rchild);
  cout<<root->data<<" ";
}
}
template<typename T>void BTree<T>::DeNode(T & x)/*删除节点*/
{
BTreeNode<T> *p,*ptr,*q;
    p=Search(x);
if(p==NULL)
  cout<<"你要删除的节点不存在!"<<endl;
else
{
  p=root;
  ptr=root;
  while(p->data!=x)
  {
            ptr=p;
   if(p->data>x)
    p=p->lchild;
   else
    p=p->rchild;
  }
  if(p->lchild==NULL&&p->rchild==NULL)
  {
   if(p->data>ptr->data)
    ptr->rchild=NULL;
   else
    ptr->lchild=NULL;
   delete p;
  }
  else if(p->lchild!=NULL&&p->rchild==NULL)
  {
   if(p->data>ptr->data)
    ptr->rchild=p->lchild;
   else
    ptr->lchild=p->lchild;
   delete p;
  }
  else if(p->lchild==NULL&&p->rchild!=NULL)
  {
   if(p->data>ptr->data)
    ptr->rchild=p->lchild;
   else
    ptr->lchild=p->rchild;
   delete p;
  }
  /*else                                //要删除的节点存在左右孩子的时候。此为第1种删法
  {
   ptr=root;
   q=p->rchild;
   while(q->lchild!=NULL)
    q=q->lchild;
   p->data=q->data;
   p=p->rchild;
   while(p->lchild!=q)
    p=p->lchild;
   if(q->rchild!=NULL)
    p->lchild=q->rchild;
   else
       p->lchild=NULL;
   delete q;
  }*/
  else                             /*此为第2种删法*/
  {
   ptr=root;
   q=p->rchild;
   while(q->lchild!=NULL)
    q=q->lchild;
   q->lchild=p->lchild;
   p->lchild=NULL;
   q=root;
   while(q!=p)
   {
    ptr=q;
    if(q->data>p->data)
     q=q->lchild;
    else
     q=q->rchild;
   }
   if(ptr->data==p->data)
   {
    root=p->rchild;
    p->rchild=NULL;
   }
   else if(ptr->data>p->data)
    ptr->lchild=p->rchild;
   else
    ptr->rchild=p->rchild;
   p->rchild=NULL;
   delete p;
  }
}
}
template<typename T>void BTree<T>::NoReInOrder(BTreeNode<T> *root)/*非递归中序遍历*/
{
Stack<BTreeNode<T> *>S;
BTreeNode<T> *p;
p=root;
while(p!=NULL||!S.IsEmpty())
{
  while(p!=NULL)
  {
   S.Push(p);
   p=p->lchild;
  }
  p=S.GetTop();
     cout<<p->data<<" ";
  S.Pop();
  p=p->rchild;
}
cout<<endl;
}
template<typename T>void BTree<T>::NoRePreOrder(BTreeNode<T> *root)/*非递归前序遍历*/
{
Stack<BTreeNode<T> *>S;
BTreeNode<T> *p;
p=root;
while(p||!S.IsEmpty())
{
  while(p!=NULL)
  {
   cout<<p->data<<" ";
   S.Push(p);
   p=p->lchild;
  }
  p=S.GetTop();
  S.Pop();
  p=p->rchild;
}
cout<<endl;
}
template<typename T>void BTree<T>::NoRePostOrder(BTreeNode<T> *root)/*非递归后序遍历*/
{
Stack<BTreeNode<T> *>S;
BTreeNode<T> *p;
int tag[100],top=-1;
p=root;
do
{
  while(p!=NULL)
  {
   S.Push(p);
   tag[++top]=0;
   p=p->lchild;
  }
  if(top>-1)
   if(tag[top]==1)
   {
    cout<<S.GetTop()->data<<" ";
    S.Pop();
    top--;
   }
   else
   {
    p=S.GetTop();
    if(top>-1)
    {
     p=p->rchild;
     tag[top]=1;
    }
   }
}while(p!=NULL||top!=-1);
cout<<endl;
}
template<typename T>void BTree<T>::LevelOrder(BTreeNode<T> *root)/*层次遍历*/
{
BTreeNode<T> *p;
Queue<BTreeNode<T> *>Q;
p=root;
Q.EnQueue(p);
while(!Q.IsEmpty())
{
  p=Q.DeQueue();
  cout<<p->data<<" ";
  if(p->lchild!=NULL) Q.EnQueue(p->lchild);
  if(p->rchild!=NULL) Q.EnQueue(p->rchild);

}
cout<<endl;
}
template<typename T>int BTree<T>::Depth(BTreeNode<T> *root)/*递归求二叉树的深度*/
{
int depthleft,depthright,depthval;
if(root==NULL)
  return 0;
else
{
  depthleft=Depth(root->lchild);
  depthright=Depth(root->rchild);
  depthval=1+(depthleft>depthright?depthleft:depthright);
}
return depthval;
}
template<typename T>void BTree<T>::MakeEmpty(BTreeNode<T> *root)/*用非递归后序遍历来删除所有节点*/
{
int tag[50],top=-1;
BTreeNode<T> *p,*q,*temp;
Stack<BTreeNode<T> *>S;
p=root;
do
{
  while(p!=NULL)
  {
   S.Push(p);
   tag[++top]=0;
   p=p->lchild;
  }
  if(top>-1)
   if(tag[top]==1)
   {
    q=S.GetTop();
    S.Pop();
    top--;
    if(!S.IsEmpty())
    {
     temp=S.GetTop();
        if(temp->lchild==q)
      temp->lchild=NULL;
        else
         temp->rchild=NULL;
     cout<<q->data<<" ";
        delete q;
    }
    else
    {
     cout<<q->data<<" ";
     delete root;
    }
   }
   else
   {
    p=S.GetTop();
    if(top>-1)
    {
     p=p->rchild;
     tag[top]=1;
    }
   }
}while(p!=NULL||top!=-1);
cout<<endl;
}
template<typename T>void BTree<T>::CountLeaf()/*调用CountLeaf(root,count)函数*/
{
int count=0;
cout<<"叶节点为:"<<endl;
CountLeaf(root,count);
cout<<endl;
cout<<"叶节点的个数为:"<<count<<endl;
}
template<typename T>void BTree<T>::CountLeaf(BTreeNode<T> *root,int &count)/*递归求叶节点个数*/
{
if(root!=NULL)
{
  CountLeaf(root->lchild,count);
  CountLeaf(root->rchild,count);
  if(root->lchild==NULL&&root->rchild==NULL)
  {
   count++;
   cout<<root->data<<" ";
  }
}
}
template<typename T>void BTree<T>::NoReCountLeaf()
{
cout<<"叶节点为:"<<endl;
NoReCountLeaf(root);
}
template<typename T>void BTree<T>::NoReCountLeaf(BTreeNode<T> *root)
{
Stack<BTreeNode<T> *>S;
BTreeNode<T> *p,*temp;
int tag[100],top=-1,count=0;
p=root;
do
{
  while(p!=NULL)
  {
   S.Push(p);
   tag[++top]=0;
   p=p->lchild;
  }
  if(top>-1)
   if(tag[top]==1)
   {
    temp=S.GetTop();
    S.Pop();
    top--;
    if(temp->lchild==NULL&&temp->rchild==NULL)
    {
     cout<<temp->data<<" ";
     count++;
    }
   }
   else
   {
    p=S.GetTop();
    if(top>-1)
    {
     p=p->rchild;
     tag[top]=1;
    }
   }
}while(p!=NULL||top!=-1);
cout<<endl;
cout<<"叶节点的个树为:"<<count<<endl;
}

生是编程人！！！！死是编程鬼！！！！颠峰人生！！！焚尽编程！！！爱已严重死机！情必须重新启动！情人已和服务器断开连接！网恋也需要重新拨号！-----激情依旧