B - 数据结构上机测试4.1:二叉树的遍历和应用1
Description
输入二叉树的先序遍历序列和中序遍历序列,输出该二叉树的后序遍历序列。
Input
第一行输入二叉树的先序遍历序列;
第二行输入二叉树的中序遍历序列。
Output
输出该二叉树的后序遍历序列。
Sample
Input
ABDCEF
BDAECF
Output
DBEFCA
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char str1[100],str2[100];
int len;
struct node{
struct node *lchild,*rchild;
int date;
};
struct node *create(int len,char *str1,char *str2)
{
int i;
struct node *root;
if(len==0)
return NULL;
root=(struct node*)malloc(sizeof(struct node));
root->date=str1[0];
for(i=0;i<len;i )
{
if(str2[i]==root->date)
break;
}
root->lchild=create(i,str1 1,str2);//左子树,确定了str2第i个输入等于根节点后,左边的都是左子树上的点。因为中序是左-根-右。所以,第i-1之前的结点都是左子树上的点。长度为i,str1 1的意思是从str1之后的那个点开始,因为str1第一个点是根节点,所以,左子树的根,要从下一个点开始。当i一直减少等于0的时候,就返回NULL。
root->rchild=create(len-i-1,str1 i 1,str2 i 1);//右子树,因为找到了根节点的位置,是i,所以,右子树的长度为i 1到len-(i 1),简单整理一下就是len-i-1,右子树的左子树从str1 i 1开始,右子树的右子树从str2 i 1开始。简单解释一下,以右子树的左子树为例,str1 i,这个代表了根节点的位置,根节点的下一个就是右子树的开始,所以str1 i 1。右子树的右子树同理。
//这是我的理解,有不对的地方还请指出。
return root;
};
void hou(struct node *root)
{
if(root)
{
hou(root->lchild);
hou(root->rchild);
printf("%c",root->date);
}
}
int main()
{
scanf("%s",str1);
scanf("%s",str2);
struct node* root;
len=strlen(str1);
root=create(len,str1,str2);
hou(root);
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggfhea
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13