1. 首页
  2. 数据结构

二叉树根据前序中序求后序~~

二叉树

前序遍历顺序: 根节点、左子树、右子树

中序遍历顺序: 左子树、根节点、右子树

后序遍历顺序: 左子树、右子树、根节点

可以发现,二叉树前序中的第一个节点为树的根节点root,然后找出root在中序里面的位置,就可以把前序和中序分别划分为左、右子树两个部分,然后递归调用即可。

举个例子,前序 5 3 2 4 8 6 10 中序 2 3 4 5 6 8 10

首先,5肯定是二叉树的根节点,然后5在中序里面的位置是3号(从0开始),此位置前面的是左子树中的节点,右面的是右子树的节点,即5 || 3 2 4|| 8 2 6 , 2 3 4 || 5 || 6 8 10,对红色的左子树序列、蓝色的右子树序列继续上述过程,直至结束。

已知前序中序求后序:

已知后序中序求前序:

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/1031 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

1 条评论

gravatar

  1. 小包子 2016-08-06 Google Chrome 52.0.2743.82Windows 10

    签到成功!签到时间:上午12:38:09每日打卡,生活更精彩哦~

    回复 沙发
  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40