首页 > 代码库 > 根据二叉树的两种遍历求二叉树的结构
根据二叉树的两种遍历求二叉树的结构
二叉树的前序遍历顺序是:根节点,左树,右树
中序遍历顺序是:左树,根节点,右树
后序遍历顺序是:左树,右树,根节点
上面这棵树的前序遍历是:abfcjm 中序遍历是:fbcamj 后序遍历是:fcbmja
根据前序遍历和后序遍历是不能求出树的唯一结构的,
已知的两种遍历顺序必须必须包括中序遍历,因为中序遍历能够递归的推出根节点的左树和右树
如上题已知 前序遍历是:abfcjm 中序遍历是:fbcamj 那么根据前序遍历就可以知道树根是a,
再根据中序遍历就可以知道以a为根节点左树节点包括fbc右树节点包括mj,
再根据前序遍历的第二个节点可知b是a的左子节点,又根据中序遍历可知b的左树是f右树是c,
重复以上步骤递归求解就可以推出整个树的结构了,
最后根据整个树的结构就可以推出来后续便利的顺序了。
本文出自 “开发者” 博客,请务必保留此出处http://tang1513.blog.51cto.com/7678175/1566669
根据二叉树的两种遍历求二叉树的结构
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。