首页 > 试题广场 >

证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。

[问答题]
证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。
添加回答
推荐
赞花婆头像 赞花婆
因为知道先序遍历后,第一个根是唯一确定的.然后在中序遍历里这个根将它分为两个部分,第一个根的两棵子树的根也会唯一确定,依次此类推,所有子树的根都唯一确定,二叉树就是唯一的.
发表于 2018-03-25 10:05:46 回复(0)
快乐程序员头像 快乐程序员
  1. 二叉树先序遍历是先访问根，然后访问左子树，最后访问右子树；中序遍历先访问左子树，然后访问根，最后访问右子树。
  2. 首先从先序遍历获取第一个节点即为根节点，然后再中序遍历结果集中找到根节点的位置，根节点的位置左侧节点即为二叉树的左子树，右侧即为右子树；
  3. 重复步骤2，利用迭代的方式依次确定各个节点在二叉树中的位置。
发表于 2019-11-04 19:50:16 回复(0)
提交观点

问题信息

树
上传者：赞花婆
难度：
2条回答 4345浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号