二叉樹的反序列化

反序列化

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

解題思路

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

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

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

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

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

這個方法主要是生成TreeNode對象的方法，上面說到當節(jié)點下面沒有子節(jié)點的時候就會用null來表不，所以這里接收到的形參如果是null的話就會反回一個空指針，相反如果不是null就會反回一個創(chuàng)建的TreeNode對象，并將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
}

代碼解讀

這個方法的代碼比較多，這里就會塊來說一下:

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

這幾行代碼無非就是一個邊界條件的判斷的問題,當傳來的隊列沒有數(shù)據(jù)的時候就返回一個空,為啥是隊列?因為我將字符串轉(zhuǎn)成了隊列

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)建一個TreeNode指針數(shù)組的原因是存儲要操作節(jié)點的數(shù)據(jù),因為我將序列化后的數(shù)據(jù)轉(zhuǎn)成了隊列,所以在這個數(shù)組中最后一個元素應(yīng)該是先出來的數(shù)組,同樣第一個出來的數(shù)據(jù)是這顆二叉樹的根節(jié)點,將這個節(jié)點保存到了這個隊列里面,然后這個隊列將在下面的for循環(huán)中使用到,其余的下面再說.

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

dataQueue = dataQueue[:len(dataQueue) - 1]:因為有一個數(shù)組已經(jīng)出了隊列,就要將其去掉

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

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

當進入For循環(huán)后,也就證明現(xiàn)在這個隊列里面有數(shù)據(jù),不管三七二十一,先將里面的數(shù)據(jù)彈出,因為只有有了數(shù)據(jù)才可以進行下面的操作(無數(shù)據(jù),不編程)

tempNodeQueue = tempNodeQueue[1:]:因為前一行代碼將數(shù)據(jù)在這個隊列里面彈出了, 所以一行代碼是將已彈出的數(shù)據(jù)去除

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

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

可能有小伙伴存在疑問?

所返回的resultNode變量只賦值過一次,那子節(jié)點是如何賦值的呢?因為所有的TreeNode的節(jié)點我都是通過指針來處理的,

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

二叉樹的序列化

介紹

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

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

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

解題思路

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

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

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

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

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

運行結(jié)果

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

最新評論