搜索
简帛阁>技术文章>利用go语言判断是否是完全二叉树

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

一、什么是完全二叉树?

先看如下这一张图:

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

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

录一、什么是完全二叉?二、流程三、代码1节点2测试代码3判断是否完全二叉代码4代码解读5运行结果一、什么是完全二叉?先看如下这一张图:这个一颗二叉,如何区分该是不是完全二叉呢?当一
首先我们要了解什么事完全二叉完全二叉:假设一颗二叉的深度为h,除了第h层以外,其余各层节点的个数全都达到了每层的最大值,即2^(n1),只有第h层的结点个数小于或者等于2^(h1),而且节点
首先要知道完全二叉的定义:前n1层都是满的,第n层如有空缺,则右边有空缺,即第n层的右边的某个节点开始有空缺,它的左边满的,右边空的。以二叉搜索举例。include<bits/stdc
按层遍历,存在两种情况:(1)当前节点有右孩子却没有左孩子,一定不是完全二叉(2)当前节点不是同时有左右两个孩子的时候,后面遍历到的所有节点都必须叶节点,否则不是完全二叉具体方法在注释写的很清楚
心思路:1如果有右节点,没有左节点,直接返回False2如果左右节点都没有,或者只有左节点,就看看后面的节点,必须叶节点,不能有子节点。(就是看看这是不是最后一排。)res[root]flag0w
二叉:1满二叉:在一棵二叉中,如果所有分支节点都存在左子树和右子树,并且所有叶子节点都在同一层上。2完全二叉:如果一棵具有N个结点的二叉的结构与满二叉的前N个结点的结构相同,称为完全二叉
判断一棵树是否完全二叉发布时间:2020032910:32:53来源:51CTO阅读:3571作者:朔月云影完全二叉:若一棵二叉具有具有n个节点,它的每个节点都与高度为k的满二叉编号为0~n
判断一棵二叉是否完全二叉一,完全二叉的三种节点完全二叉树有右树必有左树,,节点编号和满二叉一一对应1,度为2的节点有n个2,度为1的节点只能有1个3,度为0的节点有n个二,具体思路1,分两个
//判断一棵树是否完全二叉include<iostream>include<queue>include<asserth>usingnamespacestd;c
FileName:是否完全二叉pyclassNode(object):def__init__(self,valNone):selfvalvalselfleftNoneselfrightNonede