数据结构编程,单链表,链栈,队列,二叉树。

发布网友发布时间：2022-04-23 07:48

共1个回答

热心网友时间：2022-04-23 09:18

#include <iostream>                //二叉树层次遍历
using namespace std;
struct BNode                       //二叉树结点
{
char data;
BNode* lch;
BNode* rch;
};
struct QNode                      //队列结点
{
BNode* data;
QNode* link;
};
class LQue                        //链队列
{
private:
  QNode* Head;
  QNode* Tail;
public:
  LQue();
  int  QueEmp();             //判空?
  void EnQue(BNode* x);      //进
  void DeQue(BNode** x);              //出

};
LQue:: LQue()
{
Head=new QNode;
//Head->link=NULL;
Tail=Head;
}
int  LQue::QueEmp()             //判空?
{
if(Head->link==NULL)
  return 1;
else
  return 0 ;
}
void LQue::EnQue(BNode* x)      //进
{
QNode* p=new QNode;
p->data=x;
p->link=NULL;
Tail->link=p;
Tail=p;
}
void LQue::DeQue(BNode** x)      //出
{
if(!QueEmp())
{
  QNode* p=Head->link;
  *x=p->data;
  Head->link=p->link;
  if(p==Tail)
   Tail=Head;          //只有这种情况需要改变Tail
  delete p;
}
}
class BiTree                       //二叉树
{
private:
  BNode* T;                 //根指针
public:
  BiTree();
  void Create(BNode** T);             //先序
  void InOrder(BNode* T);            //中序
  void PostOrder(BNode* T);          //后序
  void LvlOrder();                   //层次 ,需要队列函数支持Que(),QueEmp(),EnQue()进,DeQue()出
};
BiTree::BiTree()
{
T=NULL;
cout<<"请输入数据(#),以创建二叉树..."<<endl;
Create(&T);
cout<<"中序遍历二叉树..."<<endl;
InOrder(T);
cout<<endl<<"后序遍历二叉树..."<<endl;
PostOrder(T);
cout<<endl<<"层次遍历二叉树..."<<endl;
LvlOrder();
}
void BiTree::Create(BNode** T)            //先序
{
char da;              //数据类型必须和BNode中对应
cin>>da;
if(da=='#')
  *T=NULL;
else
{
  *T=new BNode;
  (*T)->data=da;
  //cout<<endl;
  Create(&(*T)->lch);     //调用加&
  Create(&(*T)->rch);
}
}
void BiTree::InOrder(BNode* T)
{
if(T)
{
  InOrder(T->lch);
  cout<<T->data;
  InOrder(T->rch);
}
}
void BiTree::PostOrder(BNode* T)
{
if(T)
{
  PostOrder(T->lch);
  PostOrder(T->rch);
  cout<<T->data;
}
}
void BiTree::LvlOrder()
{
LQue q;
BNode* a;
if(T)
{
  q.EnQue(T);
  while(!q.QueEmp())
  {
   q.DeQue(&a);            //返回值赋值给a
   cout<<a->data;
   if(a->lch!=NULL)
    q.EnQue(a->lch);
   if(a->rch!=NULL)
    q.EnQue(a->rch);
  }
  cout<<endl;
}
}
int main(int argc, char** argv)
{
BiTree T;
return 0;
}