完全二叉树 订阅
一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。 [1] 展开全文
一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。 [1]
信息
外文名
Complete Binary Tree [1]
特    点
叶子结点只可能在最大的两层出现 [1]
应用学科
计算机科学 [1]
中文名
完全二叉树
实    质
效率很高的数据结构 [1]
完全二叉树定义
一棵深度为k且有 个结点的二叉树称为满二叉树。 [2]  根据二叉树的性质2, 满二叉树每一层的结点个数都达到了最大值, 即满二叉树的第i层上有 个结点 (i≥1) 。 [2]  如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。 [2]  从满二叉树和完全二叉树的定义可以看出, 满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树。 [2] 
收起全文
精华内容
下载资源
问答
  • 主要介绍了判断二叉树是否为完全二叉树的实例的相关资料,需要的朋友可以参考下
  • 在二叉树类binarytree中增加一个功能,判断是否为完全二叉树(使用自定义的队列类完成)
  • 完全二叉树总结点数与叶结点数关系分析班级软件一班姓名徐政钧学号130120010002完全二叉树定义 对一棵具有n个结点的二叉树按层序编号如果编号为i1in的结点与同样深度的满二叉树中编号为i的结点在二叉树中位值完全...
  • C++ 数据结构完全二叉树的判断 完全二叉树(Complete Binary ...完全二叉树的特点:完全二叉树的效率极高,堆是一种完全二叉树或者近似完全二叉树,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化
  • 针对一般的SVM方法不能有效地处理不平衡样本数据及现有的偏二叉树结构SVM分类器速度慢的这两个问题,提出了一种基于球结构的完全二叉树SVM多分类算法。该算法利用球结构的SVM考虑了每个类的分布情况,能有效地处理不...
  • 1、 定义链接存储的二叉树类。 2、 实验验证如下算法的正确性、各种功能及指标: 1) 创建一棵二叉树,并对其初始化; 2)先根、中根、后根遍历二叉树;...判别给定二叉树是否为完全二叉树。两个要求写了一份代码
  • 若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。 PHP代码实现(暂时实现添加节点、层次遍历节点,删除节点后续更新) &...
  • 完全二叉树

    2021-03-01 20:18:46
    一棵有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。 满二叉树是完全二叉树中...

    目录

    一,完全二叉树

    二,完全二叉树的性质

    三,OJ实战

    CSU 1946 A Rational Sequence

    CSU 1213 二叉树结点公共祖先

    力扣 222. 完全二叉树的节点个数


    一,完全二叉树

    一棵有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

    完全二叉树是Full Binary Tree中的一种特例,而Perfect Binary Tree又是完全二叉树中的一种特例。

    FBT、PBT https://blog.csdn.net/nameofcsdn/article/details/114559547

     

    二,完全二叉树的性质

    除根节点外,节点n的父节点是节点n/2

     

    三,OJ实战

    CSU 1946 A Rational Sequence

    Description
    An infinite full binary tree labeled by positive rational numbers is defined by:

    The label of the root is 1/1.
    The left child of label p/q is p/(p+q).
    The right child of label p/q is (p+q)/q.
    The top of the tree is shown in the following figure:

    A rational sequence is defined by doing a level order (breadth first) traversal of the tree (indicated by the light dashed line). So that:


    Write a program to compute the nth element of the sequence, F(n). Does this problem sound familiar? Well it should! But we changed it a little!
    Input
    The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set should be processed identically and independently.
    Each data set consists of a single line of input. It contains the data set number, K, and the index, N, of the sequence element to compute (1 <= N <= 2147483647).

    Output
    For each data set there is a single line of output. It contains the data set number, K, followed by a single space which is then followed by the numerator of the fraction, followed immediately by a forward slash (‘/’) followed immediately by the denominator of the fraction. Inputs will be chosen so neither the numerator nor the denominator will overflow an 32-bit unsigned integer.

    Sample Input
    4
    1 1
    2 4
    3 11
    4 1431655765
    Sample Output
    1 1/1
    2 1/3
    3 5/2
    4 2178309/1346269


    这是完全二叉树,所以可以直接找到每个节点的父亲是谁,递归即可解决本题。

    代码:
     

    #include<iostream>
    using namespace std;
     
    int a, b;
     
    void f(int n)
    {
    	if (n == 1)
    	{
    		a = 1, b = 1;
    		return;
    	}
    	f(n / 2);
    	if (n % 2)a += b;
    	else b += a;
    }
    int main()
    {
    	int p, n;
    	cin >> p;
    	while (p--)
    	{
    		cin >> n;
    		cout << n<<' ';
    		cin >> n;
    		f(n);
    		cout << a << '/' << b << endl;
    	}
    	return 0;
    }

     

    CSU 1213 二叉树结点公共祖先

    题目:

    Description

    一个顺序存储的完全二叉树:

                 1

              /     \

            2         3

          /   \     /    \

        4       5  6      7

        ...

    任意给定两结点的编号,求两结点最近的公共祖先。

    Input

    每组数据一行,为空格隔开的两个数i和j,皆为32位有符号正整数

    Output

    每组数据对应一行,为编号为i和j的结点的最近公共祖先的编号

    Sample Input

    4 5
    4 7
    Sample Output

    2
    1

    这是完全二叉树,代码:
     

    #include<iostream>
    using namespace std;
     
    int main()
    {
        int a,b;
        while(cin>>a>>b)
        {
            while(a!=b)
            {
                if(a>b)a/=2;
                else b/=2;
            }
    	cout<<a<<endl;
        }
        return 0;
    }

    力扣 222. 完全二叉树的节点个数

    题目:

    给出一个完全二叉树,求出该树的节点个数。

    说明:

    完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

    示例:

    输入: 
        1
       / \
      2   3
     / \  /
    4  5 6

    输出: 6

     

    代码:

    class Solution {
    public:
    	int countNodes(TreeNode* root) {
    		if (!root)return 0;
    		return countNodes(root->left) + countNodes(root->right) + 1;
    	}
    };

     

    展开全文
  • 里面是关于完全二叉树的判定方法,有两种方法,一种是用队列,另外一种是联想到堆排序算法,堆也是一种完全二叉树,也是一种简单算法,其实两者本质区别不大,只是实现方式略有区别。
  • 采用线性表的形式存放一颗完全二叉树,实现二叉树的创建,输出二叉树的叶子结点,实现二叉树的层次遍历。
  • 主要介绍了Java完全二叉树的创建与四种遍历方法,结合实例形式分析了完全二叉树的概念、定义及遍历操作相关实现技巧,并对比分析了满二叉树与完全二叉树的区别,需要的朋友可以参考下
  • 编写算法判别给定二叉树是否为完全二叉树,用递归实现
  • 完全二叉树的种类

    2012-12-01 12:50:40
    构造n个(2)叶结点的的完全二叉树(完全二叉树意味着每个分支结点都有2个儿子结点),有多少种构造方法? 注意:不改变n个结点的相对顺序,左右儿子不调换. 例如: 4个叶子节点A1,A2,A3,A4,可构造出如下完全二叉树,共5种。...
  • PAGE PAGE 13 安徽省巢湖学院计算机与信息工程学院 课程设计报告 课程名称 数据结构 课题名称 完全二叉树操作演示 专业班级 计算机科学与技术专升本1班 学 号 140110161401104014011019 姓 名 李鹏 王帅 李泳波 联系...
  •  3.(答案:B)假设该完全二叉树的层数为K,则该完全二叉树的前K-1层的结点总数为2K-1-1,若该完全二叉树是满二叉树,则该满二叉树的结点总数为2K-1,所以深度为K的完全二叉树的结点总数范围为:2K-1-1 。...

    树的概念及结构

    树的概念

     树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成的一个具有层次关系的集合。把它叫做“树”,是因为它看起来像一颗倒挂的树,也就是说它是根朝上,而叶朝下的。
    在这里插入图片描述
    树的特点:
     有一个特殊的结点,称为根结点,根结点没有前驱结点。
     除根结点外,其余结点被分成M(M>0)互不相交的集合T1,T2…Tm,其中每一个集合Ti(1<=i<=m)又是一颗结构与树类似的子树。
     每棵子树的根结点有且仅有一个前驱,可以有0个或多个后继。
     因此,树是递归定义的。

    树中的专有名词

    结点的度:一个结点含有的子树的个数称为该结点的度。
    叶结点(终端结点):度为0的结点称为叶结点。
    非终端结点(分支结点):度不为0的结点。
    父结点(双亲结点):若一个结点含有子结点,则这个结点称为其子结点的父结点。
    子结点(孩子结点):一个结点含有的子树的根结点称为该结点的子结点。
    兄弟结点:具有相同父结点的结点互称为兄弟结点。
    树的度:一棵树中,最大的结点的度称为树的度。
    结点的层次:从根开始定义起,根为第一层,根的子结点为第二层,以此类推。
    树的高度(树的深度):树中结点的最大层次。
    堂兄弟结点:双亲在同一层的结点互称为堂兄弟结点。
    结点的祖先:从根到该结点所经分支上的所有结点。
    子孙:以某结点为根的子树中任一结点都称为该结点的子孙。
    森林:由m(m>0)棵互不相交的树组成的集合称为森林。
    在这里插入图片描述

    树的表示

     树结构相对于线性表就比较复杂了,要存储和表示起来就比较麻烦了,实际中树有很多种表示方法。如:双亲表示法、孩子表示法、孩子兄弟表示法等等。其中最常用的是孩子兄弟表示法
     孩子兄弟表示法中,所定义的结点类型大致是这样的:

    typedef int DataType
    
    struct Node
    {
    	struct Node* firstChild;   //第一个孩子结点
    	struct Node* nextBrother;  //指向下一个兄弟结点
    	DataType data;             //结点中的数据域
    };
    

    对于任意树,我们都可以用孩子兄弟法访问到树中的每一个结点:
    在这里插入图片描述

    树在实际中的运用(表示文件系统的目录树结构)

    在这里插入图片描述

    二叉树的概念及其重要性质

    二叉树的概念

     二叉树是n个结点的有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。当集合为空时,称该二叉树为空二叉树。

    二叉树的特点:
     每个结点最多有两个棵子树,即二叉树不存在度大于2的结点。
     二叉树的子树有左右之分,其子树的次序不能颠倒。

    自然界中的二叉树

    在这里插入图片描述

    数据结构中的二叉树

    在这里插入图片描述

    特殊的二叉树

    满二叉树:一个二叉树,如果每一层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为k,且结点总数是2k-1,则它就是满二叉树。
    完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至N的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
    在这里插入图片描述
    总结:
    满二叉树:若树的深度为K,那么它的每一层的结点数必须都是满的。
    完全二叉树:若数的深度为K,那么它的前K-1层的结点数必须都是满的,第K层的结点数可以不是满的但是从左到右必须是连续的。

    二叉树的性质(重要!!!)

    性质一:若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有2i-1个结点。
    性质二:若规定根结点的层数为1,则深度为h的二叉树的最大结点数为2h-1个。
    性质三:对任何一棵二叉树,如果度为0的叶结点个数为n0,度为2的分支结点个数为n2,则有n0 = n2+1。
    性质四:若规定根结点的层数为1,则具有N个结点的满二叉树的深度h = log2(N+1)。
    性质五:对于具有N个结点的完全二叉树,如果按照从上至下、从左至右的数组顺序对所有结点从0开始编号,则对于序号为i的结点:
     若 i > 0,则该结点的父结点序号为:( i - 1) / 2;若 i = 0,则无父结点。
     若2i + 1 < N,则该结点的左孩子序号为:2i + 1;若2i + 1 >= N,则无左孩子。
     若2i + 2 < N,则该结点的右孩子序号为:2i + 2;若2i + 2 >= N,则无右孩子。
    在这里插入图片描述
    练习一下:
     1.某二叉树共有399个结点,其中199个度为2的结点,则该二叉树中的叶子结点数为( )。
     A.不存在这样的二叉树
     B.200
     C.198
     D.199

     2.在具有2n个结点的完全二叉树中叶子结点个数为( )。
     A.n
     B.n+1
     C.n-1
     D.n/2

     3.一棵完全二叉树的结点数为531,那么这棵树的高度为( )。
     A.11
     B.10
     C.8
     D.12

     4.一个具有767个结点的完全二叉树,其叶子结点个数为( )。
     A.383
     B.384
     C.385
     D.386

    解析:
     1.(答案:B)根据性质三,叶子结点(度为0)的个数200个,由于199+200 = 399(该二叉树的总结点数),所以该二叉树的叶子结点数为200。

     2.(答案:A)根据性质三,度为0的结点数和度为2的结点数之和应为奇数,因为该完全二叉树的结点总数为2n(偶数),所以二叉树中必然存在一个度为1的结点。于是可以推出:度为0的结点和度为2的结点总共有2n-1个。性质三:对任何一棵二叉树,度为0的叶结点个数比度为2的分支结点个数多1,所以该二叉树度为1的结点个数为n-1,度为0的结点数(即叶结点数)为n。
    注意理解:任何一棵完全二叉树中度为1的结点要么有1个,要么就没有度为1的结点。因为完全二叉树的最后一层的结点必须是从左到右连续的,而位于最后一层之前的层数的结点的度均为2。
    在这里插入图片描述
     3.(答案:B)假设该完全二叉树的层数为K,则该完全二叉树的前K-1层的结点总数为2K-1-1,若该完全二叉树是满二叉树,则该满二叉树的结点总数为2K-1,所以深度为K的完全二叉树的结点总数范围为:2K-1-1 < N <= 2K-1。因为29 < 531 <= 210,所以该完全二叉树的高度为10。
    注意记忆:210 = 1024。

     4.(答案:B)该题与第2题的道理是一样的,因为该树的结点总数为767(奇数),所以该树中不存在度为1的结点,度为2的结点个数为383,度为0的结点个数为384,即叶子结点个数为384。

    二叉树的存储结构

    顺序结构

     顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实生活中只有堆(一种二叉树)才会使用数组来存储。二叉树的顺序存储在物理上是一个数组,在逻辑上是一棵二叉树
    在这里插入图片描述

    链式结构

     二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素之间的逻辑关系。通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来存储该结点左孩子和右孩子所在的结点的地址。
     链式结构又分为二叉链和三叉链,之后我们会用二叉链来实现二叉树的链式存储结构,三叉链运用于更高阶的数据结构,例如红黑树。
    在这里插入图片描述

    展开全文
  • 数据结构:满二叉树,完全二叉树,非完全二叉树 的区别前言一、满二叉树二、完全二叉树三、非完全二叉树总结 前言 记录下满二叉树,完全二叉树,非完全二叉树的区别 一、满二叉树 如上图所示,这就是一个满二叉树...

    数据结构:满二叉树,完全二叉树,非完全二叉树 的区别


    前言

    记录下满二叉树,完全二叉树,非完全二叉树的区别


    一、满二叉树

    在这里插入图片描述
    如上图所示,这就是一个满二叉树的示例图,从字面上也很好理解,叶子节点外,所有节点都有两个子节点。

    二、完全二叉树

    在这里插入图片描述
    完全二叉树就和名字有点不太一样了,除最后一层节点外,其他层节点都必须要有两个子节点,并且最后一层节点都要左排列。
    要满足两个条件:

    1.除最后一层节点外,其他层节点都必须要有两个子节点
    2.最后一层节点都要左排列

    像下面这两种都不能称为完全二叉树
    中间层的节点没有满足两个子节点
    在这里插入图片描述
    最后一层节点没有左排列
    在这里插入图片描述

    三、非完全二叉树

    其实上面的没有满足完全二叉树的例子就可以称为非完全二叉树。


    总结

    欢迎大佬多多来给萌新指正,欢迎大家来共同探讨。
    如果各位看官觉得文章有点点帮助,跪求各位给点个“一键三连”,谢啦~

    声明一下:本博文章若非特殊注明皆为原创原文链接
    https://blog.csdn.net/Wrinkle2017/article/details/118728106
    ————————————————————————————————

    版权声明

    版权声明:本博客为非营利性个人原创
    所刊登的所有作品的著作权均为本人所拥有
    本人保留所有法定权利,违者必究!
    对于需要复制、转载、链接和传播博客文章或内容的
    请及时和本博主进行联系
    对于经本博主明确授权和许可使用文章及内容的
    使用时请注明文章或内容出处并注明网址
    转载请附上原文出处链接及本声明

    展开全文
  • Python实现完全二叉树

    2021-01-20 02:41:20
    Python实现完全二叉树 一、二叉树的存储结构 对于线性表、栈、队列等数据结构,数据都可以使用物理有序和逻辑有序的方式存储,二叉树也可以使用这两种方式存储。 物理有序将数据存储在连续的内存空间中,例如存储在...
  • 1.建立完全二叉树 2.先序非递归遍历二叉树函数 & 先序递归遍历二叉树验证 3.中序非递归遍历二叉树函数 & 中序递归遍历二叉树验证 4.后序非递归遍历二叉树函数 & 后序递归遍历二叉树验证
  • 编写算法判别给定二叉树是否为完全二叉树
  • 二叉树分类很多,其中满二叉树和完全二叉树比较特殊,因为这两种二叉树效率很高,这里记录几条相关性质。 首先是满二叉树:从形象上来说满二叉树是一个绝对的三角形,也就是说它的最后一层全部是叶子节点,其余各层...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 111,333
精华内容 44,533
关键字:

完全二叉树