当前位置: 首页 > news >正文

部门网站建设的意义个人网站可以做音乐下载网

部门网站建设的意义,个人网站可以做音乐下载网,简易h5制作开发,今天建设银行网站无法登录题目链接: 二叉树遍历_牛客题霸_牛客网二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问根,然后遍历其左子树,最。题目来自【牛客题霸】https://www.nowcoder.com/share/jump/43719512169…

题目链接:

二叉树遍历_牛客题霸_牛客网二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问根,然后遍历其左子树,最。题目来自【牛客题霸】https://www.nowcoder.com/share/jump/437195121692587727256

描述

二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树; 中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树; 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。 给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。

输入描述:

两个字符串,其长度n均小于等于26。 第一行为前序遍历,第二行为中序遍历。 二叉树中的结点名称以大写字母表示:A,B,C....最多26个结点。

输出描述:

输入样例可能有多组,对于每组测试样例, 输出一行,为后序遍历的字符串。

示例1

输入:

ABC
BAC
FDXEAG
XDEFAG

输出:

BCA
XEDGAF

思路:

先来一个例子:

先序遍历序列为:FDXEAG

中序遍历序列为:XDEFAG

要根据先序序列和中序序列确定这个二叉树,通用的步骤为:

1.根据先序序列的第一位确定这棵树的根;

2.在中序序列中找到根的所在的位置,根的左边就是该树的左子树的节点,根的右边就是该树的右子树的节点;

3.根据树的左子树节点和右子树节点在先序序列中分别找到对应的子串;

4.对3中找到的两个子串分别重复1 2 3步,左子树节点用于构建左子树,右子树节点用于构建右子树,直到所有的节点都用于构建这棵树。

示例:

根据以上的案例走一遍:

1.由先序遍历序列为:FDXEAG可知,树的根节点为F;

2.在中序遍历序列XDEFAG找到F的索引为3,左边XDE就是该树的左子树的节点,右边AG就是该树的右子树的节点;

3.根据树的左子树节点XDE和右子树节点AG在先序序列中分别找到对应的子串,分别为:DXE和AG;

4.对DXE和AG分别重复步骤1 2 3,DXE用于构建左子树,AG用于构建右子树,直到所有的节点都用于构建树。

每执行完第一轮步骤1 2 3,所用的根节点已经用于构建树了,后续就不用再考虑了。例如,执行完第一轮步骤1 2 3,根节点F已经用过了,后续就不用再考虑了。

分析:

相信思路都很明确,步骤大概也明白了,接下来代码实现中一个非常注重细节的地方就是递归构建左子树和右子树的部分,再详细说就是在递归调用构建树的函数中,我们要传入的两个参数应该怎么确定。

本次主要介绍利用先序遍历序列和中序遍历构建一个二叉树并输出后序遍历的方法,我们在递归调用构建树的函数中,我们要传入的两个参数当然就是子树的先序遍历序列和中序遍历序列。创建左子树时就传入左子树的先序遍历序列和中序遍历序列,创建右子树时就传入右子树的先序遍历序列和中序遍历序列。

以下根据以上案例详细分析:对于:

索         引:012345
先序遍历序列为:FDXEAG中序遍历序列为:XDEFAG

将以上两个遍历序列分别命名为字符串s1,s2,即s1 = "FDXEAG", s2 = "XDEFAG"。根据s1可知树的根为F,在s2中寻找到F的索引(定义为pos)为3。根据s2可得左子树包括的字符有:XDE(由s2.substr(0, pos)获得),右子树包括的字符有:AG(由s2.substr(pos+1)获得),在s1中对应的字符串分别为:DXE(由s1.substr(1, pos)获得)和AG(由s1.substr(pos+1)获得)。根据以上获得的四个参数,可以递归创建左子树和右子树。

源代码:

//根据先序遍历和中序遍历确定一个二叉树
// 二叉树节点结构定义
struct TreeNode {char data;TreeNode* leftChild;TreeNode* rightChild;TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL){}
};// 根据先序遍历和中序遍历构建二叉树
TreeNode* Build(string str1, string str2) {if (str1.size() == 0) {return NULL;}// 取先序遍历的第一个字符作为根节点char c = str1[0];// 在中序遍历中找到根节点的位置int pos = str2.find(c);// 创建根节点TreeNode* root = new TreeNode(c);递归构建左子树root->leftChild = Build(str1.substr(1, pos), str2.substr(0, pos));递归构建右子树root->rightChild = Build(str1.substr(pos + 1), str2.substr(pos + 1));return root;
}// 后序遍历输出
void postOrder(TreeNode* root) {if (root == NULL) {return;}//先遍历左子树postOrder(root->leftChild);//再遍历右子树postOrder(root->rightChild);//输出当前根节点的值cout << root->data;return;
}int main()
{string s1, s2;while (getline(cin, s1)) {getline(cin, s2);TreeNode* root = Build(s1, s2);postOrder(root);cout << endl;}return 0;
}

示例运行结果:

http://www.yayakq.cn/news/668995/

相关文章:

  • 网站建设付费项目互联网有多少网站
  • 制作网站协议快看点自媒体平台注册账号入口
  • 泉州制作网站开发iis网站突然无法访问
  • 企业 网站设计网页制作基础教程第二版葛艳玲
  • 网站备案密码找回江西中企动力做的网站
  • 微信公众号开发网站开发百度联盟推广
  • 大连市住房和建设局网站大型软件公司有哪些
  • 网站服务商查询免费门户网站
  • 重庆建站公司哪个好江苏缘生源建设工程有限公司网站
  • 网站开发与系统开发公司部门解散怎么赔偿员工
  • 十堰网站seo技巧wordpress 无法更换会员注册页面
  • 网站建设后需要录入厦门 建网站
  • 传统网站设计微商城分销系统设计|分销电商系统app软件
  • 长沙最新招聘信息最新消息wordpress怎么做seo关键词
  • 网站怎么在工信部备案信息查询wordpress设置cdn缓存
  • 义乌官网制作网站大学网站建设论文
  • 做支付网站音乐网站开发需求文档模板
  • 网站开发工具安全性能公司变更法人的流程
  • 上海哪里可以做网站范县网站建设价格
  • 网站策划及过程深圳宝安机场
  • 中小型电子商务网站有哪些wordpress设置滑动效果
  • 已经有域名 如何建设网站网站功能需求用什么做
  • 网站不备案有什么后果如何下载ppt模板免费下载
  • 三亚网站建设公司荆门网站制作公司
  • 网站页面组成那个网站有帮人做图的
  • 小型网站运营网站刷链接怎么做
  • 学前教育网站建设免费自助建站系统
  • 网站排名做不上去vs怎样建设新网站
  • 做相册的网站(网易建筑二级建造师培训机构
  • 网站开发个人博客做的漂亮的商务网站