Before reading benefits: hundreds of Internet technology books gave everyone mp.weixin.qq.com/s/dFqVQ2qJx…

[0]

preface

Come across a topic!! ~

Usually when we’re faced with a binary tree problem we’re faced with operations on the tree, and the problem is to serialize the whole tree, and then deserialize it, and return the binary tree as it was. Finally, return the tree’s head ~~~

【 1 】

The title

Serialization and deserialization of binary trees

Serialization: After a binary tree is generated, it is stored in a file in the format of text, that is, the serialization of the binary tree

Deserialization: The serialized binary tree is resolved to the original binary tree format according to the serialization rules, and the header is returned

The following figure corresponds to the serialization result of the preceding traversal 6! 88! 10! #! #! #! 92! 11! 22! #! #! 9! #! #! 12! #! #! :

【 2 】

The solution

1. Construct a tree node class

Let’s take Python as an example

class TreeNode:
    def __init__(self, value) :
        self.val = value		# store node values
        self.left = None		# refers to the left subtree
        self.right = None		# point to the right subtree
Copy the code

Then manually construct the binary tree

if __name__ == "__main__":
    Create a new node
    node_A = TreeNode("6")
    node_B = TreeNode("88")
    node_C = TreeNode("92")
    node_D = TreeNode("10")
    node_E = TreeNode("11")
    node_F = TreeNode("12")
    node_G = TreeNode("22")
    node_H = TreeNode("9")

    # build a binary tree
    # 6
    # / \
    # 88, 92,
    # / / \
    11 12 # 10
    # / \
    9 # 22
Copy the code

2. Binary tree serialization

First, serialize the binary tree by iterating one value at a time, followed by! (exclamation mark), empty nodes are represented by #(hash mark)

! (exclamation mark) indicates the end of the object, for example, if no! #(exclamation mark) is used to indicate that the node is null. For logical consistency, empty nodes are also used with #! Said. You could have just used the # notation

Second, we serialize using a binary tree preorder traversal

Combining the above two aspects, we can get that the serialized content should be

Sequential serialization: 6! 88! 10! #! #! #! 92! 11! 22! #! #! 9! #! #! 12! #! #!Copy the code

Here’s the code:

def serialize_by_pre_order_traverse(self, root) :
  if root is None:
    self.serialize_string += "#!"
    return None
  self.serialize_string += root.val+"!"
  self.serialize_by_pre_order_traverse(root.left)
  self.serialize_by_pre_order_traverse(root.right)
Copy the code

When traversing recursively, each time a node value is traversed, add “!” to the node value. (exclamation mark), automatically fill in “#” (hash sign) and add “!” each time a null node is traversed. (exclamation mark)

3. Deserialization of binary trees

Deserialization focuses on constructing binary trees. If you have the idea of constructing binary trees, deserialization is easy to implement

First, since each node is serialized with “!” (exclamation mark), so serialized results need to be separated by “!” Split, store as an array

The following code splits the serialized string into an array items_tree_node

Implement deserialization first
def deserialize_by_pre_order_traverse(self, serialize_string) :
    items_tree_node = []
    items = serialize_string.split("!") [0: -1]
    Place the values of each node into the list
    for item in items:
        items_tree_node.append(item)
    # print(items_tree_node)
    # construct binary tree
    return self.create_tree(items_tree_node)
Copy the code

Second, the array is traversed in the way of the preceding order to construct a binary tree

def create_tree(self, item_tree_node) :
    if len(item_tree_node) <= 0:
        return None
    item = item_tree_node.pop(0)
    root = None
    ifitem ! =The '#':
        root = TreeNode(item)
        root.left = self.create_tree(item_tree_node)
        root.right = self.create_tree(item_tree_node)
    return root
Copy the code

code

At this point, all the ideas have been outlined

According to the idea of preorder traversal, serialization and deserialization are constructed

Serialization: Traverses each node in the preceding order, using “!” (exclamation mark) split, null node with “#” (hash sign)

Deserialization: To serialize the result as “!” (exclamation mark) split storage into arrays, and then construct a binary tree based on the preceding traversal

Finally, after tidying up all the above code:

# -*- coding:utf-8 -*-
# !/usr/bin/env python

# tree node class
class TreeNode:
    def __init__(self, value) :
        self.val = value
        self.left = None
        self.right = None


class TreeSerializeAndDeserialize(object) :

    def __init__(self) :
        # binary tree serialized string result
        self.serialize_string = ""
        Binary tree deserializes string results
        self.deserialize_head = None

    def print_tree_pre_order_traverse(self, head) :
        if head is None:
            return None
        print(head.val, end="")
        self.print_tree_pre_order_traverse(head.left)
        self.print_tree_pre_order_traverse(head.right)

    def create_tree(self, item_tree_node) :
        if len(item_tree_node) <= 0:
            return None
        item = item_tree_node.pop(0)
        root = None
        ifitem ! =The '#':
            root = TreeNode(item)
            root.left = self.create_tree(item_tree_node)
            root.right = self.create_tree(item_tree_node)
        return root

    Serialization is implemented first
    def serialize_by_pre_order_traverse(self, root) :
        Serialize binary tree (serialize binary tree, serialize binary tree, serialize binary tree) (exclamation mark), empty nodes are represented by #(hash mark)
        #! (exclamation mark) indicates the end of the object, for example, if no! (exclamation mark), 88 means 8 or 88, which is ambiguous
        # # is used to indicate that a node is null. For logical consistency, empty nodes are also used with #! Said. You could have just used the # notation
        Binary tree structure:
        # 6
        # / \
        # 88, 92,
        # / / \
        11 12 # 10
        # / \
        9 # 22
        Sequential serialization: 6! 88! 10! #! #! #! 92! 11! 22! #! #! 9! #! #! 12! #! #!
        if root is None:
            self.serialize_string += "#!"
            return None
        self.serialize_string += root.val+"!"
        self.serialize_by_pre_order_traverse(root.left)
        self.serialize_by_pre_order_traverse(root.right)

    Implement deserialization first
    def deserialize_by_pre_order_traverse(self, serialize_string) :
        items_tree_node = []
        items = serialize_string.split("!") [0: -1]
        Place the values of each node into the list
        for item in items:
            items_tree_node.append(item)
        # print(items_tree_node)
        # construct binary tree
        return self.create_tree(items_tree_node)


if __name__ == "__main__":
    Create a new node
    node_A = TreeNode("6")
    node_B = TreeNode("88")
    node_C = TreeNode("92")
    node_D = TreeNode("10")
    node_E = TreeNode("11")
    node_F = TreeNode("12")
    node_G = TreeNode("22")
    node_H = TreeNode("9")

    # build a binary tree
    # 6
    # / \
    # 88, 92,
    # / / \
    11 12 # 10
    # / \
    9 # 22

    node_A.left, node_A.right = node_B, node_C
    node_B.left = node_D
    node_C.left, node_C.right = node_E, node_F
    node_E.left, node_E.right = node_G, node_H

    serialize_res = ""
    # instantiate the class
    TS = TreeSerializeAndDeserialize()
    print("\n Sequential traversal tree structure:")
    TS.print_tree_pre_order_traverse(node_A)

    Serialization using preemptive traversal
    TS.serialize_by_pre_order_traverse(node_A)
    print("\n Serialization by sequential traversal: \n", TS.serialize_string)

    Deserialize using preemptive traversal
    print("Deserialize by sequential traversal:")
    TS.deserialize_head = TS.deserialize_by_pre_order_traverse(TS.serialize_string)
    TS.print_tree_pre_order_traverse(TS.deserialize_head)
Copy the code

Results after execution:

Sequential traversal tree structure: 6 88 10 92 11 22 9 12 Serialized by sequential traversal: 6! 88! 10! #! #! #! 92! 11! 22! #! #! 9! #! #! 12! #! #! Deserialize by sequential traversal: 6 88 10 92 11 22 9 12Copy the code

The last

Here to prepare hundreds of Internet technology books, you need to download it! Click to get any questions, please feel free to communicate!!