[007- Week2] 构建一个常用的二叉树类库 golang

[v1xingyue]

二叉树最近操作比较多，发现操作相对比较繁琐，尤其是刷leetcode的时候，线上测试有完整的环境和测试用例。本地测试就会相对麻烦。
所以，抽象出了一个简单的操作函数库，后期会继续扩充。

二叉树基本操作

分为几个功能：

• 支持不同的类型:
  所以节点的val 类型选择了 interface{} 空接口类型。
  但是,这个类型在应用中有个坑。

  当你把一个，特定类型的nil 指针 赋值给一个节点的val 时，他并不为nil 。
  具体情况,可以抽象为如下的代码:

	var l interface{}
	var n *int
	n = nil
	l = n
	t.Log(l == nil)    为false 

情况解析: interface{} 内部包含了两个指针pt,pv , pt 指向类型， pv 指向对应的值。所以，才保证了这种类型的数据可以放任何类型的对象。
  l = n 做的操作是, 将l 的 pt 指向 *int , l的pv 指向nil , 所以 l 自身依然不为nil

• 节点插入数据:
  考虑构建树的时候，结构清晰，所以，插入一个节点以后，一般会在后边继续插入。比较符合人类的操作习惯。 所以 , 添加节点的操作，最好把新加入的节点返回给调用方，供后续，操作.
  拿一个插入左右两个数据为例，则应该返回 l,r 两个对应的指针。
  这点在golang 中可以返回多个值， 且返回类型为指针类型，不会占用太多的空间.
  简单实现如下:

func (self *node) addBoth(l, r vtype) (*node, *node) {
	self.left = Node(l)
	self.right = Node(r)
	return self.left, self.right
}

• 遍历操作的时候，传递对应的函数回调：
  leetcode 里边一般只对结果进行输出返回，结构较为简单。
  考虑到实际操作中，会对元素做多种多样的操作。将操作和遍历本身分开。
  也是一种类似函数编程的思想。

  函数回调可以定义对应的函数指针类型: 注意使用 通用的类型 interface {}
  下边是一个后续遍历的例子

//后续遍历

type LoopHandler func(x vtype)

func PostLoopTree(tree *node, fn LoopHandler) {
	if tree == nil {
		return
	}
	PostLoopTree(tree.left, fn)
	PostLoopTree(tree.right, fn)
	if fn != nil {
		fn(tree.data)
	}
}

[v1xingyue]

基于以上的类库，可以有一种很酷的写法 :

l := Node(32)
l.addRight(2).addLeft(15).addLeft(16).addLeft(34).addRight(50)