Go语言实现二叉树遍历

Python031

Go语言实现二叉树遍历,第1张

图例如下:

结果应该是分别是:

广度优先: a ->b ->c ->d ->f ->e ->g

先序遍历: a ->b ->d ->e ->f ->g ->c

中序遍历: e ->d ->b ->g ->f ->a ->c

后序遍历: e ->d ->g ->f ->b ->c ->a

结果存在result里面,如果不存可以少一层变量

这个地方强烈建议读一下下面的第一个链接,我遵照着那篇文章实现的,只是用Go改写了而已。

首先定义一个数据结构,用来存储一些Node的信息。

这里是可以运行的,但是总会抛出一个数组越界的错误,我看了半天也没看出来哪里有问题,Mac版的devel我这边又有bug,没用起来。至少思路对了,我后面再看一下哪里的问题。(感谢 @RiXu 指正)

在linux下实现定时器主要有如下方式

在这当中 基于时间轮方式实现的定时器 时间复杂度最小,效率最高,然而我们可以通过 优先队列 实现时间轮定时器。

优先队列的实现可以使用最大堆和最小堆,因此在队列中所有的数据都可以定义排序规则自动排序。我们直接通过队列中 pop 函数获取数据,就是我们按照自定义排序规则想要的数据。

在 Golang 中实现一个优先队列异常简单,在 container/head 包中已经帮我们封装了,实现的细节,我们只需要实现特定的接口就可以。

下面是官方提供的例子

因为优先队列底层数据结构是由二叉树构建的,所以我们可以通过数组来保存二叉树上的每一个节点。

改数组需要实现 Go 预先定义的接口 Len , Less , Swap , Push , Pop 和 update 。

timerType结构是定时任务抽象结构

首先的 start 函数,当创建一个 TimeingWheel 时,通过一个 goroutine 来执行 start ,在start中for循环和select来监控不同的channel的状态

通过for循环从队列中取数据,直到该队列为空或者是遇见第一个当前时间比任务开始时间大的任务, append 到 expired 中。因为优先队列中是根据 expiration 来排序的,

所以当取到第一个定时任务未到的任务时,表示该定时任务以后的任务都未到时间。

当 getExpired 函数取出队列中要执行的任务时,当有的定时任务需要不断执行,所以就需要判断是否该定时任务需要重新放回优先队列中。 isRepeat 是通过判断任务中 interval 是否大于 0 判断,

如果大于0 则,表示永久就生效。

防止外部滥用,阻塞定时器协程,框架又一次封装了timer这个包,名为 timer_wapper 这个包,它提供了两种调用方式。

参数和上面的参数一样,只是在第三个参数中使用了任务池,将定时任务放入了任务池中。定时任务的本身执行就是一个 put 操作。

至于put以后,那就是 workers 这个包管理的了。在 worker 包中, 也就是维护了一个任务池,任务池中的任务会有序的执行,方便管理。

这选择显然是因人而异的。。至于怎么选,要看你是初学者,还是老手?。。对性能有要求,还是没要求?

如果是完全没有基础,我建议哪个都不选,如果非要选一个,那就选PYTHON。。如果你是初学者,把网上的教程看个遍,再买上几本书。。。你所学会的也仅仅是语法,而根本不会编程。。。因为这些教程,也仅仅是教你语法,而没有教你编程。。你甚至把网上的教程看个精光,却连个最基本的OA系统都做不出来。。。只能在一个黑乎乎的控制台上,打印一堆破字符。。

-------网上的所有教程都会教你的:

怎么定义一个变量?怎么在控制台打印变量?

怎么写一个循环?怎么在控制台打印一堆变量?

怎么写一个函数?怎么在控制台打印返回值?

怎么创建一个对象?怎么在控制台打印对象属性?

------高级一点的教程,会教你的:

怎么用PYTHON的模块,写一个爬虫?

怎么用RUBY的ROR框架,获取一个表单?

怎么用GO的beego,写一个博客?

-------而这些的教程,从来不教你的:

面向对象有什么用? 委托是什么?事件是什么? 工厂模式,单例模式,观察者模式,这些都是啥?套接字是啥?UDP是啥?TCP/IP是啥?二叉树是什么玩意?状态机又是什么玩意?啥叫逆变?啥叫协变?啥叫异步?啥叫反射?

---------------------------------------------------------------------------------------------

如果一套教程,要把这些都讲明白。。。可能需要上千集。。。所以这些教程,都跳过了这些内容。。但如果你不明白这些,就根本学不会编程。。。如果你打算学一门语言,而手上只有几十集教程,外加三五本书。。。那你只能学会玩控制台。。。

所以初学者选择一门语言,首先要保证这门语言作为主要开发语言,常年被公司使用,这样才能真正学会编程。然而这三门语言都不具备这样的特点。它们通常都是被当成第二语言,做一些辅助开发的工作。其中Python只在极少数情况下,才被用来作为主要开发语言。至于Go与Ruby,我目前还没听说过它们有被当作主要开发语言的例子。我所推荐的是从C#和JAVA两者之间,二选一。。。学精其中一门之后,再来考虑PYTHON或GO作为第二语言。。。不然无论你选哪个,都几乎不可能靠一门语言找到工作。