Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to realize the serialization and deserialization of binary tree in go language". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "go language how to achieve binary tree serialization and deserialization" it!

Deserialization of binary tree

Tree deserialization of the meaning of the name is to serialize a string or other forms of data to re-generate a binary tree, the following binary tree will serialize it into a string after the result [5last 4lnullreparent3], and now to do is to re-generate this string into a binary tree (generate the following tree, because this string is serialized through this tree).

Problem-solving ideas

First of all, you should first get a serialized data, which may be a queue, stack, string (with characters in the middle), or other form of data

When there is no data under a node, I use the empty space represented by null here. For example, if there is no data under node 2 above, it is represented by null in the string.

Here I convert the string to the form of a queue, of course, it is also possible to use the form of a string, for example, to split the string into an array by the split method

Create a queue, put the nodes to be processed and the master into the queue, for example, put the left and right branches into this queue during each cycle. Because the queue has the characteristics of FIFO, you can get the right node after processing the left branch.

Next, analyze the code.

TreeNode structure

The data in this is easy to understand. Val is the data of the current node; left and right save the data of the left and right branches, respectively.

Generate a corresponding TreeNode for each data

Func GenerateNode (str string) * TreeNode {if str = = "null" {return nil} return & TreeNode {val: str}}

This method is mainly used to generate TreeNode objects. As mentioned above, when there is no child node under the node, null will be used to indicate no, so if the formal parameter received here is null, it will return a null pointer. On the contrary, if it is not null, it will return a created TreeNode object and assign the val attribute to it.

Deserialization method func DeserializationTb (dataQueue [] string) (resultNode * TreeNode) {if len (dataQueue) = 0 {return nil} var tempNodeQueue [] * TreeNode resultNode = generateNode (dataQueue [len (dataQueue)-1]) dataQueue = dataQueue [: len (dataQueue)-1] if resultNode! = nil {tempNodeQueue = append (tempNodeQueue) ResultNode)} var tempNode * TreeNode for len (tempNodeQueue)! = 0 {tempNode = tempNodeQueue [0] tempNodeQueue = tempNodeQueue [1:] if len (dataQueue) > 0 {tempNode.left = generateNode [len (dataQueue)-1]) dataQueue = dataQueue [: len (dataQueue)-1] tempNode.right = generateNode (dataQueue [len (dataQueue)-1]) dataQueue = dataQueue [: len (dataQueue)-1]} if tempNode.left! = nil {tempNodeQueue = append (tempNodeQueue TempNode.left)} if tempNode.right! = nil {tempNodeQueue = append (tempNodeQueue,tempNode.right)}} return} Code interpretation

There is a lot of code for this method, so here's a block to say:

If len (dataQueue) = = 0 {return nil}

These lines of code are nothing more than a matter of judging boundary conditions. When the incoming queue has no data, it returns an empty one. Why the queue? Because I turned the string into a queue.

Var tempNodeQueue [] * TreeNoderesultNode = generateNode (dataQueue [len (dataQueue)-1]) dataQueue = dataQueue [: len (dataQueue)-1] if resultNode! = nil {tempNodeQueue = append (tempNodeQueue,resultNode)}

Var tempNodeQueue [] * TreeNode: the reason for creating a TreeNode pointer array is to store the data to be manipulated on the node. Because I transferred the serialized data into a queue, the last element in this array should be the first out array, and the first data is the root node of the binary tree. Save this node to the queue, and then the queue will be used in the following for loop. We'll talk about the rest later.

ResultNode = generateNode (dataQueue [len (dataQueue)-1]): here you will dequeue and generate a TreeNode object through generateNode

DataQueue = dataQueue [: len (dataQueue)-1]: because an array is out of queue, it needs to be removed

TempNodeQueue = append (tempNodeQueue,resultNode): after a null process, the node is saved to the queue mentioned above

For len (tempNodeQueue)! = 0 {tempNode = tempNodeQueue [0] tempNodeQueue = tempNodeQueue [1:] if len (dataQueue) > 0 {tempNode.left = generateNode (dataQueue [len (dataQueue)-1]) dataQueue = dataQueue [: len (dataQueue)-1] tempNode.right = generateNode (dataQueue [len (dataQueue)-1]) dataQueue = dataQueue [: len (dataQueue)-1]} if tempNode .left! = nil {tempNodeQueue = append (tempNodeQueue TempNode.left)} if tempNode.right! = nil {tempNodeQueue = append (tempNodeQueue,tempNode.right)}}

When entering the For loop, it also proves that there is data in the queue now. No matter three, seven or twenty-one, pop up the data in it first, because only with the data can you do the following operations (no data, no programming)

TempNodeQueue = tempNodeQueue [1:]: because the previous line of code pops up the data in this queue, one line of code removes the popped data

TempNode.left = generateNode (dataQueue [len (dataQueue)-1]): when serializing the existing data of the binary tree, the left and right branches of the binary tree are assigned, the next line of code is to remove the pop-up data, and the next two lines are the processing of the right node, just like left

TempNodeQueue = append (tempNodeQueue,tempNode.left): if the left node of the tempNode exists, save it to the queue, iterate through the tempNodeQueue queue, and perform the above steps again.

There may be some friends who have questions?

The returned resultNode variable is only assigned once, so how are the child nodes assigned? Because I deal with all TreeNode nodes through pointers.

And the data that pops up in the first line of code in For points to the address of resultNode, so after building the tree, I just have to grasp the root node of the tree.

Introduction to serialization of binary Tree

What about tree serialization? I can convert the tree to a data structure in a certain format, for example, converting it to a piece of text that can be persisted to the hard disk.

What's the use of that? For example, the data in Redis is in memory, and it has a function that can save the data to the hard disk at regular intervals to prevent sudden power outages from leading to data loss.

You can also understand the serialization of the tree here. I'm going to serialize the data in a binary tree to the hard disk so that the next time I use the data in this tree, I can generate the tree directly.

Problem-solving ideas

In order to solve this problem, the idea is to traverse the binary tree by layer. When a node has no child nodes, it is regarded as empty. I use null to express it here.

When serializing in this, I deal with the left child node first, and then deal with the right child node.

Like deserialization, I use the structure of temporary data in a queue, and I need to save the obtained data to a queue.

If the given header node is not empty at the beginning of the program, the header node is added to the queue

When traversing the queue, pop up the data in the queue (Note: the queue has the characteristics of FIFO), and put the val of this node into the queue where the data is stored.

Put the left and right child nodes of this node in the queue in turn, and perform the above steps at the second time

Code / * * serialize binary tree * / func SerializationTb (bt * TreeNode) (saveSerData [] string) {root: = bt var tempQueue [] * TreeNode if root! = nil {tempQueue = append (tempQueue) Root)} var tempNode * TreeNode for len (tempQueue)! = 0 {tempNode = tempQueue [0] if tempNode! = nil {saveSerData = append (saveSerData, tempNode.val)} else {saveSerData = append (saveSerData) "null")} tempQueue = tempQueue [1:] if tempNode! = nil {tempQueue = append (tempQueue, tempNode.left) tempQueue = append (tempQueue, tempNode.right)}} return} Code interpretation

These codes are easy to understand. Let's talk about the codes in for.

TempNode = tempQueue [0]: a data pops up in the queue

SaveSerData = append (saveSerData, tempNode.val): save the val attribute of tempNode to the saveSerData queue

The following if is to determine what to do with the data when the node is empty or not. It says that if there is no child node under a node, it is represented by null, so when there are no child nodes, null is added to the queue.

TempQueue = tempQueue [1:]: re-assign the queue to remove the data that pops up

TempQueue = append (tempQueue, tempNode.left): add the left node to the queue, and the next line is the same.

Running result

At this point, I believe that the "go language how to achieve binary tree serialization and deserialization" have a deeper understanding, might as well to practical operation it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.