二叉樹的反序列化

反序列化

樹的反序列化故名知意就是將一個(gè)序列化成字符串或者其它形式的數(shù)據(jù)重新的生成一顆二叉樹,如下這顆二叉樹將它序列化成字符串后的結(jié)果[5,4,null,null,3,2,1],而現(xiàn)在要做的是要將這個(gè)字符串重新的生成一顆二叉樹(生成下面這顆樹，因?yàn)檫@個(gè)字符串就是通過這顆樹序列化來的)。

解題思路

• 首先，應(yīng)該先拿到一個(gè)序列化后數(shù)據(jù)，可能是隊(duì)列、棧、字符串(中間會(huì)有字符將其分割)，或其它形式的數(shù)據(jù)
• 當(dāng)一個(gè)節(jié)點(diǎn)下面沒有數(shù)據(jù)的時(shí)候，我這里采用的是用null來表示的空，比如上面節(jié)點(diǎn)2下面沒有數(shù)據(jù),在字符串中就用了null來表示
• 這里我將字符串轉(zhuǎn)換成了隊(duì)列的形式，當(dāng)然使用字符串的形式也可以的，例如:通過split方法來分割成數(shù)組
• 創(chuàng)建一個(gè)隊(duì)列，把要進(jìn)行處理的節(jié)點(diǎn)放和主到隊(duì)列里面，比如，每次循環(huán)的時(shí)候?qū)⒆笥曳种Х诺竭@個(gè)隊(duì)列里面，因?yàn)殛?duì)列有FIFO的特性，在處理完左支的時(shí)候能夠放便的拿到右支的node
• 接下來分析代碼

TreeNode結(jié)構(gòu)體

這個(gè)里面的數(shù)據(jù)很容易就看懂，val是當(dāng)前節(jié)點(diǎn)的數(shù)據(jù);left ,right分別保存的是左支和右支的數(shù)據(jù)

針對(duì)每個(gè)數(shù)據(jù)生成對(duì)應(yīng)的TreeNode

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

這個(gè)方法主要是生成TreeNode對(duì)象的方法，上面說到當(dāng)節(jié)點(diǎn)下面沒有子節(jié)點(diǎn)的時(shí)候就會(huì)用null來表不，所以這里接收到的形參如果是null的話就會(huì)反回一個(gè)空指針，相反如果不是null就會(huì)反回一個(gè)創(chuàng)建的TreeNode對(duì)象，并將val屬性賦值

反序列化方法

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(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)
		}
	}
	return
}

代碼解讀

這個(gè)方法的代碼比較多，這里就會(huì)塊來說一下:

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

這幾行代碼無非就是一個(gè)邊界條件的判斷的問題,當(dāng)傳來的隊(duì)列沒有數(shù)據(jù)的時(shí)候就返回一個(gè)空,為啥是隊(duì)列?因?yàn)槲覍⒆址D(zhuǎn)成了隊(duì)列

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

var tempNodeQueue []*TreeNode:這里創(chuàng)建一個(gè)TreeNode指針數(shù)組的原因是存儲(chǔ)要操作節(jié)點(diǎn)的數(shù)據(jù),因?yàn)槲覍⑿蛄谢蟮臄?shù)據(jù)轉(zhuǎn)成了隊(duì)列,所以在這個(gè)數(shù)組中最后一個(gè)元素應(yīng)該是先出來的數(shù)組,同樣第一個(gè)出來的數(shù)據(jù)是這顆二叉樹的根節(jié)點(diǎn),將這個(gè)節(jié)點(diǎn)保存到了這個(gè)隊(duì)列里面,然后這個(gè)隊(duì)列將在下面的for循環(huán)中使用到,其余的下面再說.

resultNode = generateNode(dataQueue[len(dataQueue) - 1]):這里便是將出隊(duì)列,并通過generateNode生成一個(gè)TreeNode對(duì)象

dataQueue = dataQueue[:len(dataQueue) - 1]:因?yàn)橛幸粋€(gè)數(shù)組已經(jīng)出了隊(duì)列,就要將其去掉

tempNodeQueue = append(tempNodeQueue,resultNode):經(jīng)過一個(gè)判空處理,便將這個(gè)節(jié)點(diǎn)保存到了上面提到的隊(duì)列里面

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

當(dāng)進(jìn)入For循環(huán)后,也就證明現(xiàn)在這個(gè)隊(duì)列里面有數(shù)據(jù),不管三七二十一,先將里面的數(shù)據(jù)彈出,因?yàn)橹挥杏辛藬?shù)據(jù)才可以進(jìn)行下面的操作(無數(shù)據(jù),不編程)

tempNodeQueue = tempNodeQueue[1:]:因?yàn)榍耙恍写a將數(shù)據(jù)在這個(gè)隊(duì)列里面彈出了, 所以一行代碼是將已彈出的數(shù)據(jù)去除

tempNode.left = generateNode(dataQueue[len(dataQueue) - 1]):當(dāng)傳來序列化二叉樹的存在數(shù)據(jù)的時(shí)候就將其節(jié)點(diǎn)的left , right分支進(jìn)么賦值,下一行代碼就是將彈出的數(shù)據(jù)去除,接下來的兩行便是對(duì)right節(jié)點(diǎn)的處理,同left一樣

tempNodeQueue = append(tempNodeQueue,tempNode.left):如果tempNode的左節(jié)點(diǎn)存在的時(shí)候就將其保存到隊(duì)列中,遍歷tempNodeQueue隊(duì)列,再次執(zhí)行上面的步驟.

可能有小伙伴存在疑問?

所返回的resultNode變量只賦值過一次,那子節(jié)點(diǎn)是如何賦值的呢?因?yàn)樗械腡reeNode的節(jié)點(diǎn)我都是通過指針來處理的,

而在For里面的第一行代碼所彈出的數(shù)據(jù)指向的地址正是resultNode的地址,所以在生成完樹之后,我只要抓住這顆樹的根節(jié)點(diǎn)就好了

二叉樹的序列化

介紹

樹的序列化又是怎么一回事呢？我可以將這顆樹轉(zhuǎn)換成一定格式的數(shù)據(jù)結(jié)構(gòu)，比如：轉(zhuǎn)換成一段文本可以持久化到硬盤中。

那有什么作用呢？比如Redis中的數(shù)據(jù)是在內(nèi)存中的，它有一個(gè)功能是每隔一段 時(shí)間可以將數(shù)據(jù)保存到硬盤中以防止突發(fā)的斷電導(dǎo)至數(shù)據(jù)的丟失

這里說的樹的序列化你也可以這樣的理解，我要將一顆二叉樹里面的數(shù)據(jù)序列化保存到硬盤，以便下次使用這里面的數(shù)的據(jù)的時(shí)候可以直接生成這顆樹

解題思路

• 參于解這種題，想到的是通過對(duì)二叉樹的按層來遍歷來解決，當(dāng)一個(gè)節(jié)點(diǎn)沒有子節(jié)點(diǎn)的時(shí)候，將其視為空， 我這里用null來表示的
• 在這個(gè)里面序列化時(shí)我是先處理的左子節(jié)點(diǎn)，然后在處理右子節(jié)點(diǎn)
• 同反序列化一樣，暫存數(shù)據(jù)的結(jié)構(gòu)我使用的是隊(duì)列的方式，還需要將獲得的數(shù)據(jù)也要保存到一個(gè)隊(duì)列里面
• 在程序的開始如果所給的頭節(jié)點(diǎn)不為空，就將頭節(jié)點(diǎn)加入到隊(duì)列
• 在對(duì)隊(duì)列遍歷的時(shí)候彈出隊(duì)列里面的數(shù)據(jù)(注:隊(duì)列有FIFO的特性)，將本節(jié)點(diǎn)的val放到保存數(shù)據(jù)的隊(duì)列里面
• 依次將本節(jié)點(diǎn)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)放到隊(duì)列里面，在次執(zhí)行上述步驟

代碼

/**
序列化二叉樹
*/
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
}

代碼解讀

這些代碼還是很好看懂的，這里就說下for里面的代碼吧~~

tempNode = tempQueue[0]:在隊(duì)列里面彈出一個(gè)數(shù)據(jù)

saveSerData = append(saveSerData, tempNode.val):將tempNode的val屬性保存到saveSerData隊(duì)列里面

下面的if就是判斷當(dāng)這個(gè)節(jié)點(diǎn)為空或者是不為空的時(shí)候需要分別怎么處理數(shù)據(jù)，上面說到如果一個(gè)節(jié)點(diǎn)下面沒有子節(jié)點(diǎn)，這里就用null來表示，所以當(dāng)沒有子節(jié)點(diǎn)的時(shí)候就用將null添加到隊(duì)列里面

tempQueue = tempQueue[1:]:對(duì)隊(duì)列重新賦值，將彈出的那個(gè)數(shù)據(jù)去掉

tempQueue = append(tempQueue, tempNode.left):將左節(jié)點(diǎn)加入到隊(duì)列里面，下一行同理

運(yùn)行結(jié)果

到此這篇關(guān)于go語言實(shí)現(xiàn)二叉樹的序例化與反序列化的文章就介紹到這了,更多相關(guān)go序例化內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論