【C++】满二叉树、完全二叉树等概念解释

news/2024/7/8 6:55:18

二叉树中的判断有以下几种:

是否完全二叉树、是否满二叉树、是否为BST树、是否为平衡二叉树、是否为对称二叉树、完美二叉树

满二叉树:

        除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。

上述所示图除最外一层节点之外,每个节点都有两个子节点,所以上述两图都是满二叉树!!!

完全二叉树:

完全二叉树是满二叉树的一直特例,怎么个特例法呢?

 上图为啥有些是完全二叉树,有些又不是完全二叉树呢?

完全二叉树定义:完全二叉树(Complete Binary Tree):若设二叉树的高度为h。除第h层外,其它各层(0~h-1)的结点数都达到最大个数,第h层从右向左连续缺若干结点,这就是完全二叉树
 

上述所说从右向左缺若干节点,也就是说在h层的时候,如果有节点都在左半边,而缺的都是右半边的节点,这就是完全二叉树!

BST树(二叉搜索树)

        

 这玩意就是说,右孩子的节点比双亲结点大,左孩子的节点比双亲节点小,从根节点走出来之后,左子树和右子树都按照这个大小再次进行排序!!!

平衡二叉搜索树(AVL树)

 两子树高度相差不超过1的搜索二叉树即为平衡搜索二叉树!!!

对称二叉树

如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

最后再了解一下完美二叉树 

 除了最外层叶子结点之外的每一个结点都有两个孩子,每一层(当然包含最后一层)都被完全填充。

“认真写好一篇博客,写完之后的收获是非常大的”

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.pgtn.cn/news/15574.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

相关文章

【C++】多线程(链式、循环队列)实现生产者消费者模式

生产者消费者模式: 生产者消费者问题(英语:Producer-consumer problem),也称有限缓冲问题(英语:Bounded-buffer problem),是一个多线程同步问题的经典案例。该问题描述了…

添加引用方式抛出和捕获干净的WebService异常

转载:http://www.cnblogs.com/ahdung/p/3953431.html 说明:【干净】指的是客户端在捕获WebService(下称WS)抛出的异常时,得到的ex.Message就是WS方法中抛出的异常消息,不含任何“杂质”。 前提:…

基数排序(桶排序)

基数排序又叫桶排序: 先按照个位数排序,第一次排序好之后;再次按照十位数进行排序,第二次排序好之后;第三次对百位进行排序.................. 实现原理图:拿出一些个类似“桶”的东西 将分别按照个位&am…

如何用两个栈实现一个队列?

先看分析 来看代码,因为代码量巨大,其中包括两个头文件,两个实现函数 , 这块就写一个两个栈实现按一个队列的头文件以及函数名,填补代码不难的,有需要的话,我在评论区发出来: 这部分…

堆排序(超详细的原理图以及代码注释)

在了解学习堆排序之前,我们必须清楚以下的概念: 上述概念搞清楚之后,来看下面的原理图: 然后原理部分就讲完了 下面来看如何由子节点下标推出父节点和父节点下标推出子节点下标 下面这个原理图来展现一下为什么在调整大顶堆的时候…

【C++】模拟实现多线程中的信号量

信号量: 二元信号量和一般信号量 二元信号量是最简单的一种锁,适合那种被唯一线程访问的资源,而一般信号量就允许多线程并发的访问资源。 二元信号量类似于互斥量,但是有一点不同的是,互斥量只能被上锁的那个线程释…

senfile函数实例的运行过程截图

//要传输的文件内容如下所示: 启动服务器,等待客户端连接(在同一台主机上模拟的) 客户端远程登录,这里是在本地登录 这个要注意一点就是远程登陆的时候一定要带上端口号不然连接失败!!转载于:ht…

【C++】单例模式(懒汉、饿汉)

1.什么是单例模式? 顾名思义,单例模式就是在这个单例类确保只有一个对象被创建。也就是说这个类只能实例化一个对象。 特征:1.单例类最多只能有一个实例; 2.单例类必须自己创建自己唯一的实例; 3.单例类必须给所有其…