一、什么是完全二叉樹？

先看如下這一張圖：

這個一顆二叉樹，如何區(qū)分該樹是不是完全二叉樹呢？

• 當(dāng)一個節(jié)點存在右子節(jié)點但是不存在左子節(jié)點這顆樹視為非完全二叉樹
• 當(dāng)一個節(jié)點的左子節(jié)點存在但是右子節(jié)點不存在視為完全二叉樹
• 如果沒有子節(jié)點，那也是要在左側(cè)開始到右側(cè)依次沒有子節(jié)點才視為完全二叉樹,就像上圖2中

而上面第一張圖這顆二叉樹很明顯是一顆非完全二叉樹，因為在第三層也就是在節(jié)點2它并沒有右子節(jié)點。在6和4節(jié)點中隔開了一個節(jié)點(2節(jié)點沒有右子節(jié)點)，所以不是完全二叉樹

再看第二張圖，這顆樹就是一個完全二叉樹，雖然在這個顆節(jié)點3沒有右子節(jié)點，但是6 4 5節(jié)點之間并沒有空缺的子節(jié)點，這里就解釋了上面說的第三條(如何沒有子節(jié)點，那也是在左側(cè)開始到右側(cè)依次沒有子節(jié)點才視為完全二叉樹)

二、流程

這道題可以使用按層遍歷的方式來解決：

• 首先準(zhǔn)備一個隊列，按層遍歷使用隊列是最好的一種解決方法
• 首先將頭節(jié)點加入到隊列里面(如果頭節(jié)點為空，你可以認(rèn)為它是一個非完全二叉樹也可以認(rèn)為它是完全二叉樹)
• 遍歷該隊列跳出遍歷的條件是直到這個隊列為空時
• 這個時候需要準(zhǔn)備一個Bool的變量，如果當(dāng)一個節(jié)點的左子節(jié)點或者右子節(jié)點不存在時將其置成true
• 當(dāng)Bool變量為true并且剩余節(jié)點的左或右子節(jié)點不為空該樹就是非完全二叉樹
• 當(dāng)一樹的左子節(jié)點不存在并且右子節(jié)點存在,該樹也是非完全二叉樹

三、代碼

1.樹節(jié)點

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

2.測試代碼

func main() {
	root := &TreeNode{val: "1"}
	root.left = &TreeNode{val: "2"}
	root.left.left = &TreeNode{val: "4"}
	root.left.right = &TreeNode{val: "10"}
	root.left.left.left = &TreeNode{val: "7"}
	root.right = &TreeNode{val: "3"}
	root.right.left = &TreeNode{val: "5"}
	root.right.right = &TreeNode{val: "6"}
	if IsCompleteBt(root) {
		fmt.Println("是完全二叉樹")
	} else {
		fmt.Println("不是完全二叉樹")
	}
}

3.判斷樹是否為完全二叉樹代碼

// IsCompleteBt 這里默認(rèn)根節(jié)點為空屬于完全二叉樹,這個可以自已定義是否為完全二叉樹/***/
func IsCompleteBt(root *TreeNode) bool {
	if root == nil {
		return true
	}

	/**
	* 條件:
	* 	1.當(dāng)一個節(jié)點存在右子節(jié)點但是不存在左子節(jié)點這顆樹視為非完全二叉樹
	*	2.當(dāng)一個節(jié)點的左子節(jié)點存在但是右子節(jié)點不存在視為完全二叉樹
	 */
	var tempNodeQueue []*TreeNode

	tempNodeQueue = append(tempNodeQueue, root)

	var tempNode *TreeNode
	isSingleNode := false
	for len(tempNodeQueue) != 0 {
		tempNode = tempNodeQueue[0]
		tempNodeQueue = tempNodeQueue[1:]

		if (isSingleNode && (tempNode.left != nil || tempNode.right != nil)) || (tempNode.left == nil && tempNode.right != nil){
			return false
		}

		if tempNode.left != nil{
			tempNodeQueue = append(tempNodeQueue,tempNode.left)
		}else{
			isSingleNode = true
		}

		if  tempNode.right != nil {
			tempNodeQueue = append(tempNodeQueue, tempNode.right)
		}else{
			isSingleNode = true
		}
	}
	return true
}

4.代碼解讀

這段代碼里面沒有多少好說的,就說下for里面第一個if判斷叭

這里看下上面流程中最后兩個條件,當(dāng)滿足最后兩個條件的時候才可以判斷出來這顆樹是否是完全二叉樹.

同樣因為實現(xiàn)判斷是否是完全二叉樹是通過對樹的按層遍歷來處理的，因為對樹的按層遍歷通過隊列是可以間單的實現(xiàn)的。所以這里使用到了隊列

至于這里為什么要單獨創(chuàng)建一個isSingleNode變量:

• 因為當(dāng)有一個節(jié)點左側(cè)節(jié)點或者是右側(cè)的節(jié)點沒有的時候,在這同一層后面如果還有不為空的節(jié)點時,那么這顆樹便不是完全二叉樹,看下圖

在這顆樹的最后一層綠色涂鴨處是少一個節(jié)點的,所以我用了一個變量我標(biāo)識當(dāng)前節(jié)點(在上圖表示節(jié)點2)的子節(jié)點是不是少一個,如果少了當(dāng)前節(jié)點(在上圖表示節(jié)點2)的下一個節(jié)點(在上圖表示節(jié)點3)的子節(jié)點(在上圖表示4和5)如果存在則不是完全二叉樹,所以這就是創(chuàng)建了一個isSingleNode變量的作用

5.運行結(jié)果

到此這篇關(guān)于利用go語言判斷是否是完全二叉樹的文章就介紹到這了,更多相關(guān)go 二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論