treesort.go

package main

import (
	"fmt"
	"math/rand"
)

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

func (t *tree) String() string {
	var str string
	var visit func(t *tree)

	visit = func(t *tree) {
		if t.left != nil {
			visit(t.left)
		}
		str = fmt.Sprintf("%s %d", str, t.value)
		if t.right != nil {
			visit(t.right)
		}
	}
	visit(t)
	return str
}

func main() {
	s := make([]int, 50)
	for i := range s {
		s[i] = rand.Int() % 50
	}

	fmt.Println(s)
	Sort(s)
	fmt.Println(s)

	var root *tree
	for _, v := range s {
		root = add(root, v)
	}
	fmt.Println(root)
}

func Sort(nums []int) {
	var root *tree

	for _, v := range nums {
		root = add(root, v)
	}
	appendValue(nums[:0], root)
}

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

}

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