Golang 二叉树插入排序

/* 我们将切片中的元素插入到二叉树中，通过二叉树的遍历排序 */

type tree struct {
	values int
	left, right *tree
}

func SortTree(values []int) {
	var root *tree
	for _, v := range values {
		root = Insert(root, v)
	}
	addValues(values[:0], root)
}

func Insert(t *tree, val int) *tree {

	if t == nil {
		t = new(tree)
		t.values = val
		return t
	}
	if val < t.values {
		t.left = Insert(t.left,val)
	} else {
		t.right = Insert(t.right,val)
	}
	return t
}

func addValues(values []int, t *tree) []int {
	if t!= nil {
		values = addValues(values, t.left)
		values = append(values, t.values)
		values = addValues(values, t.right)
	}
	return values
}

example

package main

import (
	"fmt"
)

func main() {
	var a  []int = []int{1,2,4,4,5,10,7,6,9,8}
	SortTree(a)
	fmt.Println(a)
	// [1 2 4 4 5 6 7 8 9 10]
}