精华内容
下载资源
问答
  • 本文从树的基本概念入手,给出完美(Perfect)二叉树,完全(Complete)二叉树和完满(Full)二叉树的区别。如果学习过二叉树,但是对这三种二叉树并没有深入的理解,或者完全被国产数据结构教科书所误导(只听说过满二叉树...

    树在数据结构中占有非常重要的地位。本文从树的基本概念入手,给出完美(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 树的基本术语

    RootThe top node in a tree.树的顶端结点
    ChildA node directly connected to another node when moving away from the Root.孩子当远离根(Root)的时候,直接连接到另外一个结点的结点被称之为孩子(Child); 
    ParentThe converse notion of a child.双亲相应地,另外一个结点称为孩子(child)的双亲(parent)。
    SiblingsA group of nodes with the same parent.兄弟具有同一个双亲(Parent)的孩子(Child)之间互称为兄弟(Sibling)。
    AncestorA node reachable by repeated proceeding from child to parent.祖先结点的祖先(Ancestor)是从根(Root)到该结点所经分支(Branch)上的所有结点。
    DescendantA node reachable by repeated proceeding from parent to child.子孙以某结点为根的子树中的任一结点都称为该结点的子孙(后代)。
    LeafA node with no children.叶子(终端结点)没有孩子的结点(也就是度为0的结点)称为叶子(Leaf)或终端结点。
    BranchA node with at least one child.分支(非终端结点)至少有一个孩子的结点称为分支(Branch)或非终端结点。
    DegreeThe number of sub trees of a node.结点所拥有的子树个数称为结点的度(Degree)。
    EdgeThe connection between one node and another.一个结点和另一个结点之间的连接被称之为边(Edge)。
    PathA sequence of nodes and edges connecting a node with a descendant.路径连接结点和其后代的结点之间的(结点,边)的序列。 
    LevelThe 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 nodeThe height of a node is the number of edges on the longest path between that node and a leaf.结点的高度结点的高度是该结点和某个叶子之间存在的最长路径上的边的个数。 
    Height of treeThe height of a tree is the height of its root node.树的高度树的高度是其根结点的高度。 
    Depth of nodeThe depth of a node is the number of edges from the tree's root node to the node.结点的深度结点的深度是从树的根结点到该结点的边的个数。(注:树的深度指的是树中结点的最大层次。)
    ForestA 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 TreeEvery level except the last level is completely filled and all the nodes are left justified. 除了最后一层之外的其他每一层都被完全填充,并且所有结点都保持向左对齐。
    完满二叉树Full/Strictly Binary TreeEvery node except the leaf nodes have two children. 除了叶子结点之外的每一个结点都有两个孩子结点。
    • 完美(Perfect)二叉树一定是完全(Complete)二叉树,但完全(Complete)二叉树不一定是完美(Perfect)二叉树。
    • 完美(Perfect)二叉树一定是完满(Full)二叉树,但完满(Full)二叉树不一定是完美(Perfect)二叉树。
    • 完全(Complete)二叉树可能是完满(Full)二叉树,完满(Full)二叉树也可能是完全(Complete)二叉树。
    • 既是完全(Complete)二叉树又是完满(Full)二叉树也不一定就是完美(Perfect)二叉树。
    展开全文
  • 完美二叉树, 完全二叉树和完满二叉树

    万次阅读 多人点赞 2018-06-22 15:05:42
    本文从树的基本概念入手,给出完美(Perfect)二叉树,完全(Complete)二叉树和完满(Full)二叉树的区别。如果学习过二叉树,但是对这三种二叉树并没有深入的理解,或者完全被国产数据结构教科书所误导(只听说过满二叉树...

    树在数据结构中占有非常重要的地位。本文从树的基本概念入手,给出完美(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 树的基本术语

    RootThe top node in a tree.树的顶端结点
    ChildA node directly connected to another node when moving away from the Root.孩子当远离根(Root)的时候,直接连接到另外一个结点的结点被称之为孩子(Child); 
    ParentThe converse notion of a child.双亲相应地,另外一个结点称为孩子(child)的双亲(parent)。
    SiblingsA group of nodes with the same parent.兄弟具有同一个双亲(Parent)的孩子(Child)之间互称为兄弟(Sibling)。
    AncestorA node reachable by repeated proceeding from child to parent.祖先结点的祖先(Ancestor)是从根(Root)到该结点所经分支(Branch)上的所有结点。
    DescendantA node reachable by repeated proceeding from parent to child.子孙反之,以某结点为根的子树中的任一结点都称为该结点的子孙(Ancestor)。
    LeafA node with no children.叶子(终端结点)没有孩子的结点(也就是度为0的结点)称为叶子(Leaf)或终端结点。
    BranchA node with at least one child.分支(非终端结点)至少有一个孩子的结点称为分支(Branch)或非终端结点。
    DegreeThe number of sub trees of a node.结点所拥有的子树个数称为结点的度(Degree)。
    EdgeThe connection between one node and another.一个结点和另一个结点之间的连接被称之为边(Edge)。
    PathA sequence of nodes and edges connecting a node with a descendant.路径连接结点和其后代的结点之间的(结点,边)的序列。 
    LevelThe 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 nodeThe height of a node is the number of edges on the longest path between that node and a leaf.结点的高度结点的高度是该结点和某个叶子之间存在的最长路径上的边的个数。 
    Height of treeThe height of a tree is the height of its root node.树的高度树的高度是其根结点的高度。 
    Depth of nodeThe depth of a node is the number of edges from the tree's root node to the node.结点的深度结点的深度是从树的根结点到该结点的边的个数。(注:树的深度指的是树中结点的最大层次。)
    ForestA 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 TreeEvery level except the last level is completely filled and all the nodes are left justified. 除了最后一层之外的其他每一层都被完全填充,并且所有结点都保持向左对齐。
    完满二叉树Full/Strictly Binary TreeEvery node except the leaf nodes have two children. 除了叶子结点之外的每一个结点都有两个孩子结点。
    • 完美(Perfect)二叉树一定是完全(Complete)二叉树,但完全(Complete)二叉树不一定是完美(Perfect)二叉树。
    • 完美(Perfect)二叉树一定是完满(Full)二叉树,但完满(Full)二叉树不一定是完美(Perfect)二叉树。
    • 完全(Complete)二叉树可能是完满(Full)二叉树,完满(Full)二叉树也可能是完全(Complete)二叉树。
    • 既是完全(Complete)二叉树又是完满(Full)二叉树也不一定就是完美(Perfect)二叉树。
    展开全文
  • 一、完美二叉树 一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。 二、满二叉树 如果一棵二叉树只有度为 0 的结点和度为 2的结点,则这棵二叉树为满二叉树。 三、完全二叉树 三者对比...

    一、完美二叉树

    一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。

    二、满二叉树

    如果一棵二叉树只有度为 0 的结点和度为 2的结点,则这棵二叉树为满二叉树。

    三、完全二叉树

    完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

    完全二叉树通常采用数组储存,int[] arr = new int[n]

    当n从0开始时:对于结点 i ,其左子节点为 2i+1 ,右子节点为 2i+2

    当n从1开始时:对于结点 i ,其左子节点为 2i ,右子节点为 2i+1

    三者对比

    • 完美(Perfect)二叉树一定是完全(Complete)二叉树,但完全(Complete)二叉树不一定是完美(Perfect)二叉树。
    • 完美(Perfect)二叉树一定是满(Full)二叉树,但满(Full)二叉树不一定是完美(Perfect)二叉树。
    • 完全(Complete)二叉树可能是满(Full)二叉树,满(Full)二叉树也可能是完全(Complete)二叉树。
    • 既是完全(Complete)二叉树又是满(Full)二叉树也不一定就是完美(Perfect)二叉树。
    展开全文
  • 本文从树的基本概念入手,给出完美(Perfect)二叉树,完全(Complete)二叉树和完满(Full)二叉树的区别。可能会有错误,希望大家多多指正。 1. 树(Tree)的基本概念 1.1 树的定义 树是由结点或顶点和边组成的(可能是非...

    树在数据结构中占有非常重要的地位。本文从树的基本概念入手,给出完美(Perfect)二叉树,完全(Complete)二叉树和完满(Full)二叉树的区别。可能会有错误,希望大家多多指正。

    1. 树(Tree)的基本概念

    1.1 树的定义

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

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

    树
    上图是一棵无序的树示例。在上图中,标号为7的结点有两个孩子,分别是标号为2和6的结点。
    根结点,在最顶端,它没有双亲。

    1.2 树的基本术语

    英文英文翻译中文中文翻译
    RootThe top node in a tree.树的顶端结点
    ChildA node directly connected to another node when moving away from the Root.孩子当远离根(Root)的时候,直接连接到另外一个结点的结点被称之为孩子(Child)
    ParentThe converse notion of a child.双亲相应地,另外一个结点称为孩子(child)的双亲(parent)。
    SiblingsA group of nodes with the same parent.兄弟具有同一个双亲(Parent)的孩子(Child)之间互称为兄弟(Sibling)。
    internal nodeA Node that has at least one chird.内结点具有至少一个孩子的结点
    AncestorA node reachable by repeated proceeding from child to parent.祖先结点的祖先(Ancestor)是从根(Root)到该结点所经分支(Branch)上的所有结点。
    DescendantA node reachable by repeated proceeding from parent to child.子孙反之,以某结点为根的子树中的任一结点都称为该结点的子孙(Ancestor)。
    LeafA node with no children.叶子(终端结点)没有孩子的结点(也就是度为0的结点)称为叶子(Leaf)或终端结点。
    BranchA node with at least one child.分支(非终端结点)至少有一个孩子的结点称为分支(Branch)或非终端结点。
    DegreeThe number of sub trees of a node.结点所拥有的子树个数称为结点的度(Degree)。
    PathA sequence of nodes and edges connecting a node with a descendant.路径连接结点和其后代的结点之间的(结点,边)的序列。
    LevelThe 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 nodeThe height of a node is the number of edges on the longest path between that node and a leaf.结点的高度结点的高度是该结点和某个叶子之间存在的最长路径上的边的个数。
    Height of treeThe height of a tree is the height of its root node.树的高度树的高度是其根结点的高度。
    Depth of nodeThe depth of a node is the number of edges from the tree’s root node to the node.结点的深度结点的深度是从树的根结点到该结点的边的个数。(注:树的深度指的是树中结点的最大层次。)
    ForestA 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)

    一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。

    例如:
    完美二叉树

    2.4 完全二叉树(Complete Binary Tree)

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

    例如:
    完全二叉树

    2.5 满二叉树(Full Binary Tree)

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

    例如:
    满二叉树

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

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

    在这里插入图片描述

    (2) 那么,将编号为15, 14, …, 9的叶子结点从右到左依次拿掉或者拿掉部分,则是一棵完全(Complete)二叉树,例如,将上图中的编号为15, 14, 13, 12, 11叶子结点都拿掉(从右到左的顺序), 【图2.6.2】

    (3) 下图就不是一棵完全(Complete)二叉树
    在这里插入图片描述

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

    注: 上三图均来自: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 TreeEvery node except the leaf nodes have two children and every level (last level too) is completely filled.完美二叉树除了叶子结点之外的每一个结点都有两个孩子,每一层(当然包含最后一层)都被完全填充。
    Complete BinaryTree Every level except the last level is completely filled and all the nodes are left justified.完全二叉树除了最后一层之外的其他每一层都被完全填充,并且所有结点都保持向左对齐。
    Full Binary TreeEvery node except the leaf nodes have two children.满二叉树除了叶子结点之外的每一个结点都有两个孩子结点。

    完美(Perfect)二叉树一定是完全(Complete)二叉树,但完全(Complete)二叉树不一定是完美(Perfect)二叉树。
    完美(Perfect)二叉树一定是完满(Full)二叉树,但满(Full)二叉树不一定是完美(Perfect)二叉树。
    完全(Complete)二叉树可能是满(Full)二叉树,满(Full)二叉树也可能是完全(Complete)二叉树。
    既是完全(Complete)二叉树又是满(Full)二叉树也不一定就是完美(Perfect)二叉树。

    展开全文
  • 完美二叉树, 完全二叉树和完满二叉树 2017年09月22日 17:19:47 小辣抓 阅读数:10663更多 <div class="tags-box space"> ...
  • 满二叉树与完美二叉树 国内的翻译和国外是有些对不上的\ 完美二叉树 英文: Perfect Binary Tree, 有时候在国内就叫满二叉树 除了叶子结点之外的每一个结点都有两个孩子,每一层(当然包含最后一层)都被完全填充 ...
  • 完美二叉树、完全二叉树、完满二叉树

    万次阅读 多人点赞 2018-08-24 19:56:03
    1、二叉树(Binary Tree) 1.1 什么是二叉树(Binary Tree) 每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。 1.2 二叉树的性质 若二叉树的...
  • 二叉树(Binary Tree) 什么是二叉树(Binary Tree) 每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。 二叉树的性质 (1)若二叉树的层次从0开始...
  • 完美二叉树, 完全二叉树和完满二叉树本文出处:http://www.cnblogs.com/idorax/p/6441043.html树在数据结构中占有非常重要的地位。本文从树的基本概念入手,给出完美(Perfect)二叉树,完全(Complete)二叉树和完满...
  • 完美二叉树, 完全二叉树和完满二叉树 树在数据结构中占有非常重要的地位。本文从树的基本概念入手,给出完美(Perfect)二叉树,完全(Complete)二叉树和完满(Full)二叉树的区别。如果学习过二叉树,但是对这三种...
  • 了解完美二叉树

    2021-03-01 13:25:28
    文章目录C示例完美二叉树定理参考文档     在本教程中,您将学习完美二叉树。此外,您还将找到C语言中完美二叉树的示例。     完美二叉树是一种二叉树,其中每个内部节点正好有两个子节点,所有叶节点处于...
  • 【二叉树】完美二叉树 完美二叉树 (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...
  • 完美二叉树的层序遍历:一开始将root进队,然后进入外循环,循环条件为队列不为空,内循环次数为queue.size(),如果i小于size-1的话,说明正在遍历的节点不是该层最后一个节点,故在出队后,node->next = queue....
  • 如果其右子节点不为空,那么该节点的value值永远 其右子节点满二叉树:树中除了叶子节点,每个节点都有两个子节点完全二叉树:在满足满二叉树的性质后,最后一层的叶子节点均需在最左边完美二叉树:满足完全二叉树...
  • 没时间写了,以后补充,先参考这个。 满二叉树(Full Binary Tree)&&完全二叉树(Complete Binary Tree) full tree complete tree
  • 二叉树:树中每个节点至多有两个子节点 【最普通的二叉】 二叉搜索树:对于树中任何节点,如果其左子节点不为空,那么该节点的value值永远>=其左子节点;如果其右子节点不为空,那么该节点的value值永远<=...
  • 完美二叉树 Perfect Binary Tree 除了叶子结点之外的每一个结点都有两个孩子,每一层(当然包含最后一层)都被完全填充。 下图就不是一棵完全(Complete)二叉树 如果将编号11(K)结点从编号6(E)的左儿子位置移动到...
  • internal nodes介绍: 完美二叉树举例: 高度为h的完美二叉树的结点总数为: – 1。(高度h是从根结点到叶子结点的层数) 四、二叉查找树(Binary Search Tree) 1 简介 二叉查找树也称为有序二叉查找树,满足二叉...
  • 满二叉树 所有非叶子结点的度都是2,也就是说,一个结点要么没有孩子,要么就有两个孩子。 ...完美二叉树 二叉树中除了叶子结点,每个结点都有两个孩子,并且每个叶子结点的深度是一样的。 ...
  • 给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针,让这个指针指向其...
  • 完美二叉树

    千次阅读 2013-09-15 22:58:49
    class BinaryTree { // 定义二叉树的操作类 class Node { private Comparable data; // 保存数据 private Node left;// 表示左子树 private Node right;// 表示右子树 public Node(Comparable data) { ...
  • 如图所示, 假设二叉树中的结点从1开始,从左到右,从上到下进行标号。 那么结点标号(label)与层数(level)的关系为: level=log2(label) +1level = log_{2}(label ) \ +1level=log2​(label) +1 Java代码...
  • lua构造完美二叉树

    千次阅读 2017-12-05 19:27:30
    重点是今天下用lua来写构造一个二叉树,中间有个小坑,感觉自己弱的数据结构没学好啊,以后还是要多看看别人的代码,虽然我现在也不想看书,之前也问过公司的一个人,写代码这种东西,还是强调实干,看那么多书,然...
  • 填充完美二叉树的next指针 思路 对于root节点,只要让root.left.next = root.right即可。 但要让节点5和节点6相连,必须从各自的父亲入手,因此递归函数需要传入两个参数,设为node1和node2,连接node1和node2需要...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,376
精华内容 5,750
关键字:

完美二叉树