博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【树】求先序遍历
阅读量:6612 次
发布时间:2019-06-24

本文共 805 字,大约阅读时间需要 2 分钟。

题目


题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示)。

输入输出格式

输入格式:

2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列。
输出格式:
1行,表示一棵二叉树的先序。

思路


首先,一点基本常识,给你一个后序遍历,那么最后一个就是根(如ABCD,则根为D)。

因为题目求先序,意味着要不断找根。
中序ACGDBHZKX,后序CDGAHXKZB,首先可找到主根B;
那么我们找到中序遍历中的B,由这种遍历的性质,可将中序遍历分为ACGD和HZKX两棵子树,
那么对应可找到后序遍历CDGA和HXKZ(从头找即可)
从而问题就变成求1.中序遍历ACGD,后序遍历CDGA的树 2.中序遍历HZKX,后序遍历HXKZ的树;
接着递归,按照原先方法,找到1.子根A,再分为两棵子树2.子根Z,再分为两棵子树。
就按这样一直做下去(先输出根,再递归);
模板概括为step1:找到根并输出
step2:将中序,后序各分为左右两棵子树;
step3:递归,重复step1,2;

Code


#include
#include
#include
using namespace std;void beford(string in,string after){ if (in.size()>0){ char ch=after[after.size()-1]; cout<
>inord;cin>>aftord;//读入 beford(inord,aftord);cout<

转载于:https://www.cnblogs.com/gongdakai/p/11066351.html

你可能感兴趣的文章
HDUPhysical Examination(贪心)
查看>>
Android官方架构组件LiveData: 观察者模式领域二三事
查看>>
你必须知道的HTTP基本概念
查看>>
Android ContentProvider调用报错"Bad call:..."及相关Binder权限问题分析
查看>>
基本shell脚本的编辑及变量
查看>>
加密和解密 tar
查看>>
将datatable 保存为 Excel文件(高效率版本)
查看>>
C/C++五大内存分区(转)
查看>>
CentOS 6.5下PXE+Kickstart无人值守安装操作系统
查看>>
xtrapivotcontrol 控件用法及相关属性
查看>>
Shell脚本 常用命令总结 二
查看>>
JS模拟select下拉菜单
查看>>
vmware workstation14永久激活密钥分享
查看>>
iOS 多线程 之 GCD(大中枢派发)(一)
查看>>
Myeclipse中打开接口实现类的快捷键
查看>>
删除sql dump中的AUTO_INCREMENT
查看>>
使用JdbcTemplate和JdbcDaoSupport
查看>>
C博客作业--指针
查看>>
版本12.2.0.1.0数据库,复制种子数据库快速创建租户数据库PDB
查看>>
Glibc 和 uClibc
查看>>