数据结构考试题

发布网友发布时间：2022-04-23 08:43

共2个回答

热心网友时间：2022-06-18 12:28

#include <iostream.h>
#include <stdlib.h>
#define maxsize 64
typedef char datatype;
typedef struct node
{
datatype data;
struct node *lchild,*rchild;
}bitree;

bitree *creatree()
{
bitree *Q[maxsize];
char ch;
int f,r;
bitree *root,*s;
root=NULL;
f=1;
r=0;
cout<<"请输入:";
cin>>ch;
while(ch!='#')
{
s=NULL;
if(ch!='@')
{
s=(bitree *)malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
r++;
Q[r]=s;
if(r==1)
root=s;
else
{
if(s&&Q[f])
if(r%2==0)
Q[f]->lchild=s;
else
Q[f]->rchild=s;
if(r%2==1)
f++;
}
cin>>ch;
}
return root;
}

void preorder(bitree *root)
{
bitree *p;
bitree *stack[maxsize];
int top;
if(root!=NULL)
{
top=0;
stack[++top]=root;
while(top>0)
{
p=stack[top--];
cout<<p->data<<" ";
if(p->rchild!=NULL)
stack[++top]=p->rchild;
if(p->lchild!=NULL)
stack[++top]=p->lchild;
}
}
}

void inorder(bitree *root)
{
bitree *stack[maxsize],*p;
int top=0;
p=root;
while(p!=NULL||top>0)
{
if(p!=NULL)
{
stack[++top]=p;
p=p->lchild;
}
else
{
p=stack[top--];
cout<<p->data<<" ";
p=p->rchild;
}
}
}

void main()
{
bitree *root;
root=creatree();
cout<<"非递归前序遍历:";
preorder(root);
cout<<endl;
cout<<"非递归中序遍历:";
inorder(root);
cout<<endl;

}

热心网友时间：2022-06-18 12:29

void inorder(bitree *root)
{
bitree *stack[maxsize],*p;
int top=0;
p=root;
while(p!=NULL||top>0)
{
if(p!=NULL)
{
stack[++top]=p;
p=p->lchild;
}
else
{
p=stack[top--];
cout<<p->data<<" ";
p=p->rchild;
}
}
}
这就是中序遍历的算法