Open v1xingyue opened 5 years ago
二叉树最近操作比较多,发现操作相对比较繁琐,尤其是刷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) } }
基于以上的类库,可以有一种很酷的写法 :
l := Node(32) l.addRight(2).addLeft(15).addLeft(16).addLeft(34).addRight(50)
二叉树最近操作比较多,发现操作相对比较繁琐,尤其是刷leetcode的时候,线上测试有完整的环境和测试用例。本地测试就会相对麻烦。 所以,抽象出了一个简单的操作函数库,后期会继续扩充。
二叉树基本操作
分为几个功能:
支持不同的类型: 所以节点的val 类型选择了 interface{} 空接口类型。 但是,这个类型在应用中有个坑。
当你把一个,特定类型的nil 指针 赋值给一个节点的val 时,他并不为nil 。 具体情况,可以抽象为如下的代码:
情况解析: interface{} 内部包含了两个指针pt,pv , pt 指向类型, pv 指向对应的值。所以,才保证了这种类型的数据可以放任何类型的对象。 l = n 做的操作是, 将l 的 pt 指向 *int , l的pv 指向nil , 所以 l 自身依然不为nil
节点插入数据: 考虑构建树的时候,结构清晰,所以,插入一个节点以后,一般会在后边继续插入。比较符合人类的操作习惯。 所以 , 添加节点的操作,最好把新加入的节点返回给调用方,供后续,操作. 拿一个插入左右两个数据为例,则应该返回 l,r 两个对应的指针。 这点在golang 中可以返回多个值, 且返回类型为指针类型,不会占用太多的空间. 简单实现如下:
遍历操作的时候,传递对应的函数回调: leetcode 里边一般只对结果进行输出返回,结构较为简单。 考虑到实际操作中,会对元素做多种多样的操作。将操作和遍历本身分开。 也是一种类似函数编程的思想。
函数回调可以定义对应的函数指针类型: 注意使用 通用的类型 interface {} 下边是一个后续遍历的例子