C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

链接：C语言数据结构系列之树的概念结构和常见表示方法

0x00 概念

定义：二叉树既然叫二叉树，顾名思义即度最大为2的树称为二叉树。 它的度可以为 1 也可以为 0，但是度最大为 2 。

一颗二叉树是节点的一个有限集合，该集合：

① 由一个根节点加上两颗被称为左子树和右子树的二叉树组成

② 或者为空

观察上图我们可以得出如下结论：

① 二叉树不存在度大于 2 的节点，换言之二叉树最多也只能有两个孩子。

② 二叉树的子树有左右之分，分别为左孩子和右孩子。次序不可颠倒，因此二叉树是有序树。

注意：对于任意的二叉树都是由以下几种情况复合而成的：

0x01 满二叉树

定义：一个二叉树，如果每一层的节点数都达到了最大值（均为2），则这个二叉树就可以被称作为 "满二叉树" 。

换言之，如果一个二叉树的层数为，且节点总数是 ，则他就是一个满二叉树。

计算公式：

① 已知层数求总数：

② 已知总数求层数： 

十亿个节点，满二叉树是多少层？

 ≈ 10亿多

0x02 完全二叉树

定义：对于深度为 的，有个结点的二叉树，当且仅当其每一个结点都与深度为的满二叉树中编号从 1 至的结点一一对应时称之为完全二叉树。

前 层是满的，最后一层不满，但是最后一层从左到右是连续的。

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。所以，满二叉树是一种特殊的完全二叉树（每一层节点均为2）。

常识：

① 完全二叉树中，度为 1 的最多只有 1 个。

② 高度为  的完全二叉树节点范围是   

0x03 二叉树的性质

四点规则：

① 若规定根节点的层数为 1 ，则一颗非空二叉树的第  层上最多有  个节点。

② 若规定根节点的层数为 1 ，则深度为  的二叉树最大节点数是  .

③ 对任何一颗二叉树，如果度为 0 其叶子结点个数为  ，度为 2 的分支节点个数为  ，则有   。换言之，度为 0 的永远比度为 2 的多一个叶子结点。

④ 若规定根节点的层数为 1 ， 具有  个节点的满二叉树的深度     （log是以2为底，n+1的对数）。

对于有  个节点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号，则对于序号为  的节点有：

（非完全二叉树，也可以用数组存放，但会浪费很多空间）

假设  是父节点在数组中的下标，此公式仅适用于完全二叉树：

① 求左孩子： 

② 求右孩子：

③ 求父亲（假设不关注是左孩子还是右孩子）： 

④  判断是否有左孩子：

⑤  判断是否由右孩子：

赞 (0)

相关推荐

  • C语言中二叉树的后序遍历详解

    C语言中二叉树的后序遍历详解

    目录 一.二叉树的后序遍历.(递归) 二.二叉树的后序遍历(迭代) 总结 首先我们从两个方面讲解二叉树的后序遍历(递归+迭代) 一.二叉树的后序遍历.(递归) 思想: 首先我们从二叉树的根节点开始先遍历其左孩子,①接着同样继续遍历其左孩子的左孩子,直到某个左孩子节点的左孩子为NULL时,②开始遍历其右孩子,如果其为NULL则访问该节点的值域,并返回其双亲节点重复第二步的操作,如果其不为NULL则以该节点为根节点重复第一步的操作.直到访问完所有节点时结束递归. 代码: void BTreePost

  • C语言数据结构系列篇二叉树的遍历

    C语言数据结构系列篇二叉树的遍历

    目录 前言: Ⅰ. 定义二叉树 0x00二叉树的概念(回顾) 0x00定义二叉树 0x01 手动创建二叉树 Ⅱ. 二叉树的遍历 0x00关于遍历 0x01二叉树前序遍历 0x02二叉树中序遍历 0x03二叉树后序遍历 0x04层序遍历 前言: 学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习.等二叉树结构了解的差不多后,后期我们会带大家研究二叉树地真正的创建方式.

  • C语言数据结构之二叉链表创建二叉树

    目录 一.思想(先序思想创建) 二.创建二叉树 (1)传一级参数方法 (2)传二级参数方法 一.思想(先序思想创建) 第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树,直到递归创建到的节点下不继续创建左子树,也就是当下递归到的节点下的左子树指向NULL,结束本次左子树递归,返回这个节点的上一个节点,开始创建右子树,然后又开始以当下这个节点,继续递归创建左子树,左子树递归创建完,就递归创建右子树,直到递归结束返回到上一级指针节点(也就是根节点下),此时根节点左边子树创建完毕,开始创建右

  • C语言二叉树的遍历示例介绍

    C语言二叉树的遍历示例介绍

    在本算法中先利用先序遍历创建了树,利用了递归的算法使得算法简单,操作容易,本来无printf("%c的左/右子树:", ch);的语句,但由于计算机需要输入空格字符来判断左右子树,为了减少人为输入的失误,特地加入这条语句,以此保证准确率. #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW 3 typedef int Status; typedef

  • C语言数据结构二叉树先序、中序、后序及层次四种遍历

    C语言数据结构二叉树先序、中序、后序及层次四种遍历

    目录 一.图示展示 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 (5)口诀 二.代码展示 一.图示展示 (1)先序遍历 先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解 (2)中序遍历 中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最

  • C语言实现二叉树层次遍历介绍

    目录 什么是层次遍历? 那我们如何来实现这个算法呢? 主体代码: 总结 什么是层次遍历? 对于一颗二叉树来说,从根节点开始,按从上到下.从左到右的顺序访问每一个结点. 注:每一个结点有且访问一次. 那我们如何来实现这个算法呢? 实现原理: 对于二叉树来说,它是一个递归的定义,我们要实现层次遍历必然要满足从上到下.从左到右这个要求,从根结点出发,我们可以将所有意义上的根结点都存储在队列之中,那我们可以使用队列先进先出的特点来实现要求的遍历. 这里我们需要引用队列来实现. 主体代码: BiTree

  • C语言实现线索二叉树的前中后创建和遍历详解

    C语言实现线索二叉树的前中后创建和遍历详解

    目录 1.结构 1.1初始化tag 2.基本操作 2.1先序创建二叉树 2.2.先序线索化 2.2.1.先序遍历 2.3.中序线索化 2.3.1中序遍历 2.4.后序线索化 2.4.1后序遍历 总结 1.结构 #include<stdio.h> #include<stdlib.h> #define false 0 #define true 1 using namespace std; typedef struct BTnode{ int data; struct BTnode *l

  • 统计C语言二叉树中叶子结点个数

    树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的,下面我们就用简单小栗子来简单说明关于统计C语言二叉树中叶子结点个数的方法吧 简单小栗子: #include<stdio.h> #include<stdlib.h>   typedef char ElemType; typedef struct BTNode {     ElemType data;     struct B

  • C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

    C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

    链接:C语言数据结构系列之树的概念结构和常见表示方法 0x00 概念 定义:二叉树既然叫二叉树,顾名思义即度最大为2的树称为二叉树. 它的度可以为 1 也可以为 0,但是度最大为 2 . 一颗二叉树是节点的一个有限集合,该集合: ① 由一个根节点加上两颗被称为左子树和右子树的二叉树组成 ② 或者为空 观察上图我们可以得出如下结论: ① 二叉树不存在度大于 2 的节点,换言之二叉树最多也只能有两个孩子. ② 二叉树的子树有左右之分,分别为左孩子和右孩子.次序不可颠倒,因此二叉树是有序树. 注意:对

  • C语言数据结构系列队列篇

    C语言数据结构系列队列篇

    目录 一.队列(Queue) 0x00队列的概念 0x01队列的结构 二.队列的定义 0x00链式队列 0x02 接口函数 三.队列的实现 0x00队列初始化(QueueInit) 0x01销毁队列(QueueDestroy) 0x02判断队列是否为空(HeapIsEmpty) 0x03入队(QueuePush) 0x04出队(QueuePop) 0x05 返回队头数据(QueueFront) 0x06 返回队尾数据(QueueBack) 0x07 求队列大小(QueueSize) 0x08完整

  • Java中关于二叉树的概念以及搜索二叉树详解

    Java中关于二叉树的概念以及搜索二叉树详解

    目录 一.二叉树的概念 为什么要使用二叉树? 树是什么? 树的相关术语! 根节点 路径 父节点 子节点 叶节点 子树 访问 层(深度) 关键字 满二叉树 完全二叉树 二叉树的五大性质 二.搜索二叉树 插入 删除 hello, everyone. Long time no see. 本期文章,我们主要讲解一下二叉树的相关概念,顺便也把搜索二叉树(也叫二叉排序树)讲一下.我们直接进入正题吧!GitHub源码链接 一.二叉树的概念 为什么要使用二叉树? 为什么要用到树呢?因为它通常结合了另外两种数据结

  • C语言数据结构系列之树的概念结构和常见表示方法

    C语言数据结构系列之树的概念结构和常见表示方法

    0x00 树的概念 树是一种非线性的数据结构,它是由 n(n >= 0)个有限节点组成的一个具有层次关系的集合. 那么为什么叫 "树" 呢? 我们之所以把它成为 "树",是因为它很像我们现实生活中的树.只是它是倒过来的,根朝上叶子朝下. 0x01 树的结构 ① 有一个特殊的节点,成为根节点,根节点不存在前驱节点. ② 除根节点外,其余节点被分成 M(M>0) 个互不相交的集合 T1.T2.…….Tm,期中没一个集合 Ti(1 <= i <=

  • 树,二叉树(完全二叉树,满二叉树)概念图解

    树,二叉树(完全二叉树,满二叉树)概念图解

    目录 1.树的定义 2.树的概念 3.二叉树 4.二叉树遍历 5.满二叉树 6.完全二叉树 总结 1.树的定义 树是n个结点的有限集合,有且仅有一个根结点,其余结点可分为m个根结点的子树. 2.树的概念 结点的度:一个结点拥有子树的个数称为度.比如A的度为3,C的度为2,H的度为0.度为0的结点称为叶子节点(D,F,G,H).树的度是树中所有结点的度的最大值,此树的度为3. 树中结点的最大层次成为树的深度或高度.此树的深度为4. 父节点A的子结点B,C,D:B,C,D也是兄弟节点 树的集合称为森

  • 二叉树的概念案例详解

    二叉树的概念案例详解

    二叉树简介 关于树的介绍,请参考:https://blog.csdn.net/weixin_43790276/article/details/104033482 一.二叉树简介 二叉树是每个节点最多有两个子树的树结构,是一种特殊的树,如下图,就是一棵二叉树. 二叉树是由n(n>=0)个节点组成的数据集合.当 n=0 时,二叉树中没有节点,称为空二叉树.当 n=1 时,二叉树只有根节点一个节点.当 n>1 时,二叉树的每个节点都最多只能有两个子树,递归地构建成一棵完整的二叉树. 二叉树的两个子树

  • Python 二叉树的概念案例详解

    Python 二叉树的概念案例详解

    二叉树简介 关于树的介绍,请参考:https://www.jb51.net/article/222488.htm 一.二叉树简介 二叉树是每个节点最多有两个子树的树结构,是一种特殊的树,如下图,就是一棵二叉树. 二叉树是由n(n>=0)个节点组成的数据集合.当 n=0 时,二叉树中没有节点,称为空二叉树.当 n=1 时,二叉树只有根节点一个节点.当 n>1 时,二叉树的每个节点都最多只能有两个子树,递归地构建成一棵完整的二叉树. 二叉树的两个子树被称为左子树(left subtree)和右子树

  • C语言数据结构之二叉树详解

    C语言数据结构之二叉树详解

    目录 1. 树概念及结构 1.1树概念 1.2树的表示 2. 二叉树概念及结构 2.1概念 2.2数据结构中的二叉树 2.3特殊的二叉树 2.4二叉树的存储结构 2.5二叉树的性质 3. 二叉树顺序结构及概念 3.1二叉树的顺序结构 3.2堆的概念及结构 3.3堆的实现 4. 二叉树链式结构及实现 4.1二叉树链式结构的遍历 4.2二叉树的链式实现 1. 树概念及结构 1.1树概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵

  • C语言 超详细总结讲解二叉树的概念与使用

    C语言 超详细总结讲解二叉树的概念与使用

    目录 1.二叉树的概念及结构 2.二叉树链式结构的实现 1.二叉树的概念及结构 ①概念:一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成. ②二叉树的特点: 每个结点最多有两棵子树,即二叉树不存在度大于2的结点.(度最多为2) 二叉树的子树有左右之分,其子树的次序不能颠倒. ③现实中的二叉树: 当一名普通的人看到这样一颗树,可能会想:好标准的一棵树 当一个程序猿看到这样一棵树,可能会想:好像数据结构中的二叉树,并且还是颗满二叉树 ④数据结

随机推荐