在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1261|回复: 6
收起左侧

[树/链表/图] 前序遍历 OR 后序遍历

[复制链接] |试试Instant~ |关注本帖
WhatsFLAG 发表于 2016-10-25 05:50:25 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
我想请教一下,在树的遍历过程中,前序遍历和后序遍历对于解决问题的区别。

首先,概念上我是认可 前序遍历描述了一个自顶向下的过程,而后序遍历描述了一个自底向上的过程。但是仔细分析一下会发现计算机实现的过程其实都是自底向上实现的,所以我感觉前序遍历 和 后序遍历是本质上是一样的。所以想问一下这两种遍历各自代表的是什么,相对应解决那些问题,有什么区别和联系呢?

评分

1

查看全部评分

stellari 发表于 2016-10-25 13:20:57 | 显示全部楼层
Top-down和Bottom-up这两个词在不同的context下,具体意义会有些区别。比如,同样的算法。人们可能会把使用递归实现的方法统一称作Top-down,而使用迭代法的算法称作Bottom-up。这里的TD和BU指的是implementation方式层面的TD和BU。而二者实现的算法其实是相同的。

而我们说preorder和postorder分别是TD和BU,则代表了算法本质的差别。这时的TD和BU代表了两种完全不同的算法,即使它们都用递归或都用迭代实现。

如果上层函数的执行顺序是直接把input拆成两半,分别递归调用子函数。每个子函数得到一半的结果,然后再由上层函数把着两半结果拼成一个完整结果。这叫做bottom-up递归。最明显的例子,就是mergesort和post-order。之所以这种情况是bottom-up,是因为你看最后的元素处理顺序是局部到整体。比如mergesort,最先被执行的交换都是局部交换:0和1换, 1和2换...然后才可能出现0和3换……最后一步才可能出现1和n, 2和n-1这种交换。post-order同理,最先被访问的是最基层的节点。

反之,如果是上层函数先对input做一定的处理,然后再递归调用函数分别对被处理好的input一半做处理。两半递归结束后,答案自然成型,上层函数不需要再做任何事情了。这叫做bottom-up递归。最典型的例子是quicksort和pre-order。quicksort最开始出现的交换全是整个数组范围内的交换:1和n交换,2和n-1交换……直到最后才变成局部的0和1,1和2……交换。一旦所有局部交换都完成,那数组就自然排好了。这种递归是整体到局部,所以是top-down.

区分两者你就记住一个原则就好:看算法是“先递归再处理”(bottom-up),还是"先处理再递归"(top-down)
回复 支持 1 反对 0

使用道具 举报

全球28万学生4.7分推荐
 楼主| WhatsFLAG 发表于 2016-10-25 13:56:05 | 显示全部楼层
stellari 发表于 2016-10-25 13:20
Top-down和Bottom-up这两个词在不同的context下,具体意义会有些区别。比如,同样的算法。人们可能会把使用 ...

感谢您精彩的回复,那么您认为先序,中序,后序三种对树的遍历方式,实质上的区别究竟是什么呢?
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-10-25 14:15:32 | 显示全部楼层
你觉得都是自上而下是因为你写成了递归....stack call无论你写什么玩意它都是自上而下的. 这跟算法没关系.
回复 支持 反对

使用道具 举报

adrianliu729 发表于 2016-10-25 16:03:19 | 显示全部楼层
WhatsFLAG 发表于 2016-10-25 13:56
感谢您精彩的回复,那么您认为先序,中序,后序三种对树的遍历方式,实质上的区别究竟是什么呢?

The easiest answer is that the order of the traversal is different.
回复 支持 反对

使用道具 举报

 楼主| WhatsFLAG 发表于 2016-10-26 00:04:09 | 显示全部楼层
adrianliu729 发表于 2016-10-25 16:03
The easiest answer is that the order of the traversal is different.

Instead of only one order, why do we need the other two orders?
回复 支持 反对

使用道具 举报

pogo 发表于 2016-11-11 01:55:19 | 显示全部楼层
“先递归再处理”(bottom-up),还是"先处理再递归"(top-down)-----好赞!
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-23 15:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表