完全二叉树 订阅
一棵深度为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] 
收起全文
精华内容
下载资源
问答
  • 数据结构 - 完全二叉树

    万次阅读 多人点赞 2019-02-18 10:45:16
    完全二叉树是一种效率很高的数据结构,堆就是一种完全二叉树,效率极高。像十分常用的排序算法、Dijkstra算法、Prim算法等等都要用堆才能优化;经常提到的二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net 

    完全二叉树是一种效率很高的数据结构,堆就是一种完全二叉树,效率极高。像十分常用的排序算法、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 object; {n:integer; n>=1}

    对于tree有如下特点:

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

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

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

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

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

    (6)若i<(n-1)/2,那么tree必有两个孩子(对应于(4));

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

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

     

    完全二叉树叶子结点数的算法

    可以根据公式进行推导,假设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,就可根据完全二叉树的结点总数计算出叶子结点数。

     

    完全二叉树的性质

    具有n个结点的完全二叉树的深度为floor(log2n)+1或ceil(log2(n+1))。
    证明:设所求完全二叉树的深度为k。

    由完全二叉树定义可得:
    深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树,一共有2^(k-1)-1个结点。
    由于完全二叉树深度为k,故第k层上还有若干个结点,因此该完全二叉树的结点个数:n>2^(k-1)-1。
    由二叉树的性质可知:n≤2^(k)-1,即:2^(k-1)-1<n≤2^k-1

    由此可推出:2^(k-1)<≤n≤2k,取对数后有:k-1<log2n≤k

    由于k-1和k是相邻的两个整数,故有k-1=floor(log2n),由此即得:k=floor(log2n)+1。

    

    展开全文
  • 完全二叉树

    2015-07-06 11:28:51
    完全二叉树,二叉树的基本操作,遍历算法,构建等操作
  • 说对于满二叉树,除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树完全二叉树完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其...

    满二叉树

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

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

    04e949b76add0c9e6f94e5924b4485d8.png

    完全二叉树

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

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

    8c3371a43c8738334775f02373154d79.png

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

    其实满二叉树是完全二叉树的特例,因为满二叉树已经满了,而完全并不代表满。满指的是出了叶子节点外每个节点都有两个孩子,而完全的含义则是最后一层没有满,并没有满。

    满二叉树肯定是完全二叉树

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

    展开全文
  • 满二叉树与完全二叉树的区别:满二叉树(Full Binary Tree):一个二叉树完全二叉树(Complete Binary Tree):完全二叉树完全二叉树的节点数是任意的,从形式上讲它是个缺失的的三角形,但所缺失的部分一定是右下角某个...

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

    满二叉树(Full Binary Tree):

    一个二叉树

    4abc5ba0c54eb75216ca552730026af7.png

    完全二叉树(Complete Binary Tree):

    完全二叉树:完全二叉树的节点数是任意的,从形式上讲它是个缺失的的三角形,但所缺失的部分一定是右下角某个连续的部
    分,最后那一行可能不是完整的,对于k层的完全二叉树,节点数的范围2^ (k - 1) -1 < N< 2^k - 1;
    
    设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,
    这就是完全二叉树。
    
                                                  0
                                         /               
                                      1                   2
                                  /                  /       
                                3        4         5           6
                              /      /        /    
                            7    8  9     10  11

    56b51edb2553c52a76f4f5f24cadba06.png
    展开全文
  • 完美二叉树, 完全二叉树和完满二叉树

    万次阅读 多人点赞 2018-06-22 15:05:42
    如果学习过二叉树,但是对这三种二叉树并没有深入的理解,或者完全被国产数据结构教科书所误导(只听说过满二叉树和完全二叉树)的朋友不妨花点时间耐着性子将本文仔细阅读N(>=1)遍。 1. 树(Tree)的基本概念 1.1 ...

    树在数据结构中占有非常重要的地位。本文从树的基本概念入手,给出完美(Perfect)二叉树,完全(Complete)二叉树和完满(Full)二叉树的区别。如果学习过二叉树,但是对这三种二叉树并没有深入的理解,或者完全被国产数据结构教科书所误导(只听说过满二叉树和完全二叉树)的朋友不妨花点时间耐着性子将本文仔细阅读N(>=1)遍。

    1. 树(Tree)的基本概念

    1.1 树的定义

    A tree is a (possibly non-linear) data structure made up of nodes or vertices 
    and edges without having any cycle. The tree with no nodes is called the null 
    or empty tree. A tree that is not empty consists of a root node and potentially 
    many levels of additional nodes that form a hierarchy.

    树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点,还(很可能)有多个附加结点,所有结点构成一个多级分层结构。

    [注:本文将node一律译为"结点"(而不是"节点"),因为joint或connection是节点,而node是结点。关于"结点"与"节点"请自行搜索浙江大学陈水福教授的文章--"360度"解读如何正确应用"结点"与"节点"]

    例如: 【图片来源: https://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg】

    A simple unordered tree; in this diagram, the node labeled 7 has two children, 
    labeled 2 and 6, and one parent, labeled 2. The root node, at the top, 
    has no parent. 上图是一棵无序的树示例。在上图中,标号为7的结点有两个孩子,分别是标号为2和6的结点。
    根结点,在最顶端,它没有双亲。

    1.2 树的基本术语

    Root The top node in a tree. 树的顶端结点
    Child A node directly connected to another node when moving away from the Root. 孩子 当远离根(Root)的时候,直接连接到另外一个结点的结点被称之为孩子(Child); 
    Parent The converse notion of a child. 双亲 相应地,另外一个结点称为孩子(child)的双亲(parent)。
    Siblings A group of nodes with the same parent. 兄弟 具有同一个双亲(Parent)的孩子(Child)之间互称为兄弟(Sibling)。
    Ancestor A node reachable by repeated proceeding from child to parent. 祖先 结点的祖先(Ancestor)是从根(Root)到该结点所经分支(Branch)上的所有结点。
    Descendant A node reachable by repeated proceeding from parent to child. 子孙 反之,以某结点为根的子树中的任一结点都称为该结点的子孙(Ancestor)。
    Leaf A node with no children. 叶子(终端结点) 没有孩子的结点(也就是度为0的结点)称为叶子(Leaf)或终端结点。
    Branch A node with at least one child. 分支(非终端结点) 至少有一个孩子的结点称为分支(Branch)或非终端结点。
    Degree The number of sub trees of a node. 结点所拥有的子树个数称为结点的度(Degree)。
    Edge The connection between one node and another. 一个结点和另一个结点之间的连接被称之为边(Edge)。
    Path A sequence of nodes and edges connecting a node with a descendant. 路径 连接结点和其后代的结点之间的(结点,边)的序列。 
    Level The level of a node is defined by 0 + (the number of connections between the node and the root). 层次 结点的层次(Level)从根(Root)开始定义起,根为第0层,根的孩子为第1层。以此类推,若某结点在第i层,那么其子树的根就在第i+1层。
    Height of node The height of a node is the number of edges on the longest path between that node and a leaf. 结点的高度 结点的高度是该结点和某个叶子之间存在的最长路径上的边的个数。 
    Height of tree The height of a tree is the height of its root node. 树的高度 树的高度是其根结点的高度。 
    Depth of node The depth of a node is the number of edges from the tree's root node to the node. 结点的深度 结点的深度是从树的根结点到该结点的边的个数。(注:树的深度指的是树中结点的最大层次。)
    Forest A forest is a set of n ≥ 0 disjoint trees. 森林 森林是n(>=0)棵互不相交的树的集合。

    2 二叉树(Binary Tree)

    2.1 什么是二叉树(Binary Tree)

    每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。

    2.2 二叉树的性质

    (1)若二叉树的层次从0开始,则在二叉树的第i层至多有2^i个结点(i>=0)。

    (2)高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)。 (空树的高度为-1)

    (3)对任何一棵二叉树,如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。

    2.3 完美二叉树(Perfect Binary Tree)

    A Perfect Binary Tree(PBT) is a tree with all leaf nodes at the same depth. 
    All internal nodes have degree 2.

    一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。 (注: 国内的数据结构教材大多翻译为"满二叉树")

    例如:

    2.4 完全二叉树(Complete Binary Tree)

    A Complete Binary Tree (CBT) is a binary tree in which every level, 
    except possibly the last, is completely filled, and all nodes 
    are as far left as possible.

    换句话说,完全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐。

    例如:

    2.5 完满二叉树(Full Binary Tree)

    A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children.

    换句话说,所有非叶子结点的度都是2。(只要你有孩子,你就必然是有两个孩子。) 

    注:Full Binary Tree又叫做Strictly Binary Tree

    例如:

     

    2.6 完美(Perfect)二叉树 v.s. 完全(Complete)二叉树

    (1) 一棵完美(Perfect)二叉树看起来是这个样儿的, 【图2.6.1】

    (2) 那么,将编号为15, 14, ..., 9的叶子结点从右到左依次拿掉或者拿掉部分,则是一棵完全(Complete)二叉树,

    例如,将上图中的编号为15, 14, 13, 12, 11叶子结点都拿掉(从右到左的顺序), 【图2.6.2】

    (3) 下图就不是一棵完全(Complete)二叉树,【图2.6.3】,

    如果将编号11(K)结点从编号6(E)的左儿子位置移动到编号5(E)的右儿子位置,则变成一棵完全(Complete)二叉树。

    注: 图2.6.1, 2.6.2和2.6.3均来自:http://alrightchiu.github.io/SecondRound/binary-tree-introjian-jie.html, 但是,其将Full Binary Tree当做就是Perfect Binary Tree, 我认为是不正确的,特此说明。

    特别说明: 其实,理解完全(Complete)二叉树可以借助于栈(stack)的思想。 例如,把图2.6.1中的完美(Perfect)二叉树的所有结点按照编号1, 2, 3, ..., 15依次入栈(push)。 那么,对栈的每一次出栈(pop)操作后,栈里保存的结点集对应到图2.6.1上去都是一棵完全(Complete)二叉树。

    2.7 完全(Complete)二叉树 v.s. 完满(Full)二叉树

    【截图来源:http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf】

    2.8 完满(Full)二叉树 v.s. 完全(Complete)二叉树 v.s. 完美(Perfect)二叉树

    【图片来源: http://www.csie.ntnu.edu.tw/~u91029/BinaryTree2.png】

     

    3. 总结 (下表参考来源)

    完美二叉树 Perfect Binary Tree

    Every node except the leaf nodes have two children and every level (last level too) is completely filled. 除了叶子结点之外的每一个结点都有两个孩子,每一层(当然包含最后一层)都被完全填充。

    完全二叉树 Complete Binary Tree Every level except the last level is completely filled and all the nodes are left justified. 除了最后一层之外的其他每一层都被完全填充,并且所有结点都保持向左对齐。
    完满二叉树 Full/Strictly Binary Tree Every node except the leaf nodes have two children. 除了叶子结点之外的每一个结点都有两个孩子结点。
    • 完美(Perfect)二叉树一定是完全(Complete)二叉树,但完全(Complete)二叉树不一定是完美(Perfect)二叉树。
    • 完美(Perfect)二叉树一定是完满(Full)二叉树,但完满(Full)二叉树不一定是完美(Perfect)二叉树。
    • 完全(Complete)二叉树可能是完满(Full)二叉树,完满(Full)二叉树也可能是完全(Complete)二叉树。
    • 既是完全(Complete)二叉树又是完满(Full)二叉树也不一定就是完美(Perfect)二叉树。
    展开全文
  • 判断二叉树是否为完全二叉树的实例完全二叉树是指除了最后一层之外,其他每一层的结点数都是满的,今天百分网小编为大家整理的判断二叉树是否为完全二叉树的实例,仅供学习参考,欢迎大家阅读浏览!完全二叉树特点...
  • 完全二叉树特点完全二叉树是指除了最后一层之外,其他每一层的结点数都是满的。最后一层如果也满了,是一颗满二叉树,也是完全二叉树。最后一层如果不满,缺少的结点也全部的集中在左边,那也是一颗完全二叉树。判断...
  • 文章目录完全二叉树堆 参考:https://blog.csdn.net/sodacoco/article/details/83478803 https://www.cnblogs.com/zhoanghua/p/9288899.html 完全二叉树 若堆的深度【层数】为h,除了最后一层,其上各层 (1~h-1) 的...
  • 完全二叉树 满二叉树

    2020-05-03 23:59:36
    完全二叉树 满二叉树 1.定义 ①满二叉树:除最后一层无任何节点外,每一层上的所有节点都有两个子结点的二叉树。 另外的定义:一个二叉树,如果每一层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,...
  • 完全二叉树特点 完全二叉树是指除了最后一层之外,其他每一层的结点数都是满的。最后一层如果也满了,是一颗满二叉树,也是完全二叉树。最后一层如果不满,缺少的结点也全部的集中在左边,那也是一颗完全二叉树。 ...
  • 满二叉树 完全二叉树的定义 满二叉树就是每一层节点个数都是满的二叉树。第n层节点个数 = pow(2,n - 1), 总的节点个数 = pow(2, n)。 完全二叉树就是满二叉树从最后一层的最右侧开始去节点得的树,这个去...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,356
精华内容 7,742
关键字:

完全二叉树