go語言實現二元樹的序例化與反序列化

2022-05-17 13:00:58

二元樹的反序列化

反序列化

樹的反序列化故名知意就是將一個序列化成字串或者其它形式的資料重新的生成一顆二元樹,如下這顆二元樹將它序列化成字串後的結果[5,4,null,null,3,2,1],而現在要做的是要將這個字串重新的生成一顆二元樹(生成下面這顆樹，因為這個字串就是通過這顆樹序列化來的)。

解題思路

首先，應該先拿到一個序列化後資料，可能是佇列、棧、字串(中間會有字元將其分割)，或其它形式的資料
當一個節點下面沒有資料的時候，我這裡採用的是用null來表示的空，比如上面節點2下面沒有資料,在字串中就用了null來表示
這裡我將字串轉換成了佇列的形式，當然使用字串的形式也可以的，例如:通過split方法來分割成陣列
建立一個佇列，把要進行處理的節點放和主到佇列裡面，比如，每次迴圈的時候將左右分支放到這個佇列裡面，因為佇列有FIFO的特性，在處理完左支的時候能夠放便的拿到右支的node
接下來分析程式碼

TreeNode結構體

這個裡面的資料很容易就看懂，val是當前節點的資料;left ,right分別儲存的是左支和右支的資料

針對每個資料生成對應的TreeNode

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

這個方法主要是生成TreeNode物件的方法，上面說到當節點下面沒有子節點的時候就會用null來表不，所以這裡接收到的形參如果是null的話就會反回一個空指標，相反如果不是null就會反回一個建立的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
}

這幾行程式碼無非就是一個邊界條件的判斷的問題,當傳來的佇列沒有資料的時候就返回一個空,為啥是佇列?因為我將字串轉成了佇列

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

var tempNodeQueue []*TreeNode:這裡建立一個TreeNode指標陣列的原因是儲存要操作節點的資料,因為我將序列化後的資料轉成了佇列,所以在這個陣列中最後一個元素應該是先出來的陣列,同樣第一個出來的資料是這顆二元樹的根節點,將這個節點儲存到了這個佇列裡面,然後這個佇列將在下面的for迴圈中使用到,其餘的下面再說.

resultNode = generateNode(dataQueue[len(dataQueue) - 1]):這裡便是將出佇列,並通過generateNode生成一個TreeNode物件

dataQueue = dataQueue[:len(dataQueue) - 1]:因為有一個陣列已經出了佇列,就要將其去掉

tempNodeQueue = append(tempNodeQueue,resultNode):經過一個判空處理,便將這個節點儲存到了上面提到的佇列裡面

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迴圈後,也就證明現在這個佇列裡面有資料,不管三七二十一,先將裡面的資料彈出,因為只有有了資料才可以進行下面的操作(無資料,不程式設計)

tempNodeQueue = tempNodeQueue[1:]:因為前一行程式碼將資料在這個佇列裡面彈出了, 所以一行程式碼是將已彈出的資料去除

tempNode.left = generateNode(dataQueue[len(dataQueue) - 1]):當傳來序列化二元樹的存在資料的時候就將其節點的left , right分支進麼賦值,下一行程式碼就是將彈出的資料去除,接下來的兩行便是對right節點的處理,同left一樣

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

可能有小夥伴存在疑問?

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

而在For裡面的第一行程式碼所彈出的資料指向的地址正是resultNode的地址,所以在生成完樹之後,我只要抓住這顆樹的根節點就好了

二元樹的序列化

介紹

樹的序列化又是怎麼一回事呢？我可以將這顆樹轉換成一定格式的資料結構，比如：轉換成一段文字可以持久化到硬碟中。

那有什麼作用呢？比如Redis中的資料是在記憶體中的，它有一個功能是每隔一段時間可以將資料儲存到硬碟中以防止突發的斷電導至資料的丟失

這裡說的樹的序列化你也可以這樣的理解，我要將一顆二元樹裡面的資料序列化儲存到硬碟，以便下次使用這裡面的數的據的時候可以直接生成這顆樹

解題思路

參於解這種題，想到的是通過對二元樹的按層來遍歷來解決，當一個節點沒有子節點的時候，將其視為空，我這裡用null來表示的
在這個裡面序列化時我是先處理的左子節點，然後在處理右子節點
同反序列化一樣，暫存資料的結構我使用的是佇列的方式，還需要將獲得的資料也要儲存到一個佇列裡面
在程式的開始如果所給的頭節點不為空，就將頭節點加入到佇列
在對佇列遍歷的時候彈出佇列裡面的資料(注:佇列有FIFO的特性)，將本節點的val放到儲存資料的佇列裡面
依次將本節點的左子節點和右子節點放到佇列裡面，在次執行上述步驟

程式碼

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