Shulou(Shulou.com)06/01 Report--

This article will explain in detail how to understand the serialized binary tree in python. The content of the article is of high quality, so the editor shares it for you as a reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

Title

Implement two functions to serialize and deserialize the binary tree, respectively.

Analysis.

We know that we can create a binary tree by preorder traversal sequence and intermediate order traversal sequence. Therefore, we can first serialize a binary tree into a preorder ergodic sequence and a mid-order ergodic sequence, and then restore the binary tree through these two sequences during deserialization.

However, this approach has two disadvantages:

This method requires that there should be no nodes with duplicate values in the binary tree.

Serialization can only begin when all the data in the two sequences is read. If the data of two traversal sequences is read from one stream, it may take a long time to wait.

In fact, if the serialization of the binary tree starts at the root node, then the corresponding deserialization can begin when the value of the root node is read. Therefore, we can serialize the binary tree according to the order of the preorder traversal, because the preorder traversal starts at the root node. When null pointers are encountered when traversing the binary tree, these null pointers are serialized into a special character (such as $). In addition, the values of nodes should be separated by a special character (such as,).

The deserialized binary tree is also traversed according to the pre-order.

Code import com.lun.util.BinaryTree.TreeNode;public class SerializeBinaryTree {public void serialize (TreeNode node, StringBuilder result) {if (node = = null) {result.append ("$,"); return;} result.append (node.val + ",") Serialize (node.left, result); serialize (node.right, result);} public TreeNode deserialize (StringBuilder sb) {Integer number = readNum (sb); TreeNode node = null; if (number! = null) {node = new TreeNode (number) Node.left = deserialize (sb); node.right = deserialize (sb);} return node;} public Integer readNum (StringBuilder sb) {int firstCommaIndex = sb.indexOf (","); String numStr = sb.substring (0, firstCommaIndex) Integer result = null; if (! numStr.equals ("$")) {result = Integer.valueOf (numStr);} try {sb.delete (0, firstCommaIndex + 1) } catch (Exception e) {/ / do nothing} return result;}} Test import static org.junit.Assert.*;import org.junit.Test;import com.lun.util.BinaryTree;import com.lun.util.BinaryTree.TreeNode Public class SerializeBinaryTreeTest {@ Test public void testSerialize () {SerializeBinaryTree sbt = new SerializeBinaryTree (); StringBuilder result = new StringBuilder (""); TreeNode root = makeATree (); sbt.serialize (root, result); assertEquals } @ Test public void testReadNum () {SerializeBinaryTree sbt = new SerializeBinaryTree (); StringBuilder sb = new StringBuilder ("1 sbt.readNum (sb). IntValue ()) AssertEquals ("2, sbt.readNum (sb). IntValue ()); assertEquals (" 4, 4, sb, 5, and 6), ", sb.toString () AssertEquals (4, sbt.readNum (sb). IntValue ()); assertEquals ("$, 3pyrr5),", sb.toString (); assertNull (sbt.readNum (sb)); assertEquals ("$, $, 3pyrr5,", sb.toString ()). AssertNull (sbt.readNum (sb)); assertEquals ("$, 3pjcc),", sb.toString ()); assertNull (sbt.readNum (sb)); assertEquals ("3pje, 5pas),", sb.toString ()) AssertEquals (3, sbt.readNum (sb). IntValue ()); assertEquals ("5, sbt.readNum (sb). IntValue ()); assertEquals (" $, $, 6, sb.toString ()) AssertNull (sbt.readNum (sb)); assertEquals ("$, 6 sbt.readNum (sb). IntValue ()); assertNull (sbt.readNum (sb)); assertEquals (" 6 sbt.readNum (sb). IntValue ()). AssertEquals ("$, $,", sb.toString ()); assertNull (sbt.readNum (sb)); assertEquals ("$,", sb.toString ()); assertNull (sbt.readNum (sb)); assertEquals (", sb.toString ()) } @ Test public void testDeserialize () {SerializeBinaryTree sbt = new SerializeBinaryTree (); TreeNode root = null; TreeNode root2 = makeATree (); StringBuilder sb = new StringBuilder ("); sbt.serialize (root2, sb) Root = sbt.deserialize (sb); assertTrue (BinaryTree.equals (root, root2));} private TreeNode makeATree () {TreeNode root = new TreeNode (1); root.left = new TreeNode (2) Root.right = new TreeNode (3); root.left.left = new TreeNode (4); root.right.left = new TreeNode (5); root.right.right = new TreeNode (6); return root }} on how to understand the serialized binary tree in python to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

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.