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

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

十年的額濟納網站建設經驗，針對設計、前端、開發、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。營銷型網站的優勢是能夠根據用戶設備顯示端的尺寸不同，自動調整額濟納建站的顯示方式，使網站能夠適用不同顯示終端，在瀏覽器中調整網站的寬度，無論在任何一種瀏覽器上瀏覽網站，都能展現優雅布局與設計，從而大程度地提升瀏覽體驗。成都創新互聯從事“額濟納網站設計”,“額濟納網站推廣”以來，每個客戶項目都認真落實執行。

題目

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

分析

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

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

該方法要求二叉樹中不能有數值重復的節點
只有當兩個序列中所有數據讀出來才能開始序列化。如果兩個遍歷序列的數據是從一個流里讀出來的，那么可能需要等待較長時間。

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

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

放碼

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

當前題目：python中的序列化二叉樹如何理解
本文來源：http://www.2m8n56k.cn/article40/jphsho.html

成都網站建設公司_創新互聯，為您提供網站排名、企業建站、網站營銷、動態網站、網站導航、網站設計公司