搜索内容

有一个问题?

如果您有任何疑问,可以在下面询问或输入您要寻找的!

算法训练 求先序排列(递归 ,蓝桥杯C++,简洁算法、代码)

生成海报
金牌射手朱小崐
金牌射手朱小崐 2021-02-06 00:37
阅读需:0

优化算法训炼 求先序排序

資源限定
时间限制:1.0s 运行内存限定:256.0MB
难题叙述
  得出一棵二叉树的中序与之后排序。算出它的先序排序。(承诺树节点用不一样的英文大写字母表明,长短<=8)。
键入文件格式
  二行,每排一个字符串数组,各自表明中序和之后排序
輸出文件格式
  一个字符串数组,表明所愿先序排序

示例键入
  BADC
  BDCA
示例輸出
ABCD

序言:尽管它是一道很基本的一道题,可是我看到一种出色构思,我也要想纪录到blog里。

构思与分析:

这是一个给中序和之后求先序的题,大家大约的观念便是在先序中找到和之后最终一个字符(头节点)一样的标识符的部位,复印出去,随后他的左边便是左小孩,右边便是右小孩,随后再将左小孩的串递归进来,找根上下,沒有左小孩了return回家找右小孩,在将右小孩串找左小孩,递归递归递归 递归……

1、例如大家拿事例中的
中序:BADC
之后:BDCA

最先在中国序寻找之后的最终一个字符 “A” , 寻找他的字符是 1 ,并打印A,由于他是根,随后这时候之后就剩DBC,中序分成了左子串“B”和右子串“DC”。

for(int i = 0;i < r1 ;i++)		//解析xml中序中连接点
    {
        if(a[i] == b[r2 - 1])	//寻找和结尾一样的标识符
        {
            printf("%c",a[i]);	//复印根
            k = i;				//纪录字符
        }
    }

2、大家再依次把他的左子树和右子树递归进来

 if( k > l1) tree(l1, k, l2, l2 + k - l1);
 if(k + 1 < r1) tree(k+1, r1,l2 + k - l1,r2 -1);

k是根节点再中序串中的座标,那麼假如根节点的座标没有中序串的第一个部位,即 k > l1 ,则意味着他也有左小孩,那麼就打开网址他的左小孩,那麼左小孩的临界值座标应该是 l1和 k (这儿为什么是k而不是k - 1,是由于在每一次解析xml是以i = 0;i < r1 ;i++,因此 i 是< k的),右小孩的临界值座标是 l2 和 l2 + k - l1,我们知道之后串中根节点的左小孩一定是以字符为0逐渐的,由于是上下根嘛,那麼左临界值是l2没有问题,那麼右临界值就是以l4开始往右边数左小孩的数量,例如左小孩只有一个B,那便是挪动一位,即 l2 + k - l1,(k - l1 就意味着在根节点以前左小孩长短多少钱),那麼直至沒有左小孩了以后递归出去,逐渐递归右小孩,同样k+1, r1,l2 + k - l1,r2 -1这四个主要参数我觉得也无需多讲,k的下一位到最右边,和左小孩右边逐渐到最终早已复印过的连接点字符以前。

那麼到这儿早已很详尽的表明了递归全过程,下边就上详细编码:

#include
#include
using namespace std;
 char a[10];
 char b[10];

int tree(int l1,int r1,int l2,int r2)//中序之后逐渐都是0到r1
{
	int k;
	for(int i = 0;i < r1 ;i++)
    {
        if(a[i] == b[r2 - 1])		//寻找根
        {
            printf("%c",a[i]);		//复印根
            k = i;			//纪录字符
        }
    }
    if( k > l1) tree(l1, k, l2, l2 + k - l1);	//如果有左小孩就一直递归
    if(k + 1 < r1) tree(k+1, r1,l2 + k - l1,r2 -1);		//左小孩递归完后后逐渐递归右小孩
}
int main()
{
    scanf("%s",a);
    scanf("%s",b);
    int lenth1 = strlen(a);			//length 是中序
    int lenth2 = strlen(b);			//length 是之后
    tree(0,lenth2,0,lenth2);
	return 0;
}


在大家学好得出 中 后 算先序,大家再试一下得出中 先 算之后(自然不太可能是给依次算中序,由于要是没有中序你没法明确上下小孩的部位)

我依据一样的观念也想到了类似的方式
大家的观念還是一样,最先寻找根节点(中序遍历和先序的第一个做 == )

for(int i = 0;i < r1 ;i++)
    {
        if(a[i] == b[l2])
        {
            k = i;
        }
    }

可是找到并不复印,只是递归他的上下子串,直至最下边的连接点早已沒有小孩(上下也没有)了,复印该连接点


	if( k > l1) tree(l1 , k, l2 + 1 , l2 + 1  + k - l1);//cout<<"1";
    if(k + 1 < r1) tree(k+1, r1,l2 + 1 + k - l1,r2);
    printf("%c",a[k]);

这儿的上下临界值大伙儿自身去思索一下为何吧,时尚博主就不会再表述了,和上边的如出一辙;

详细编码:

#include
#include
using namespace std;
 char a[10];
 char b[10];

int tree(int l1,int r1,int l2,int r2)
{
	int k;
	for(int i = 0;i < r1 ;i++)
    {
        if(a[i] == b[l2])
        {
            k = i;
        }
    }
    if( k > l1) tree(l1 , k, l2 + 1 , l2 + 1  + k - l1);//cout<<"1";
    if(k + 1 < r1) tree(k+1, r1,l2 + 1 + k - l1,r2);
     printf("%c",a[k]);
}
int main()
{
    scanf("%s",a);
    scanf("%s",b);
    int lenth1 = strlen(a);
    int lenth2 = strlen(b);
    tree(0,lenth2,0,lenth2);
	return 0;
}

后语:这道题看过巨头的文章内容构思顿开,自身也再次计算出了给先中序求之后的编码,今日收获满满,假如文章内容另当别论,还期待大伙儿多多的不吝赐教!

相关标签:
评论
  • 消灭零回复