精华内容
下载资源
问答
  • 二叉树分类很多,其中满二叉树和完全二叉树比较特殊,因为这两种二叉树效率很高,这里记录几条相关性质。 首先是满二叉树:从形象上来说满二叉树是一个绝对的三角形,也就是说它的最后一层全部是叶子节点,其余各层...

    二叉树分类很多,其中满二叉树和完全二叉树比较特殊,因为这两种二叉树效率很高,这里记录几条相关性质。

    首先是满二叉树:从形象上来说满二叉树是一个绝对的三角形,也就是说它的最后一层全部是叶子节点,其余各层全部是非叶子节点,如果用数学公式表示那么其节点数n=2^k-1(2的k次方减一)其中k表示深度,也就是层数。也就是说满二叉树的节点数是一系列固定的数,比如说,1,3,7,15…如果节点数不是这个序列中的数,那么他肯定不是满二叉树,当然了,反之,是不成立的。

    由于它的节点数和形状固定,我们可以发现很多其数学公式性质。

    1. 首先是节点数和深度的关系 n=2^k-1

    2. 第二是第i层上的节点数为2^(i-1)

    3. 第三是给所有的节点编号(从1号开始而不是从零号开始)那对于每一个编号为i的节点我们可以根据i的大小,判断出他是左节点还是右节点,父节点是谁,子节点是谁。比如我们给一个编号13的节点,那么他是基数所以他是右节点,因为节点的左右变化和数据的基偶性是同步变化的。他的父节点是13/2=6(是从1好开始的)他的左子节点是132=26右子节点是132+1=27同理还可以求他的兄弟节点,父节点的父节点,

    总而言这在满二叉树中只要有了一个节点的编号那么他在整个二叉树中的位置就确定了,正是由于这个原因,我们更倾向于使用顺序结构而不是链式结构来存储满二叉树

    然而由于满二叉树的节点数必须是一个确定的数,而非任意数,他的使用受到了某些限制,为了打破另一个限制,我们定义一种特殊的满二叉树——完全二叉树。

    完全二叉树的节点个数是任意的,从形式上来说他是一个可能有缺失的三角形,但所缺部分肯定是右下角的某个连续部分。这样说不玩整,更准确来说,我们可以说他和满二叉树的区别是,他的最后一行可能不是完整的,但绝对是右方的连续部分缺失。可能听起来有点乱,用数学公式讲,对于K层的完全二叉树,其节点数的范围是:2的(k-1)次方-1< N <= 2的k次方-1;

    一棵深度为k且有2的k次方减1个结点的二叉树是满二叉树。
    深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树。

    在这里插入图片描述
    满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树

    展开全文
  • 完全二叉树和满二叉树区别

    万次阅读 2018-07-18 15:43:15
    依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适 完全二叉树是效率很高的数据结构,堆是一种完全二叉树或者近似完全二叉树,所以效率极高,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆...

    堆的话一般都是用完全二叉树来实现的,比如大堆和小堆。一个树节点的度数就是这个树节点有多少子节点,和树的深度意义不同。

    依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适

    完全二叉树是效率很高的数据结构,是一种完全二叉树或者近似完全二叉树,所以效率极高,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化,几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全二叉树。

    完全二叉树(Complete Binary Tree)

    若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

    完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

    一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树。

          完全二叉树特点编辑

    叶子结点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1;

    出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下:

    var tree:array[1..n]of longint;{n:integer;n>=1}

    对于tree[i]有如下特点:

    (1)若i为奇数且i>1,那么tree的左兄弟为tree[i-1];

    (2)若i为偶数且i<n,那么tree的右兄弟为tree[i+1];

    (3)若i>1,tree的双亲为tree[i div 2];

    (4)若2*i<=n,那么tree的左孩子为tree[2*i];若2*i+1<=n,那么tree的右孩子为tree[2*i+1];

    (5)若i>n div 2,那么tree[i]为叶子结点(对应于(3));

    (6)若i<(n-1) div 2.那么tree[i]必有两个孩子(对应于(4))。

    (7)满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。

    完全二叉树第i层至多有2^(i-1)个节点,共i层的完全二叉树最多有2^i-1个节点。

    如果一棵具有n个结点的深度为k的二叉树,它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应,这棵二叉树称为完全二叉树。

    可以根据公式进行推导,假设n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数,由二叉树的性质可知:n0=n2+1,则n= n0+n1+n2(其中n为完全二叉树的结点总数),由上述公式把n2消去得:n= 2n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0=(n+1)/2或n0=n/2。

    总结起来,就是 n0=[n/2],其中[]表示上取整。可根据完全二叉树的结点总数计算出叶子结点数。

     

     

     

    其实满二叉树是完全二叉树的特例,因为满二叉树已经满了,而完全并不代表满。所以形态你也应该想象出来了吧,满指的是出了叶子节点外每个节点都有两个孩子,而完全的含义则是最后一层没有满,并没有满。

     

    下面贴定义:

    满二叉树(Full Binary Tree):

     

      

     

      除最后一层无任何子节点外,每一层上的所有结点都有两个子结点(最后一层上的无子结点的结点为叶子结点)。也可以这样理解,除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.

     

     

    一颗树深度为h,最大层数为k,深度与最大层数相同,k=h;

      它的叶子数是: 2^h  第k层的结点数是: 2^(k-1)  总结点数是: 2^k-1 (2的k次方减一)  总节点数一定是奇数。

     

     

    完全二叉树(Complete Binary Tree)

      若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。  完全二叉树是由满二叉树而引出来的。对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。  若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树。

      

     

     

    霍夫曼树:每个节点要吗没有子节点,要么有两个子节点

     

     

    https://blog.csdn.net/mawming/article/details/46471429

    展开全文
  • 首先说树和二叉树: 一、性质不同 树:树是一种bai数据结du构。 二叉树二叉树是每个结点最多有两个zhi子树的一种树结构dao。 二、结点不同 树:树的每个结点有零...满二叉树和完全二叉树区别: 完全二叉zhi树

    首先说树和二叉树:

    一、性质不同

    树:树是一种数据结构可以有多个子树。

    二叉树:二叉树是每个结点最多有两个子树的一种树结构。

    二、结点不同
    树:树的每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点。

    二叉树:每个结点最多有两个子树。

    三、种类不同

    树:树的种类包括无序树、有序树、二叉树和霍夫曼树等。

    二叉树:二叉树的种类包括完全二叉树、满二叉树和平衡二叉树。

    完美/满二叉树和完全二叉树:

    满二叉树和完全二叉树的区别:

    完全二叉zhi树是由满二叉树而引出来的。对于深度为K的,有n个结点的dao二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

    对于满二叉树,除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树。而完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

    1.满二叉树

    定义:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。

    2.完全二叉树

    定义:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

    满二叉树就是每个节点都有两个子节点,每层都是满满的,而完美二叉树就是不需要每层都是慢慢的,只要满足每个节点都有两个子节点即可。完全二叉树就是除了最底层以外,其它层都是节点下有两个子节点,并且最下层的子节点集中在左侧。

    展开全文
  • 文章目录完全二叉树堆 参考:https://blog.csdn.net/sodacoco/article/details/83478803 https://www.cnblogs.com/zhoanghua/p/9288899.html 完全二叉树 若堆的深度【层数】为h,除了最后一层,其上各层 (1~h-1) 的...


    参考:https://blog.csdn.net/sodacoco/article/details/83478803
    https://www.cnblogs.com/zhoanghua/p/9288899.html
    https://www.jianshu.com/p/ac95b5a7de8b

    完全二叉树

    若堆的深度【层数】为h,除了最后一层,其上各层 (1~h-1) 的结点数都达到最大个数,并且最后一层所有的结点都连续集中在最左边,这就是完全二叉树。
    在这里插入图片描述

    堆是利用完全二叉树的结构来维护的一组数据。它的实现如下:
    在这里插入图片描述

    满二叉树

    full binary tree 满二叉树:二叉树除了叶结点外所有节点都有两个子节点。
    对于满二叉树而言,叶子的个数等于内部结点(非叶结点)+1,写作 L = l + 1
    在这里插入图片描述
    在这里插入图片描述

    完全二叉树与满二叉树的区别

    满二叉树分为:full binary tree 和 perfect binary tree
    full binary tree
    在这里插入图片描述

    perfect binary tree
    在这里插入图片描述

    满二叉树不一定是完全二叉树

    下面这个二叉树只是full binary tree,所以它不是完全二叉树。
    在这里插入图片描述

    完全二叉树也不一定是满二叉树

    在这里插入图片描述

    既是满二叉树也是完全二叉树的树

    只有 perfect binary tree才既是满二叉树也是完全二叉树
    在这里插入图片描述

    展开全文
  • 完全二叉树与满二叉树区别

    千次阅读 2019-10-27 13:01:36
    假设二叉树共K层; 满二叉树:结点数总个数=2^K-1; 完全二叉树:顺序生成节点。... 非完全二叉树:如上图,产生6节点位置,并非顺序对应同层生成的满二叉树形式。若为完全二叉树,则应建立节点于3节点的左侧。 ...
  • 主要介绍了判断二叉树是否为完全二叉树的实例的相关资料,需要的朋友可以参考下
  • 数据结构:满二叉树完全二叉树,非完全二叉树区别前言一、满二叉树二、完全二叉树三、非完全二叉树总结 前言 记录下满二叉树完全二叉树,非完全二叉树区别 一、满二叉树 如上图所示,这就是一个满二叉树...
  • 树、二叉树(完全二叉树满二叉树)概念图解

    万次阅读 多人点赞 2019-04-26 10:08:13
    完全二叉树是由满二叉树而引出来的,若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树),第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。...
  • 树形结构 这是我们最熟悉的线性...可以初步看出,二叉树就是每个节点要么没有分枝,要么就是分两根枝,而多叉树的每个节点可以有任意的分枝。 生活中的树形结构 文件夹的管理就是我们生活中最常见的树形结构 ...
  • 二叉树类binarytree中增加一个功能,判断是否为完全二叉树(使用自定义的队列类完成)
  • 完全二叉树满二叉树区别

    万次阅读 多人点赞 2019-02-21 21:16:43
    满二叉树 满二叉树:指深度为k且有2^k-1个结点...完全二叉树:当二叉树的深度为h时,它的h层节点必须都是连续靠左并不可隔开的(满二叉树也符合),并且1~h-1层的结点数都达到最大个数(即1~h-1层为一个满二叉树)。 ...
  • 1、完全二叉树满二叉树区别满二叉树:深度为k且有2^k-1个结点的二叉树称为满二叉树完全二叉树:设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续...
  • 满二叉树 完全二叉树
  • 度:指的是一个节点拥有子节点的个数。如二叉树的节点的最大度为2。 深度:数的层数,根节点为第一层,依次类推。 叶子节点:度为0的节点,即没有子节点的...满二叉树:除了叶结点外每一个结点都有左右子叶且叶结点都
  •  3.(答案:B)假设该完全二叉树的层数为K,则该完全二叉树的前K-1层的结点总数为2K-1-1,若该完全二叉树满二叉树,则该满二叉树的结点总数为2K-1,所以深度为K的完全二叉树的结点总数范围为:2K-1-1 。...
  • 这里写目录标题树二叉树的原理精讲二叉搜索树插入节点二叉搜索树删除节点二叉树的遍历 树 树状图是一种数据结构,它是由 n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因 为它看起来像一棵...
  • 完全二叉树满二叉树区别(有图)

    万次阅读 多人点赞 2015-07-08 08:45:32
    先看图: 完全二叉树:设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数, ...第 h 层所有的结点都连续集中在最左边 ...满二叉树:深度为k且有2^k-1个结点的二叉树称为满二叉树
  • 判断完全二叉树和满二叉树

    千次阅读 2018-08-25 16:28:50
    (一)判断完全二叉树 特点一: 只允许最后一层有空缺结点且空缺在右边,即叶子结点只能在层次最大的两层上出现;  特点二: 对任一结点,如果其右子树的深度为j,则其左子树的深度必为j或j+1 即度为1的点只有1...
  • 二叉树二叉树由节点(node)和边组成。节点分为根节点、父节点、子节点。 二叉树是每个结点最多有两个子树的树结构。
  • 注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树完全二叉树的特点:完全二叉树的效率极高,堆是一种完全二叉树或者近似完全二叉树,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能...
  • 二叉树定义: 二叉树是一种树型结构,它的特点是每个结点至多只有两颗子树(二叉树有左右之分次序不能随意)括号这句话的意思就是说二叉树...一颗深度为k且有2^k - 1 个结点的二叉树成为满二叉树 即每一层都是满满的...
  • 完全二叉树 满二叉树

    2020-05-03 23:59:36
    完全二叉树 满二叉树 1.定义 ①满二叉树:除最后一层无任何节点外,每一层上的所有节点都有两个子结点的二叉树。 另外的定义:一个二叉树,如果每一层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 485,444
精华内容 194,177
关键字:

完全二叉树和满二叉树的区别