python中的序列化二叉樹如何理解

這篇文章將為大家詳細講解有關python中的序列化二叉樹如何理解，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

題目

請實現兩個函數，分別用來序列化和反序列化二叉樹。

分析

我們清楚可以通過前序遍歷序列和中序遍歷序列創造出一棵二叉樹。因此，我們可以先把一棵二叉樹序列化成一個前序遍歷序列和一個中序遍歷序列，然后在反序列化時通過這兩種序列還原二叉樹。

但是，該方法有兩個缺點：

1. 該方法要求二叉樹中不能有數值重復的節點

2. 只有當兩個序列中所有數據讀出來才能開始序列化。如果兩個遍歷序列的數據是從一個流里讀出來的，那么可能需要等待較長時間。

實際上，如果二叉樹的序列化是從根節點開始的，那么相應的反序列化在根節點的數值讀出來的時候就可以開始了。因此，我們可以根據前序遍歷的順序來序列化二叉樹，因為前序遍歷是從根節點開始的。在遍歷二叉樹碰到空指針時，這些空指針序列化為一個特殊的字符(如$)。另外，節點的數值之間要用一個特殊字符 (如,) 隔開。

反序列化二叉樹也按照前序遍歷思路。

放碼

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;
	}
	
}

測試

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("1,2,4,$,$,$,3,5,$,$,6,$,$,", result.toString());
	}

	@Test
	public void testReadNum() {
		SerializeBinaryTree sbt = new SerializeBinaryTree();
		StringBuilder sb = new StringBuilder("1,2,4,$,$,$,3,5,$,$,6,$,$,");
		
		assertEquals(1, sbt.readNum(sb).intValue());
		assertEquals("2,4,$,$,$,3,5,$,$,6,$,$,", sb.toString());
		
		assertEquals(2, sbt.readNum(sb).intValue());
		assertEquals("4,$,$,$,3,5,$,$,6,$,$,", sb.toString());
		
		assertEquals(4, sbt.readNum(sb).intValue());
		assertEquals("$,$,$,3,5,$,$,6,$,$,", sb.toString());
		
		assertNull(sbt.readNum(sb));
		assertEquals("$,$,3,5,$,$,6,$,$,", sb.toString());
		
		assertNull(sbt.readNum(sb));
		assertEquals("$,3,5,$,$,6,$,$,", sb.toString());

		assertNull(sbt.readNum(sb));
		assertEquals("3,5,$,$,6,$,$,", sb.toString());
		
		assertEquals(3, sbt.readNum(sb).intValue());
		assertEquals("5,$,$,6,$,$,", sb.toString());
		
		assertEquals(5, sbt.readNum(sb).intValue());
		assertEquals("$,$,6,$,$,", sb.toString());
		
		assertNull(sbt.readNum(sb));
		assertEquals("$,6,$,$,", sb.toString());

		assertNull(sbt.readNum(sb));
		assertEquals("6,$,$,", sb.toString());
		
		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;
	}

}

關于python中的序列化二叉樹如何理解就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。