树的序列化和反序列化

tree_serialize.go

package main

import (
	"fmt"
	"strconv"
	"strings"
)

type Node struct {
	Value    int
	Children []*Node
}

func toInts(ss []string) ([]int, error) {
	var vv []int
	for _, s := range ss {
		v, err := strconv.ParseInt(s, 10, 32)
		if err != nil {
			return nil, err
		}
		vv = append(vv, int(v))
	}
	return vv, nil
}

// 序列化成 值:子节点个数
// 借助队列层序遍历
// 1:3,12:2,13:1,14:0,22:1,23:1,45:0,33:0,44:0
func s(root *Node) string {
	if root == nil {
		return ""
	}
	a := []*Node{root}
	var res []string
	for len(a) > 0 {
		cur := a[0]
		a = a[1:]
		if cur == nil {
			continue
		}
		c := len(cur.Children)
		res = append(res, fmt.Sprintf("%d:%d", cur.Value, c))
		a = append(a, cur.Children...)
	}
	return strings.Join(res, ",")
}

// 反序列化时，逐个来，把自己解析出来后，要把自己的子的个数加到队列尾部
func d(s string) *Node {
	if len(s) == 0 {
		return nil
	}
	ss := strings.Split(s, ",")
	rr, _ := toInts(strings.Split(ss[0], ":"))
	ss = ss[1:]
	root := &Node{
		Value:    rr[0],
		Children: make([]*Node, rr[1]),
	}
	a := []*Node{root}
	for len(a) > 0 && len(ss) > 0 {
		cur := a[0]
		a = a[1:]
		for i := 0; i < len(cur.Children); i++ {
			rr, _ := toInts(strings.Split(ss[i], ":"))
			cur.Children[i] = &Node{
				Value:    rr[0],
				Children: make([]*Node, rr[1]),
			}
		}
		ss = ss[len(cur.Children):]
		a = append(a, cur.Children...)
	}
	return root
}

// 1
// 12         13    14
// 22    23   45
// 33    44
func main() {
	tree := &Node{
		Value: 1,
		Children: []*Node{
			{
				Value: 12,
				Children: []*Node{
					{
						Value: 22,
						Children: []*Node{
							{
								Value: 33,
							},
						},
					},
					{
						Value: 23,
						Children: []*Node{
							{
								Value: 44,
							},
						},
					},
				},
			},
			{
				Value: 13,
				Children: []*Node{
					{
						Value: 45,
					},
				},
			},
			{
				Value: 14,
			},
		},
	}
	fmt.Println(s(tree))
	root := d(s(tree))
	fmt.Println(root)
}