利用go语言判断是否是完全二叉树

目录

• 一、什么是完全二叉树？
• 二、流程
• 三、代码
• 1.树节点
• 2.测试代码
• 3.判断树是否为完全二叉树代码
• 4.代码解读
• 5.运行结果

一、什么是完全二叉树？

先看如下这一张图：

这个一颗二叉树，如何区分该树是不是完全二叉树呢？

• 当一个节点存在右子节点但是不存在左子节点这颗树视为非完全二叉树
• 当一个节点的左子节点存在但是右子节点不存在视为完全二叉树
• 如果没有子节点，那也是要在左侧开始到右侧依次没有子节点才视为完全二叉树,就像上图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
}

4.代码解读

这段代码里面没有多少好说的,就说下for里面第一个if判断叭

这里看下上面流程中最后两个条件,当满足最后两个条件的时候才可以判断出来这颗树是否是完全二叉树.

同样因为实现判断是否是完全二叉树是通过对树的按层遍历来处理的，因为对树的按层遍历通过队列是可以间单的实现的。所以这里使用到了队列

至于这里为什么要单独创建一个isSingleNode变量:

• 因为当有一个节点左侧节点或者是右侧的节点没有的时候,在这同一层后面如果还有不为空的节点时,那么这颗树便不是完全二叉树,看下图

在这颗树的最后一层绿色涂鸭处是少一个节点的,所以我用了一个变量我标识当前节点(在上图表示节点2)的子节点是不是少一个,如果少了当前节点(在上图表示节点2)的下一个节点(在上图表示节点3)的子节点(在上图表示4和5)如果存在则不是完全二叉树,所以这就是创建了一个isSingleNode变量的作用

5.运行结果

到此这篇关于利用go语言判断是否是完全二叉树的文章就介绍到这了,更多相关go 二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！