python中的序列化二叉樹(shù)如何理解

這篇文章將為大家詳細(xì)講解有關(guān)python中的序列化二叉樹(shù)如何理解，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

題目

請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來(lái)序列化和反序列化二叉樹(shù)。

分析

我們清楚可以通過(guò)前序遍歷序列和中序遍歷序列創(chuàng)造出一棵二叉樹(shù)。因此，我們可以先把一棵二叉樹(shù)序列化成一個(gè)前序遍歷序列和一個(gè)中序遍歷序列，然后在反序列化時(shí)通過(guò)這兩種序列還原二叉樹(shù)。

但是，該方法有兩個(gè)缺點(diǎn)：

1. 該方法要求二叉樹(shù)中不能有數(shù)值重復(fù)的節(jié)點(diǎn)

2. 只有當(dāng)兩個(gè)序列中所有數(shù)據(jù)讀出來(lái)才能開(kāi)始序列化。如果兩個(gè)遍歷序列的數(shù)據(jù)是從一個(gè)流里讀出來(lái)的，那么可能需要等待較長(zhǎng)時(shí)間。

實(shí)際上，如果二叉樹(shù)的序列化是從根節(jié)點(diǎn)開(kāi)始的，那么相應(yīng)的反序列化在根節(jié)點(diǎn)的數(shù)值讀出來(lái)的時(shí)候就可以開(kāi)始了。因此，我們可以根據(jù)前序遍歷的順序來(lái)序列化二叉樹(shù)，因?yàn)榍靶虮闅v是從根節(jié)點(diǎn)開(kāi)始的。在遍歷二叉樹(shù)碰到空指針時(shí)，這些空指針序列化為一個(gè)特殊的字符(如$)。另外，節(jié)點(diǎn)的數(shù)值之間要用一個(gè)特殊字符 (如,) 隔開(kāi)。

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

放碼

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

測(cè)試

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

}

關(guān)于python中的序列化二叉樹(shù)如何理解就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。