利用go語言實現查詢二元樹中的最大寬度

2022-05-17 13:01:06

介紹

這道題是這樣的，有一個二元樹，讓求出這顆Bt樹裡面最大的寬度是有幾個節點，同時還要求出最大寬度的這些節點在第幾層？

比如:下面這顆樹，它每層最大的寬度是3，所在的層數是在第3層

流程

這個題主要是使用佇列的方式來儲存需要遍歷的節點
同時還需要幾個變數來儲存最大的寬度(maxWidth)、每層有幾個節點(count)、最大寬度所在的層(maxInrow)、當前層最後一個節點(currentRowEndNode)、下一層最後一個節點(nextRowEndNode)
程式的一開始，便將二元樹的頭節點加入到佇列裡面，同時將這個節點賦值給下一層最後一個節點因當根節點只有一個節點，同時也將當前行的最後一個節點賦值為這個節點
通過迴圈來對這個佇列進行遍歷，當進入迴圈後就認為走到了一個節點，count就要加1
將佇列裡面的節點元素開始彈出，如果它的子節點存在就將子節點賦值給nextRowEndNode,先賦值左再賦值右(因為先處理的是左子節點)，同時將這倆個節點加入到佇列裡面(如果它們存在的話)
還要對當前的節點進行一個判斷，判斷當前的節點是不是到了當前行的最後一個節點，如果是的話，就代表當前行的資料已經處理完成，就要把nextRowEndNode賦值給currentRowEndNode，count置0
進行下一波迴圈

程式碼

二元樹結構體

type TreeNode struct {
	val   string
	left  *TreeNode
	right *TreeNode
}

測試程式碼

func main() {
	sNode := &TreeNode{val: "1"}
	sNode.left = &TreeNode{val: "2"}
	sNode.right = &TreeNode{val: "3"}
	sNode.left.left = &TreeNode{val: "4"}
	sNode.left.right = &TreeNode{val: "5"}
	sNode.right.left = &TreeNode{val: "6"}
	sNode.left.left.left = &TreeNode{val: "7"}
	sNode.left.left.right = &TreeNode{val: "8"}
	sNode.left.right.left = &TreeNode{val: "9"}
	sNode.left.right.right = &TreeNode{val: "10"}
	sNode.right.left.left = &TreeNode{val: "11"}
	maxW, row := findBtMaxWidth(sNode)
	fmt.Printf("最大寬度: %v;在第 %v層", maxW, row)
}

查詢二元樹最大寬度的程式碼

func findBtMaxWidth(bt *TreeNode) (maxWidth int, maxInrow int) {
	row := 0
	//臨時儲存節點的佇列
	var tempSaveNodeQueue []*TreeNode
	//儲存寬度
	count := 1
	var currentRowEndNode *TreeNode
	var nextRowEndNode *TreeNode
	if bt != nil {
		nextRowEndNode = bt
		currentRowEndNode = nextRowEndNode
		tempSaveNodeQueue = append(tempSaveNodeQueue, bt)
	}
	for len(tempSaveNodeQueue) != 0 {
		count++
		treeNode := tempSaveNodeQueue[0]
		tempSaveNodeQueue = tempSaveNodeQueue[1:]

		if treeNode.left != nil {
			nextRowEndNode = treeNode.left
			tempSaveNodeQueue = append(tempSaveNodeQueue, treeNode.left)
		}

		if treeNode.right != nil {
			nextRowEndNode = treeNode.right
			tempSaveNodeQueue = append(tempSaveNodeQueue, treeNode.right)
		}
		if currentRowEndNode == treeNode {
			row++
			currentRowEndNode = nextRowEndNode
			if maxWidth < count {
				maxInrow = row
				maxWidth = count
			}
			count = 0
		}
	}
	return
}

程式碼解讀

這裡面的程式碼大部分的邏輯還是很簡單的，

說一下在if判斷裡面的程式碼叭，為啥要分別將子節點的left、right分別賦值給nextRowEndNode呢？

因為在一個子節點下面的left和right並不是全都存在的，有的時候會是個空，所以這裡要分別賦值

if currentRowEndNode == treeNode:這一個判斷裡面，因為如果進入到了這個判斷裡面就說明到了當前層的最後一個節點了，所以就要把下一層的最後一個節點賦值給當前層的最後一個節點；

因為還有一個要找出最大寬度的一個功能，所以這個maxWidth要和coutn做一個比較如果maxWidth比較小的話就將count賦值給maxWidth，同時將當前的層數賦值給maxInrow；

row:而row在這裡面所充當的角色是當前是完成第幾行的操作

為啥這裡要定義一個currentRowEndNode和nextRowEndNode？

這種的寫法按層來處理，當獲取到一個節點的時候，這時我就要拿到他們的子節點，如果現在不獲取子節點的話在後面是沒有辦法獲取的，當這一行結束的時候將nextRowEndNode賦值給currentRowEndNode，接下來nextRowEndNode再找下一層的最後一個節點。

到此這篇關於利用go語言實現查詢二元樹中的最大寬度的文章就介紹到這了,更多相關go查詢二元樹內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

利用go語言實現查詢二元樹中的最大寬度

目錄

介紹

流程

程式碼

二元樹結構體

測試程式碼

查詢二元樹最大寬度的程式碼

程式碼解讀

熱門文章