首页 / C语言 / C语言 · 求先序遍历

C语言 · 求先序遍历

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C语言 · 求先序遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1526字，纯文字阅读大概需要3分钟。

内容图文

算法训练 求先序排列  
时间限制：1.0s   内存限制：256.0MB
      
锦囊1
　　后序的最后一个字母为根结点。
 
问题描述
　　给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
输入格式
　　两行，每行一个字符串，分别表示中序和后序排列
输出格式
　　一个字符串，表示所求先序排列
　　样例输入
　　BADC
　　BDCA
样例输出
ABCD
 
作者注释：解此题，狠狠的复习了一把先、中、后序遍历二叉树。针对此题的笔记如下：
 
先序、中序、后序分别用pre、in、last数组表示。
　　1、后序的最后一个节点必为根节点；
　　2、在中序里由根节点可划分左右子树；
　　3、根节点就是要往先序中填充的节点；
　　4、递归左右子树。
 
递归体的四个参数：
　　instart:中序起始位置；
　　insend:中序终止位置；
　　lastroot:后序根节点(即后序最后一个节点)；
　　preindex:欲填充的先序位置。
 
在中序中：
　　左子树根节点 = 上一个后序根节点 - 右子树长度；
　　右子树根节点 = 上一个后序根节点 - 1.
 
左子树根节点：
　　lastroot - [(inend - i) + 1];
右子树根节点：
　　lastroot - 1;
左子树的根节点插入先序中的位置：
　　preindex + 1;
右子树的根节点插入先序中的位置：
　　[(i - instart) + 1] + preindex;(其中i为中序中根节点的下标);
 
递归体：
　　对于左子树：dfs(instart, i - 1, lastroot - [(inend - i) + 1], preindex + 1);
　　对于右子树：dfs(i + 1, inend, lastroot - 1, preindex + [(i - instart) + 1]);
 
代码：
                     1
                    /*
                     2
                    DEABFCHG

                     3
                    DEAFHGCB

                     4
                    */
                     5 #include<stdio.h>
 6 #include<string.h>
 7 #include<stdlib.h>
 8char pre[10],in[10],last[10];//数组规模比预算稍微设置大一点  9void dfs(int instart,int inend,int lastroot,int preindex){
10if(instart>inend) return;//出口 11for(int i=instart;i<=inend;i++){
12if(in[i] == last[lastroot]){
13             pre[preindex] = in[i];
14             dfs(instart,i-1,lastroot-(inend-i)-1,preindex+1);//左子树15             dfs(i+1,inend,lastroot-1,preindex+(i-instart)+1);//右子树16return; 
17        }
18    }
19}
20int main(){
21     scanf("%s",&in);//录入中序,后序 22     getchar();//处理回车 23     scanf("%s",&last);
24int leni = strlen(in);
25int lenl = strlen(last);
26     dfs(0,leni-1,lenl-1,0);
27     printf("%s",pre);
28return0;
29 }

 

 

C语言 · 求先序遍历

原文：http://www.cnblogs.com/panweiwei/p/6666645.html

内容总结

以上是互联网集市为您收集整理的C语言 · 求先序遍历全部内容，希望文章能够帮你解决C语言 · 求先序遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1326668.html

来源：【匿名】