p=p->next;
}
}
polyadd（polyheada,polyheadb）{//多项式相加
pointerp,q,r,s;
intt;
polyheadc;
headc=newnode;
p=heada->next;
q=headb->next;
r=headc;
while（p&&q）//两个多项式都没有处理完成。
{
if（p->exp==q->exp）{
t=p->co+q->co;
if（t!
=0）{s=newnode;s->exp=p->exp;s->co=t;}//两相相加系数项为0，不需要生成新节点，指针直接后移
p=p->next;q=q->next;
}
elseif（p->expexp）{s=newnode;s->exp=p->exp;s->co=p->co;p=p->next;}
elseif（p->exp>q->exp）{s=newnode;s->exp=q->exp;s->co=q->co;q=q->next;}
r->next=s;
r=s;
}
while（p）{s=newnode;s->exp=p->exp;s->co=p->co;p=p->next;r->next=s;r=s;}
while（q）{s=newnode;s->exp=q->exp;s->co=q->co;q=q->next;r->next=s;r=s;}
r->next=NULL;
returnheadc;
}
voidmain（）
{
polyheada,headb,headc;
cout<<"inputcoandexptocreatepolya.\n";
heada=create（）;
cout<<"inputcoandexptocreatepolyb.\n";
headb=create（）;
showpoly（heada）;
showpoly（headb）;
headc=add（heada,headb）;
showpoly（headc）;
}
#include
#include
constintmaxsize=100;
typedefchardatatype;
typedefstructnode*pointer;//二叉链表类型
structnode{
datatypedata;
pointerlchild,rchild;
};
typedefpointerbitree;
typedefstruct{
pointerdata[maxsize];
intfront,rear;
}sqqueue;
pointerQ[maxsize+1];//按层次序列建立二叉树，返回根指针
bitreelevel_creat（）{
datatypech;
intfront,rear;
pointerroot,s;
root=NULL;
front=rear=0;
while（cin>>ch,ch!
='#'）{
if（ch!
='@'）{
s=newnode;
s->data=ch;
s->lchild=s->rchild=NULL;
}
elses=NULL;
rear++;
Q[rear]=s;
if（rear==1）{root=s;front=1;}
elseif（s&&Q[front]）{
if（rear%2==0）Q[front]->lchild=s;
elseQ[front]->rchild=s;}
if（rear!
=1&&rear%2==1）front++;
}
returnroot;
}
bitreepre_creat（）{//先根建立
}
bitreeprein_creat（datatypePre[],intps,intpe,datatypeIn[],intis,intie）{//先序和中序建立二叉树，ps、pe、is、ie分别为区间的起止节点
}
bitreepostin_creat（datatypePost[],intps,intpe,datatypeIn[],intis,intie）{//后序和中序建立二叉树，ps、pe、is、ie分别为区间的起止节点
}
voidpreorder（bitreet）{//先根遍历
}
voidinorder（bitreet）{//中根遍历
}
voidpostorder（bitreet）{//后根遍历
}
voidinit_sqqueue（sqqueue&Q）{//循环队列初始化
Q.front=Q.rear=-1;
}
intempty_sqqueue（sqqueue&Q）{//循环队列空判断
if（Q.rear==Q.front）return1;
elsereturn0;
}
inten_sqqueue（sqqueue&Q,pointerp）{//入队
if（（（Q.rear+1）%maxsize）==Q.front）{
cout<<"队满，不能入队！
\n"<return0;
}
else{
Q.rear=（Q.rear+1）%maxsize;
Q.data[Q.rear]=p;
return1;
}
}
intde_sqqueue（sqqueue&Q,pointer&p）{//出队，返回原对头指针
if（Q.rear==Q.front）{
cout<<"队空，不能出队\n";
return0;
}
else{
Q.front=（Q.front+1）%maxsize;
p=Q.data[Q.front];
return1;
}
}
voidlevelorder（bitreet）{//层次遍历
}
voidvisit（pointerp）{//访问结点
if（p!
=NULL）cout<data<elsecout<<"error"<}
voidpreorder0（bitreet）{//先根遍历，非递归
}
voidpreorder1（bitreet）{//先根遍历，非递归，根预入栈处理
}
voidpreorder2（bitreet）{//先根遍历，非递归，预入栈处理
}
voidinorder0（bitreet）{//中根遍历，非递归
}
typedefstruct{
pointerp;
intflag;
}stracktype;
voidpostorder0（bitreet）{//后根遍历、非递归
pointerp;
stracktypeS[maxsize];
inttop,flag;
if（t==NULL）return;
top=-1;
p=t;
while（!
（p==NULL&&top==-1））{
while（p!
=NULL）{//进栈
top++;
S[top].p=p;
S[top].flag=1;
p=p->lchild;
}
p=S[top].p;//退栈
flag=S[top].flag;
top--;
if（flag==1）{
top++;
S[top].p=p;
S[top].flag=2;
p=p->rchild;
}
else{
visit（p）;
p=NULL;
}
}
}
intnumleaf=0;//numleaf为叶子数,求二叉树中的叶子节点总数
voidleaf（bitreet）{
}
intnum=0;//num为节点数，求二叉树中的节点总数
voidnode（bitreet）{
}
intdegree1=0;//degree1为二叉树中度为1的节点数，求二叉树中度为1的节点总数
voidnode_degree1（bitreet）{
}
intdegree2=0;//degree2为二叉树中度为2的节点数，求二叉树中度为2的节点总数
voidnode_degree2（bitreet）{
}
intdepth（bitreet）{//求二叉树的高度，depth为树的高度
intl,r;
if（t==NULL）return0;
l=depth（t->lchild）;
r=depth（t->rchild）;
return（l>r?
l:
r）+1;
}
voiddel_tree（bitreet）{//二叉树的删除，递归实现
}
voidexch_tree（bitreet）{//交换二叉树的左右子树
}
intfind_tree（bitreet,datatypex）{//在二叉树中查询值为x的节点位置，不能找到返回0
}
//层次建立，先根建立，中根建立，后根建立，先序和中序建立，后序和中序建立；先根遍历，中根遍历，后根遍历，层次遍历，非递归的先根遍历，非递归根预入栈处理的先根遍历1，非递归根预入栈处理的先根遍历2，非递归的中根遍历，非递归的后根遍历，求叶子数，求节点数，求二叉树中度为1的节点总数，求二叉树中度为2的节点总数，求二叉树的高度
voidmain（）{
inti,j;
bitreet;
datatypePre[maxsize],In[maxsize],Post[maxsize];
datatypex;
cout<<"二叉树的操作：
0、退出程序，1、层次建立，2、先根建立，3、中根建立，4、后根建立，5、先序和中序建立，6、后序和中序建立；"
<<"7、先根遍历，8、中根遍历，9、后根遍历，10、层次遍历，11、非递归的先根遍历，12、非递归根预入栈处理的先根遍历1，"
<<"13、非递归根预入栈处理的先根遍历2，14、非递归的中根遍历，15、非递归的后根遍历，16、求叶子数，17、求节点数，"
<<"18、求二叉树中度为1的节点总数，19、求二叉树中度为2的节点总数，20、求二叉树的高度,21、二叉树的销毁,22，左右子树的交换"
<cout<<"请选择要执行的函数，输入对应的序号"<cin>>i;
while（i!
=0）{
switch（i）{
case1:
t=level_creat（）;
break;
case2:
t=pre_creat（）;
break;
/*case3:
t=in_creat（）;
break;
case4:
t=post_creat（）;
break;*/
case5:
cout<<"请输入先序序列:
"<cin>>Pre;
cout<<"请输入中序序列:
"<cin>>In;
t=prein_creat（Pre,0,strlen（Pre）-1,In,0,strlen（In）-1）;
break;
case6:
cout<<"请输入后序序列:
"<cin>>Post;
cout<<"请输入中序序列:
"<cin>>In;
t=postin_creat（Post,0,strlen（Post）-1,In,0,strlen（In）-1）;
break;
case7:
preorder（t）;
break;
case8:
inorder（t）;
break;
case9:
postorder（t）;
break;
case10:
levelorder（t）;
break;
case11:
preorder0（t）;
break;
case12:
preorder1（t）;
break;
case13:
preorder2（t）;
break;
case14:
inorder0（t）;
break;
case15:
postorder0（t）;
break;
case16:
leaf（t）;
cout<<"叶子节点数为：
"<break;
case17:
node（t）;
cout<<"节点数为：
"<break;
case18:
node_degree1（t）;
cout<<"度为1的节点数为：
"<break;
case19:
node_degree2（t）;
cout<<"度为2的节点数为：
"<break;
case20:
j=depth（t）;
cout<<"二叉树的高度为：
"<break;
case21:
del_tree（t）;
break;
case22:
cout<<"交换二叉树的左右子树"<exch_tree（t）;
break;
case23:
cout<<"请输入要查找的节点值"<cin>>x;
i=find_tree（t,x）;
cout<break;
}
cout<<"请选择要执行的函数，输入对应的序号"<cin>>i;
}
}
升级会员 