codevs1013求先序排列

关键词：

题目链接：http://codevs.cn/problem/1013/

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 
 5 #define MaxSize 100
 6 
 7 typedef char ElemType;
 8 typedef struct node 
 9 {    
10     ElemType data;            //数据元素
11     struct node *lchild;    //指向左孩子结点
12     struct node *rchild;    //指向右孩子结点
13 } BTNode;
14 
15 BTNode *CreateBT2(char *post,char *in,int n)
16 /*post存放后序序列,in存放中序序列,n为二叉树结点个数,
17 本算法执行后返回构造的二叉链的根结点指针*/
18 {
19     BTNode *s;
20     char r,*p;
21     int k;
22     if (n<=0) return NULL;
23     r=*(post+n-1);                            //根结点值
24     s=(BTNode *)malloc(sizeof(BTNode));        //创建二叉树结点*s
25     s->data=r;
26     for (p=in;p<in+n;p++)                    //在in中查找根结点
27         if (*p==r)
28             break;
29     k=p-in;                                    //k为根结点在in中的下标
30     s->lchild=CreateBT2(post,in,k);            //递归构造左子树
31     s->rchild=CreateBT2(post+k,p+1,n-k-1);    //递归构造右子树
32     return s;
33 }
34 void PreOrder1(BTNode *b)    //先序非递归遍历算法
35 {
36     BTNode *St[MaxSize],*p;
37     int top=-1;
38     if (b!=NULL) 
39     {   
40         top++;                        //根结点进栈
41         St[top]=b;
42         while (top>-1)                //栈不为空时循环
43         {
44             p=St[top];                //退栈并访问该结点
45             top--;
46             printf("%c",p->data);
47             if (p->rchild!=NULL)    //右孩子结点进栈
48             {
49                 top++;
50                    St[top]=p->rchild;
51             }
52             if (p->lchild!=NULL)    //左孩子结点进栈
53             {
54                 top++;
55                    St[top]=p->lchild;
56             }
57         }
58         printf("
");
59     }
60 }
61 int main(int argc, char *argv[])
62 {
63     char str1[MaxSize],str2[MaxSize];//str1:中序序列，str2：后序序列 
64     BTNode *bt;
65     scanf("%s%s",str1,str2);
66     bt=CreateBT2(str2,str1,strlen(str1));
67     PreOrder1(bt);
68     return 0;
69 }

codevs1013求先序排列2001年noip全国联赛普及组x

            题目描述Description给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。输入描述InputDescription两个字符串，分别是中序... 查看详情

2001求先序排列

题目描述 Description给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。输入描述 InputDescription两个字符串，分别是中序和后序（每行一个）输出描述 OutputDescripti... 查看详情

求先序排列

 时间限制:1s 空间限制:128000KB 题目等级:黄金Gold题解 查看运行结果  题目描述 Description给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。输入... 查看详情

求先序排列

题目描述给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。输入输出格式输入格式： 2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。 输... 查看详情

算法训练求先序排列

...别表示中序和后序排列输出格式　　一个字符串，表示所求先序排列　　样例输入　　BADC　　BDCA样例输出ABCD1importjava.math.BigInteger;2importjava.util.Arrays;3importjava.util 查看详情

luogu1030求先序排列

https://www.luogu.org/problemnew/show/1030题目描述给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。输入输出格式输入格式：2行，均为大写字母组成的字符串，表示一棵二叉树... 查看详情

求先序排列(代码片段)

题目描述给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度≤8\le8≤8）。输入输出格式输入格式：222行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。输出... 查看详情

p1030求先序排列

题目描述给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。输入输出格式输入格式：2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。输出格式：1... 查看详情

蓝桥-求先序排列（知中序和后序求先序）(代码片段)

...符串，分别表示中序和后序排列Output一个字符串，表示所求先序排列SampleInputBADCBDCASampleOutputABCD  1#include<bits/stdc++.h>2constintINF=0x3f3f3f3f;3typedeflonglongLL;4constdoubleeps=1e-8;5constintmod=1e9+7;6constintmaxn=1e5+10;7usingnamespacestd;89stringa;... 查看详情

p1030求先序排列(代码片段)

这道题很重点啊。。。首先是对树的理解，了解先序、中序、后序的排列再自己找出排列的规律。初学树状结构做这道题能加深自己的理解。以及判定范围。。。40分惨痛教训。。。 传送门题目描述给出一棵二叉树的中序与... 查看详情

(蓝桥杯)试题算法训练求先序排列(代码片段)

试题算法训练求先序排列资源限制时间限制：1.0s内存限制：256.0MB问题描述　　给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。输入格式　　两... 查看详情

hdu_1030求先序排列

#include<bits/stdc++.h>usingnamespacestd;stringa,b;intn;voiddfs(intl,intr){ intnow=0; for(inti=n-1;i>=0;i--)if(!now) for(intj=l;j<=r;j++)if(b[i]==a[j]){now=j;break;} putchar(a[now]); if(n 查看详情

洛谷p1030求先序排列

这是一道图论模板题，用分治的策略即可轻松AC！#include<bits/stdc++.h>usingnamespacestd;stringst1,st2,s1,s2;voidbuild(stringst1,stringst2){ intlen=st1.length(); if(len==0)return; cout<<st2[len-1]; intp=st1.find(s 查看详情

洛谷p1030求先序排列label:none

题目描述给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。输入输出格式输入格式： 2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。 输... 查看详情

已知前序和中序求后序，已知中序和后序求先序。

  查看详情

二叉树重建，中序+后序求先序

tree(i-la,la,lb-n-la+i);tree(n+la-i-1,i+1,lb-1); 不用数字转#include<iostream>usingnamespacestd;stringa,b;inlinevoidtree(intn,intla,intlb){if(n<=0)return;for(inti=la;i<=la+n-1;i++){if(a[i]= 查看详情

数据结构——已知先序中序求后序，已知中序后序求先序(代码片段)

　　总结下二叉树的已知两种遍历方式求第三种遍历顺序的方法，已知先序和中序遍历或者后序与中序遍历后二叉树是唯一确定的，下面介绍怎么求出第三种遍历顺序。　　先序遍历顺序为：根结点——左子结点—&mdash... 查看详情

二叉树--已知先序中序求后序--已知中序后序求先序（基本按照网上某大神思路搬过来的）

思路来自（转载自） http://www.cnblogs.com/fzhe/archive/2013/01/07/2849040.html题目描述不说了。前序遍历: GDAFEMHZ中序遍历: ADEFGHMZ求中序遍历。1确定根,确定左子树，确定右子树。2在左子树中递归。3在右子树中递归。4打印当前... 查看详情