利用go語言判斷是否是完全二元樹

2022-05-17 10:00:03

一、什麼是完全二元樹？

先看如下這一張圖：

這個一顆二元樹，如何區分該樹是不是完全二元樹呢？

當一個節點存在右子節點但是不存在左子節點這顆樹視為非完全二元樹
當一個節點的左子節點存在但是右子節點不存在視為完全二元樹
如果沒有子節點，那也是要在左側開始到右側依次沒有子節點才視為完全二元樹,就像上圖2中

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

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

二、流程

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

首先準備一個佇列，按層遍歷使用佇列是最好的一種解決方法
首先將頭節點加入到佇列裡面(如果頭節點為空，你可以認為它是一個非完全二元樹也可以認為它是完全二元樹)
遍歷該佇列跳出遍歷的條件是直到這個佇列為空時
這個時候需要準備一個Bool的變數，如果當一個節點的左子節點或者右子節點不存在時將其置成true
當Bool變數為true並且剩餘節點的左或右子節點不為空該樹就是非完全二元樹
當一樹的左子節點不存在並且右子節點存在,該樹也是非完全二元樹

三、程式碼

1.樹節點

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 這裡預設根節點為空屬於完全二元樹,這個可以自已定義是否為完全二元樹/***/
func IsCompleteBt(root *TreeNode) bool {
	if root == nil {
		return true
	}

	/**
	* 條件:
	* 	1.當一個節點存在右子節點但是不存在左子節點這顆樹視為非完全二元樹
	*	2.當一個節點的左子節點存在但是右子節點不存在視為完全二元樹
	 */
	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
}