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]
Posted by 何敏 on 2020-02-25 02:15:20