根据输入的算术表达式构造对应的二叉树

根据输入的算术表达式构造对应的二叉树,利用二叉树的非递归算法输出对应的前缀后缀(数据结构C语言)

3个回答

typedef struct BtNode
{
char data;
struct BtNode *lchild;//左子树
struct BtNode *rchild;
};
typedef struct
{
struct BtNode *node;
char tag;
}StackNode;
BtNode * creat(char a[])
{
int i=0,k=0,top=-1;
BtNode *p,*t=NULL;
BtNode *st[maxsize];
char ch;
ch=a[i];
while(a[i]!='\0')
{
switch (ch)
{case '(':{
top++;st[top]=p;k=1;break;}
case ')':{
top--;break;}
case ',':{
k=2;break;}
default :{
p=(BtNode *)malloc(sizeof(BtNode));
p->data=ch;
p->lchild=NULL;p->rchild=NULL;
if(t==NULL) t=p;
else{
if(k==1)
{ st[top]->lchild=p;}
else if(k==2)
{ st[top]->rchild=p;}
}
}
}
i++;ch=a[i];

}
return t;
}
int preorder(BtNode * t)
{
int top=-1;
BtNode *st[maxsize],*p=t;
while(p!=NULL||top!=-1){
while(p!=NULL){
printf("%c",p->data);
top++;st[top]=p;
p=p->lchild;
}if(top==-1)
return 1;
else{
p=st[top];
top--;
}
p=p->rchild;
}
}
int inorder(BtNode *t)
{
BtNode *st[maxsize],*p=t;
int top=-1;
while(p!=NULL||top!=-1){
while(p!=NULL){
top++;st[top]=p;p=p->lchild;
}
if(top==-1) return 1;
else{
p=st[top];top--;
printf("%c",p->data);
p=p->rchild;
}
}
}
void postorder(BtNode *t)
{
int top=-1,a;
BtNode *p=t;
StackNode w,s[maxsize];
do{
while(p!=NULL){
w.node=p;w.tag='L';top++;s[top]=w;p=p->lchild;}
a=1;
while(a&&top!=-1){
w=s[top];top--;p=w.node;
switch(w.tag){
case 'L' :
w.tag='R';w.node=p;top++;s[top]=w;
a=0;p=p->rchild;
break;
case 'R':
printf("%c",p->data);

    }
    }
}while(top!=-1);

}

// 二叉树.cpp : 定义控制台应用程序的入口点。
//
//将集合表示形式的二叉树输入,并且按照前中后序输出。

//输入,前序,中序输出已解决。
// 后序输出解决。
#include "stdafx.h"
#include "stdlib.h"
#include "String.h"
#define maxsize 100
typedef struct BtNode
{
char data;
struct BtNode *lchild;//左子树
struct BtNode *rchild;
};
typedef struct
{
struct BtNode *node;
char tag;
}StackNode;
BtNode * creat(char a[])
{
int i=0,k=0,top=-1;
BtNode *p,*t=NULL;
BtNode *st[maxsize];
char ch;
ch=a[i];
while(a[i]!='\0')
{
switch (ch)
{case '(':{
top++;st[top]=p;k=1;break;}
case ')':{
top--;break;}
case ',':{
k=2;break;}
default :{
p=(BtNode *)malloc(sizeof(BtNode));
p->data=ch;
p->lchild=NULL;p->rchild=NULL;
if(t==NULL) t=p;
else{
if(k==1)
{ st[top]->lchild=p;}
else if(k==2)
{ st[top]->rchild=p;}
}
}
}
i++;ch=a[i];

}
return t;
}
int preorder(BtNode * t)
{
int top=-1;
BtNode *st[maxsize],*p=t;
while(p!=NULL||top!=-1){
while(p!=NULL){
printf("%c",p->data);
top++;st[top]=p;
p=p->lchild;
}if(top==-1)
return 1;
else{
p=st[top];
top--;
}
p=p->rchild;
}
}
int inorder(BtNode *t)
{
BtNode *st[maxsize],*p=t;
int top=-1;
while(p!=NULL||top!=-1){
while(p!=NULL){
top++;st[top]=p;p=p->lchild;
}
if(top==-1) return 1;
else{
p=st[top];top--;
printf("%c",p->data);
p=p->rchild;
}
}
}
void postorder(BtNode *t)
{
int top=-1,a;
BtNode *p=t;
StackNode w,s[maxsize];
do{
while(p!=NULL){
w.node=p;w.tag='L';top++;s[top]=w;p=p->lchild;}
a=1;
while(a&&top!=-1){
w=s[top];top--;p=w.node;
switch(w.tag){
case 'L' :
w.tag='R';w.node=p;top++;s[top]=w;
a=0;p=p->rchild;
break;
case 'R':
printf("%c",p->data);

    }
    }
}while(top!=-1);

}


不是很懂图片说明算术表达式是a+b(c-d)这种,集合是。。。

zy010101
zy010101 目的是让你利用二叉树把中缀表达式变成前缀或者后缀表达式吧
接近 3 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问