永发信息网

数据结构中怎样根据中序先序后序画出树

答案:4  悬赏:70  手机版
解决时间 2021-02-09 10:35
数据结构中怎样根据中序先序后序画出树
最佳答案
#include<iostream>
using namespace std;
#include<malloc.h>
#include<stdio.h>
#include<math.h>
#define maxsize 20 //最大结点个数
//#define N 14 //必须输入结点个数(包含虚结点)
#define M 10 //最大深度
typedef struct node{
char data;
int m; //结点的深度
struct node*lchild,*rchild;
}Bitree;
Bitree*Q[maxsize];
Bitree*creatree()
{
char ch;
int front,rear;
// int i=1;
Bitree *T,*s;
T=NULL;
front=1;
rear=0;
cout<<"请输入数据"<<endl;
cin>>ch;
while(ch!='#')
{
// cin>>ch;
s=NULL;
if(ch!='@')
{
s=(Bitree*)malloc(sizeof(Bitree));
s->data =ch;
s->lchild =s->rchild =NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
{
T=s;
T->m=1; //父结点深度为一
}
else{
if(s!=NULL&&Q[front]!=NULL)
if(rear%2==0)
{
Q[front]->lchild =s;
Q[front]->lchild ->m =Q[front]->m+1;
}
else
{
Q[front]->rchild =s;
Q[front]->rchild ->m =Q[front]->m+1;
}

if(rear%2==1)
front++;
}
//i++;
cin>>ch;
}
return T;
}
int countleaf(Bitree* T)
{
if(T==NULL)
return (0);
else if((T->lchild==NULL)&&(T->rchild==NULL))
return (1);
else
return (countleaf(T->lchild)+countleaf(T->rchild));
}
int treedepth(Bitree *T)
{
if(T==NULL)
return (0);
else
{
if(treedepth(T->lchild )>treedepth(T->rchild ))
return(treedepth(T->lchild )+1);
else
return (treedepth(T->rchild )+1);
}
}
void output(Bitree*T) //输出打印二叉数
{
int i;
if(T!=NULL)
{
output(T->rchild ); //右根左遍历二叉数,结果从上到下显示
for(i=1;i<=M;i++)
{
if(i!=T->m)
cout<<" ";
else
cout<<T->data ;
}
cout<<endl;
//cout<<T->data ;
output(T->lchild );
}
}

int menu_select( )
{
int sn;
printf(" 打印二叉树问题\n");
printf("==================\n");
printf(" 1 二叉树的建立\n");
printf(" 2 打印二叉树\n");
printf(" 3 求二叉树叶子结点个数\n");
printf(" 4 求二叉树的深度\n");
printf(" 0 退出系统\n");
printf("==================\n");
printf(" 请 选 择0-4:\n");
for( ; ; )
{
scanf( "%d", &sn);
if( sn <0||sn>4)
printf("\n\t输入错误,重选0-4:\n");
else
break;
}
return sn;
}

int main( )
{
Bitree*T;
for(; ;)
{
switch(menu_select())
{
case 1: T=creatree();
printf("\n");
break;
case 2: cout<<"打印结果:"<<endl;
output(T);
printf("\n");
break;
case 3: int i;
i=countleaf(T);
cout<<"所求二叉树叶子结点为"<<i;
cout<<endl;
break;
case 4: int j;
j=treedepth(T);
cout<<"所求二叉树深度为"<<j;
cout<<endl;
break;
case 0:printf("再见");
exit(0);
break;
}
}
return 0;
}

全部回答
先序遍历中第一个元素为根,根据此根把中序序列分为左右子树,确定左右子树中包含的元素后再分别在先序序列中确定左右子树的树根,依次找出左右子树的树根。。。 (先序中序可以,后序中序也可以,必须要有中序哟~) 不知道说的够清楚吗
#include using namespace std; class node { public: node(){ this->plchild = this->prchild = null; } char data; node * plchild; node * prchild; }; node * createtree() { node * root = new node; root->data = 'a'; node * pb = new node; pb->data = 'b'; node * pc = new node; pc->data = 'c'; node * pd = new node; pd->data = 'd'; node * pe = new node; pe->data = 'e'; root->plchild = pb; root->prchild = pc; pc->plchild = pd; pd->prchild = pe; return root; } void intraversetree(node * pt) //中序遍历 { if (null == pt) return; else { intraversetree(pt->plchild); cout << pt->data; intraversetree(pt->prchild); } } void posttraversetree(node * pt) //后序遍历 { if (null == pt) return; else { posttraversetree(pt->plchild); posttraversetree(pt->prchild); cout << pt->data; } } void pretraversetree(node * pt) //先序遍历 { if (null==pt) { return; } else { cout << pt->data; pretraversetree(pt->plchild); pretraversetree(pt->prchild); } } void destroytree(node * pt) //销毁二叉树 { if (null == pt) return; else { destroytree(pt->plchild); destroytree(pt->prchild); delete pt; } } int main() { node * pt = createtree(); cout << "先序遍历"; pretraversetree(pt); destroytree(pt); // pretraversetree(pt); //cout << endl; system("pause"); return 0; } 用c++写的 不过跟c没什么区别
在先序遍历序列中找到第一个元素作为当前树的树根,这个元素的下一个元素只能是它的左孩子或者右孩子,那么在中序序列中如果这第二个元素出现在根元素的左边就是左孩子,否则是右孩子,重复这个过程可以处理所有元素
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
珍珠商务客房地址在什么地方,想过去办事
五粮春宝轮佳酿总经销怎么去啊,有知道地址的
为什么生成1mol Si就形成了2mol Si-Si键Si不
家里的小猫总是把柜子上的东西弄下摔坏,怎么
大宅门海鲜小炒(星海店)地址在什么地方,想过
昌盛快捷地址好找么,我有些事要过去
武夷山景区最贵的房子
limx→0+(x^sinx)求极限
爱尔卡集成厨电地址在什么地方,想过去办事
星都汇主题客房怎么去啊,我要去那办事
新菜品上柜申请怎么写
框架结构与剪力墙结构相比,下列叙述正确的是
包圣殿村地址在哪,我要去那里办事
博途13支持400为什么还用pcs7
我堂弟总是缠着我男朋友借钱,怎么办啊? 我
推荐资讯
怎样找准穴位的准确位置
耳蜗起皮的原因是什么
男朋友的妹妹过生日 求留言
福代安全门地址在什么地方,想过去办事
国都美发名店在什么地方啊,我要过去处理事情
翰林国际教育这个地址在什么地方,我要处理点
(8分)某生物小组的同学利用营养液培养植物
solidworks受力分析结果中有一项位移指标为 1
空心大少爷柠檬头的表妹叫什么
1992年农历8月23日早上8点多生的。我的财运?
1000平方等于100乘100乘100.代表什么成语
怎么背好生物和地理
正方形一边上任一点到这个正方形两条对角线的
阴历怎么看 ?