Golang-遍历二叉树实现

2019-03-04

二叉树的几种遍历方式

1)先序遍历

1)访问根节点;2)采用先序递归遍历左子树;3)采用先序递归遍历右子树;

image.png (注:每个节点的分支都遵循上述的访问顺序,体现“递归调用”)

2)中序遍历

1)采用中序遍历左子树;2)访问根节点;3)采用中序遍历右子树; image.png

3)后序遍历

1)采用后序递归遍历左子树;2)采用后序递归遍历右子树;3)访问根节点;

image.png

三种方法遍历过程中经过节点的路线一样,只是访问各个节点的时机不同。 递归算法主要使用堆栈来实现,本文使用Golang实现,就当是Golang学习的练手题了。

使用Golang实现

定义结构体

type Node struct {
	Value int
	Left, Right *Node
}

建树

新建一个node_test.go文件,用于单元测试:

// 按照图示,创建相关的二叉树
func CreateNode() *Node {
	root := &Node{'A', nil, nil}
	root.Left = &Node{Value: 'B'}
	root.Right = &Node{Value: 'C'}
	root.Left.Left = &Node{Value: 'D'}
	root.Left.Right = &Node{Value: 'F'}
	root.Left.Right.Left = new(Node)
	root.Left.Right.Left.Value = 'E'

	root.Right.Left = &Node{Value: 'G'}
	root.Right.Left.Right = &Node{Value: 'H'}
	root.Right.Right = &Node{Value: 'I'}
	return root
}

###

几种遍历方法的实现

继续在结构体中定义方法,先实现效果

// 先序遍历
func (node *Node) TraversingWithPreface()  {
	if node != nil {
		node.PrintValue() // 先打印值,后续优化
		node.Left.TraversingWithPreface()
		node.Right.TraversingWithPreface()
	}
}

// 中序遍历
func (node *Node) TraversingWithMediumOrder()  {
	if node != nil {
		node.Left.TraversingWithMediumOrder()
		node.PrintValue() // 先打印值,后续优化
		node.Right.TraversingWithMediumOrder()
	}
}

// 后序遍历
func (node *Node) TraversingWithPostOrder()  {
	if node != nil {
		node.Left.TraversingWithPostOrder()
		node.Right.TraversingWithPostOrder()
		node.PrintValue() // 先打印值,后续优化
	}
}

编写单元测试

func TestTraversing(t *testing.T) {
	node := CreateNode()

	fmt.Println("TraversingWithPreface::")
	node.TraversingWithPreface()
	fmt.Println()

	fmt.Println("TraversingWithMediumOrder::")
	node.TraversingWithMediumOrder()
	fmt.Println()


	fmt.Println("TraversingWithPostOrder::")
	node.TraversingWithPostOrder()
	fmt.Println()
}

=== RUN   TestTraversing
TraversingWithPreface::
(A) (B) (D) (F) (E) (C) (G) (H) (I) 
TraversingWithMediumOrder::
(D) (B) (E) (F) (A) (G) (H) (C) (I) 
TraversingWithPostOrder::
(D) (E) (F) (B) (H) (G) (I) (C) (A) 
--- PASS: TestTraversing (0.00s)
PASS

通过实现看到,遍历二叉树相当简单,只是打印的时机不同而已,上述的实现方法非常不妥,只能打印,遍历出来没法使用咋个办?继续优化吧

使用channel + func继续优化

上述的几种遍历方式,留下比较常用的中序遍历即可   然后我们希望在递归调用的过程中,将遍历到的值通过channel发送给外面使用,直接看代码吧!

// 在Golang的世界中,func和channel均为一等公民,均可以作为返回值、参数等
// 利用该特性,在此我们分别通过两种方式实现了将遍历到的值传递到调用方处理
package tree

import "fmt"

type Node struct {
	Value int
	Left, Right *Node
}

func (node *Node) PrintValue() {
	fmt.Printf("(%c)", node.Value)
}

func (node *Node) TraversingWithFunc(applyFunc func(*Node))  {
	if node != nil {
		node.Left.TraversingWithFunc(applyFunc)
		applyFunc(node)
		node.Right.TraversingWithFunc(applyFunc)
	}
}

func (node *Node) TraversingWithChannel() chan *Node {
	channel := make(chan *Node)
	go func() {
		node.TraversingWithFunc(func(node *Node) {
			channel <- node
		})
		close(channel)
	}()
	return channel
}

通过单元测试,来打印二叉树的以及统计总节点数:

func TestTraversing(t *testing.T) {
	node := CreateNode()

	sumNodeCount := 0
	beginTime := time.Now()
	node.TraversingWithFunc(func(node *Node) {
		node.PrintValue()
		sumNodeCount ++
	})
	fmt.Printf("\nnode.TraversingWithFunc sumNodeCount = %d, timeConsuming=%d\n\n", sumNodeCount, time.Now().Sub(beginTime))

	sumNodeCount = 0
	beginTime = time.Now()
	channel := node.TraversingWithChannel()
	for node := range channel {
		node.PrintValue()
		sumNodeCount ++
	}
	fmt.Printf("\nnode.TraversingWithChannel sumNodeCount = %d, timeConsuming=%d\n", sumNodeCount, time.Now().Sub(beginTime))
}

打印日志如下:

=== RUN   TestTraversing
(D) (B) (E) (F) (A) (G) (H) (C) (I) 
node.TraversingWithFunc sumNodeCount = 9, timeConsuming=50194

(D) (B) (E) (F) (A) (G) (H) (C) (I) 
node.TraversingWithChannel sumNodeCount = 9, timeConsuming=49098
--- PASS: TestTraversing (0.00s)
PASS

可以看到,由于TraversingWithChannel()使用了goroutine+channel实现并发模型,目前看来效率远高于前者。

将相关的耗时统计代码去掉,进行进一步的性能测试:

func BenchmarkNode_TraversingWithFunc(b *testing.B) {
	node := CreateNode()
	for i := 0 ; i < b.N; i ++ {
		node.TraversingWithFunc(func(node *Node) {
			node.PrintValue()
		})
		fmt.Println()
	}
}

func BenchmarkNode_TraversingWithChannel(b *testing.B) {
	node := CreateNode()
	for i := 0 ; i < b.N; i ++ {
		channel := node.TraversingWithChannel()
		for node := range channel {
			node.PrintValue()
		}
		fmt.Println()
	}
}

image.png

image.png

从图中可以看到,分别对TraversingWithFunc() / TraversingWithChannel()做了 3w / 5w次的性能测试,仍然是后者领先。

使用pprof进行性能调优

以上的代码是否能分析出一些性能瓶颈,具体耗时是什么操作产生的呢?答案是肯定的,使出Golang的大杀器pprof吧!

  • runtime/pprof:采集程序(非 Server)的运行数据进行分析
  • net/http/pprof:采集 HTTP Server 的运行时数据进行分析

由于代码不在http server中,所以有关net/http/pprof的使用,以后再演示吧

生成cpuprofile文件

cd 到单元测试文件目录

go test -bench . -cpuprofile cpu.out

image.png

执行性能测试完成后,会在当前文件夹生成两个文件

image.png

这里主要关注cpu.out文件,该文件是一个二进制文件,可以使用golang内置的工具打开。

使用go tool pporf 查看cpuprofile文件

go tool pprof cpu.out

执行该命令后,会再次进入一个交互式控制台,输入相关指令,就能对cpuprofile文件做一些操作, 比如:输入web,直接打开可视化界面,分析调用链

image.png

第一次可能出现以上问题,按照提示,安装相关软件即可:brew install Graphviz

image.png

分析调用链,颜色较深的部分为耗时占比较多的部分, 通过分析,不难看出,主要耗时出现在了func (node *Node) PrintValue()函数中。

image.png

这也比较好理解了,频繁的打印必然消耗IO嘛,找到问题了后续就慢慢优化吧!