首页 二叉树序列化与反序列化
文章
取消

二叉树序列化与反序列化

发表于 2021/12/03
作者
8 分钟阅读

谈到序列化与反序列化，我们可能想到 json、xml 等，序列化就是在编程语言中将数据对象转换为通用的数据，可以放在不同的介质中，如磁盘、网络，另一个进程（可能同编程语言，也可能其他编程语言）可以还原出原本的数据出来，这个还原的过程就是反序列化。

序列化与反序列化的实现，重要的是规则，要能按照规则描述出数据对象，也能还原出数据对象。

二叉树是一种结构非常清晰的数据结构，对于如下的一个二叉树：

D8ZR1J.png

如果想要准确地描述出来， 需要按照固定的顺序指出每个节点的值，以及左右子节点，那么对于上图的二叉树，我们可以前序遍历它，对于空节点用 # 表示，那么就得到了这样的一个序列：

1

[41,15,13,#,#,22,#,37,33,#,#,#,58,#,60,#,#]

再还原回来呢？照着规则逆回来就好了，首元素 41 是根节点，下一个 15 肯定是 41 的左子节点，再下一个 13 是 15 的左子节点，接下来的两个 # 说明 13 是叶子节点，那么再接下来的 22 就是 15 的右子节点了……

既然思路理清楚了，那么序列化和反序列化就很简单了。

类似地，后序遍历也可行，可以确定 root 节点，在最右侧，可以实现；层序遍历也能确定 root 节点和左右子节点，可以实现；但是中序遍历就不行了，能序列化但不能反序列化，root 节点夹在中间，无法确定位置。

前序遍历

序列化为字符串，元素之间用逗号分隔，空元素用#表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

func serialize(root *BTNode, builder *strings.Builder) string {
	if root == nil {
        // 空节点，用 # 表示，并用逗号分隔
		if builder.Len() == 0 {
			builder.WriteString("#")
		} else {
			builder.WriteString(",#")
		}
	} else {
        // 非空节点，用逗号分隔
		builder.WriteString(fmt.Sprintf(",%d", root.Data))
		serialize(root.Left, builder)
		serialize(root.Right, builder)
	}
	return builder.String()
}

反序列化之前先定义一个队列，用来取出首元素并移除：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

type Queue struct {
	data []interface{}
	size int
}

func NewQueue(data ...interface{}) *Queue {
	size := len(data)
	return &Queue{data: data, size: size}
}

func (q *Queue) Size() int {
	return q.size
}

func (q *Queue) Push(val interface{}) {
	q.data = append(q.data, val)
	q.size++
}

func (q *Queue) Pop() interface{} {
	if q.size == 0 {
		return nil
	}
	r := q.data[0]
	q.data = q.data[1 : q.size]
	q.size--
	return r
}

反序列化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

func deserialize(text string) (*BTNode, error) {
	var eles []interface{}
	for _, s := range strings.Split(text, ",") {
		eles = append(eles, s)
	}

	return genNodes(NewQueue(eles...))
}

func genNodes(q *Queue) (*BTNode, error) {
	if q.Size() == 0 {
		return nil, nil
	}
	// 删掉首个数据
	rootData := q.Pop().(string)

	if rootData == "#" {
		return nil, nil
	}
	rootVal, err := strconv.ParseInt(rootData, 10, 64)
	if err != nil {
		return nil, err
	}

    // 生成左子树
	root := &BTNode{Data: int(rootVal)}
	left, err := genNodes(q)
	if err != nil {
		return nil, err
	}

    // 生成右子树
	right, err := genNodes(q)
	if err != nil {
		return nil, err
	}

	root.Left = left
	root.Right = right

	return root, nil
}

后序遍历

后序遍历，其实和前序遍历类似，只是反序列化的突破点不是首元素，而是末元素，末元素是根节点。

序列化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func serialize(root *BTNode, builder *strings.Builder) string {
	if root == nil {
		if builder.Len() == 0 {
			builder.WriteString("#")
		} else {
			builder.WriteString(",#")
		}
	} else {
		serialize(root.Left, builder)
		serialize(root.Right, builder)
		builder.WriteString(fmt.Sprintf(",%d", root.Data))
	}
	return builder.String()
}

反序列化，需要用到栈这种数据结构，先定一个一个栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

type Stack struct {
	data []interface{}
	size int
}

func NewStack(data ...interface{}) *Stack {
	size := len(data)
	return &Stack{data: data, size: size}
}

func (q *Stack) Size() int {
	return q.size
}

func (q *Stack) Push(val interface{}) {
	q.data = append(q.data, val)
	q.size++
}

func (q *Stack) Pop() interface{} {
	if q.size == 0 {
		return nil
	}
	r := q.data[q.size-1]
	q.data = q.data[:q.size-1]
	q.size--
	return r
}

反序列化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

func deserialize(text string) (*BTNode, error) {
	var eles []interface{}
	for _, s := range strings.Split(text, ",") {
		eles = append(eles, s)
	}

	return genNodes(NewStack(eles...))
}

func genNodes(q *Stack) (*BTNode, error) {
	if q.Size() == 0 {
		return nil, nil
	}
	// 删掉末尾数据
	rootData := q.Pop().(string)

	if rootData == "#" {
		return nil, nil
	}
	rootVal, err := strconv.ParseInt(rootData, 10, 64)
	if err != nil {
		return nil, err
	}

	root := &BTNode{Data: int(rootVal)}
	// 右子节点
	right, err := genNodes(q)
	if err != nil {
		return nil, err
	}

	// 左子节点
	left, err := genNodes(q)
	if err != nil {
		return nil, err
	}

	root.Left = left
	root.Right = right

	return root, nil
}

层序遍历

序列化，其实就是一个层序遍历的过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func serialize(root *BTNode, builder *strings.Builder) string {
	q := NewQueue(root)
	for q.Size() != 0 {
		node := q.Pop().(*BTNode)
		if node == nil {
			// 空节点
			if builder.Len() == 0 {
				builder.WriteString("#")
			} else {
				builder.WriteString(",#")
			}
		} else {
			// 不为空
			if builder.Len() == 0 {
				builder.WriteString(fmt.Sprintf("%d", node.Data))
			} else {
				builder.WriteString(fmt.Sprintf(",%d", node.Data))
			}
			q.Push(node.Left)
			q.Push(node.Right)
		}
	}
	return builder.String()
}

反序列化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

func deserialize(text string) (*BTNode, error) {
	if len(text) == 0 {
		return nil, nil
	}

	eles := strings.Split(text, ",")
	if eles[0] == "#" {
		return nil, nil
	}
	rootVal, err := strconv.ParseInt(eles[0], 10, 64)
	if err != nil {
		return nil, err
	}
	root := &BTNode{Data: int(rootVal)}
	q := NewQueue(root)
	for i := 1; i < len(eles); {
		parentNode := q.Pop().(*BTNode)

        // 下一个就是左子节点
		leftEle := eles[i]
		i++
		if leftEle == "#" {
			parentNode.Left = nil
		} else {
			leftVal, err := strconv.ParseInt(leftEle, 10, 64)
			if err != nil {
				return nil, err
			}
			leftNode := &BTNode{Data: int(leftVal)}
			parentNode.Left = leftNode
			q.Push(leftNode)
		}

        // 再下一个是右子节点
		rightEle := eles[i]
		i++
		if rightEle == "#" {
			parentNode.Right = nil
		} else {
			rightVal, err := strconv.ParseInt(rightEle, 10, 64)
			if err != nil {
				return nil, err
			}
			rightNode := &BTNode{Data: int(rightVal)}
			parentNode.Right = rightNode
			q.Push(rightNode)
		}
	}

	return root, nil
}
技术
go 算法 二叉树 前序遍历 后序遍历 层序遍历
本文由作者按照 CC BY 4.0 进行授权