golang 二叉树来实现递归排序
二叉树的定义介绍就不多说了,网上很多,这里想利用二叉树数据结构来实现排序,每个节点就是一个结构体,它同时又包含两个同类型指针,一个左枝,一个右枝,小的值存入左枝,相同或者大值存入右枝。
package main import ( "fmt" "math/rand" "sort" ) func main() { data := make([]int, 20) for i := range data { data[i] = rand.Int() % 20 } fmt.Println(data) Sort(data) if !sort.IntsAreSorted(data) { fmt.Println("无序的数据") } fmt.Println(data) } type tree struct { value int left, right *tree } func Sort(values []int) { var root *tree for _, v := range values { root = add(root, v) } appendValues(values[:0], root) } func appendValues(values []int, t *tree) []int { if t != nil { values = appendValues(values, t.left) values = append(values, t.value) values = appendValues(values, t.right) } return values } func add(t *tree, value int) *tree { if t == nil { t = new(tree) t.value = value return t } if value < t.value { t.left = add(t.left, value) } else { t.right = add(t.right, value) } return t }
输出:
E:\github.com\gopl.io\ch4\treesort>go run sort.go
[10 11 1 11 17 0 18 8 16 9 4 7 14 16 15 13 8 11 10 11]
[0 1 4 7 8 8 9 10 10 11 11 11 11 13 14 15 16 16 17 18]
[10 11 1 11 17 0 18 8 16 9 4 7 14 16 15 13 8 11 10 11]
[0 1 4 7 8 8 9 10 10 11 11 11 11 13 14 15 16 16 17 18]
Posted by 何敏 on 2020/2/25 02:15:20