快捷導(dǎo)航

利用go語(yǔ)言判斷是否是完全二叉樹(shù)

更新時(shí)間：2022年05月17日 11:58:12 作者：??呆呆燦????

這篇文章主要介紹了利用go語(yǔ)言判斷是否是完全二叉樹(shù)，當(dāng)一個(gè)節(jié)點(diǎn)存在右子節(jié)點(diǎn)但是不存在左子節(jié)點(diǎn)這顆樹(shù)視為非完全二叉樹(shù)，通過(guò)利用GO語(yǔ)言判斷來(lái)判斷出否是完全二叉樹(shù)，詳細(xì)內(nèi)容參考如下

一、什么是完全二叉樹(shù)？

先看如下這一張圖：

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

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

而上面第一張圖這顆二叉樹(shù)很明顯是一顆非完全二叉樹(shù)，因?yàn)樵诘谌龑右簿褪窃诠?jié)點(diǎn)2它并沒(méi)有右子節(jié)點(diǎn)。在6和4節(jié)點(diǎn)中隔開(kāi)了一個(gè)節(jié)點(diǎn)(2節(jié)點(diǎn)沒(méi)有右子節(jié)點(diǎn))，所以不是完全二叉樹(shù)

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

二、流程

這道題可以使用按層遍歷的方式來(lái)解決：

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

三、代碼

1.樹(shù)節(jié)點(diǎn)

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

2.測(cè)試代碼

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("是完全二叉樹(shù)")
	} else {
		fmt.Println("不是完全二叉樹(shù)")
	}
}

3.判斷樹(shù)是否為完全二叉樹(shù)代碼

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

	/**
	* 條件:
	* 	1.當(dāng)一個(gè)節(jié)點(diǎn)存在右子節(jié)點(diǎn)但是不存在左子節(jié)點(diǎn)這顆樹(shù)視為非完全二叉樹(shù)
	*	2.當(dāng)一個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)存在但是右子節(jié)點(diǎn)不存在視為完全二叉樹(shù)
	 */
	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.代碼解讀

這段代碼里面沒(méi)有多少好說(shuō)的,就說(shuō)下for里面第一個(gè)if判斷叭

這里看下上面流程中最后兩個(gè)條件,當(dāng)滿(mǎn)足最后兩個(gè)條件的時(shí)候才可以判斷出來(lái)這顆樹(shù)是否是完全二叉樹(shù).

同樣因?yàn)閷?shí)現(xiàn)判斷是否是完全二叉樹(shù)是通過(guò)對(duì)樹(shù)的按層遍歷來(lái)處理的，因?yàn)閷?duì)樹(shù)的按層遍歷通過(guò)隊(duì)列是可以間單的實(shí)現(xiàn)的。所以這里使用到了隊(duì)列

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

因?yàn)楫?dāng)有一個(gè)節(jié)點(diǎn)左側(cè)節(jié)點(diǎn)或者是右側(cè)的節(jié)點(diǎn)沒(méi)有的時(shí)候,在這同一層后面如果還有不為空的節(jié)點(diǎn)時(shí),那么這顆樹(shù)便不是完全二叉樹(shù),看下圖

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