package main
import(
        "fmt"
        "bytes"
)

func main(){
        //定义数组
        arr:=[...]int{6,2,1,3,4,5}
        var t *tree
        for i:=0;i<len(arr);i++{
                t=add(t,arr[i])
        }   
        //t1:=Sort(arr[:],t)
        //fmt.Println(arr)
        fmt.Println(t)
}

/*
练习 7.3： 为在gopl.io/ch4/treesort (§4.4)的*tree类型实现一个String方法去展示tree类型的值序列。
*/

func (t *tree)String()string{
        var buf bytes.Buffer
        var data []int
        data=appendValues(data,t)
        buf.WriteByte('{')
        for _,v:=range data{
                if buf.Len() > len("{"){
                        buf.WriteByte(' ')
                }   
                //重点:使用了接口约定
                fmt.Fprintf(&buf,"%d",v)
        }   
        buf.WriteByte('}')
        return buf.String()
}

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

// Sort sorts values in place.
func Sort(values []int,root *tree) *tree {
    //var root *tree
    for _, v := range values {
        root = add(root, v)
    }   

    fmt.Println(root)
    appendValues(values[:0], root)
    return root
}

// appendValues appends the elements of t to values in order
// and returns the resulting slice.
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 {
        // Equivalent to return &tree{value: value}.
        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
}