满二叉树 与完全二叉树的区别 图
答案:6 悬赏:60
解决时间 2021-01-10 22:45
- 提问者网友:我的未来我做主
- 2021-01-09 22:44
满二叉树 与完全二叉树的区别 图
最佳答案
- 二级知识专家网友:不如潦草
- 2021-01-09 22:59
满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。
完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为p+1。
完全二叉树具有以下两个性质:
性质5:具有n个结点的完全二叉树的深度为[log2n]+1。
性质6:设完全二叉树共有n个结点。如果从根结点开始,按层次(每一层从左到右)用自然数1,2,……,n给结点进行编号,则对于编号为k(k=1,2,……,n)的结点有以下结论:
①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2)。
②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点)。
③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。
满二叉树肯定是完全二叉树,完全二叉树不一定是满二叉树。
为满二叉树为完全二叉树
完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为p+1。
完全二叉树具有以下两个性质:
性质5:具有n个结点的完全二叉树的深度为[log2n]+1。
性质6:设完全二叉树共有n个结点。如果从根结点开始,按层次(每一层从左到右)用自然数1,2,……,n给结点进行编号,则对于编号为k(k=1,2,……,n)的结点有以下结论:
①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2)。
②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点)。
③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。
满二叉树肯定是完全二叉树,完全二叉树不一定是满二叉树。
为满二叉树为完全二叉树
全部回答
- 1楼网友:轻雾山林
- 2021-01-10 03:24
引用剑戈峥嵘的回答:
满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。
完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为p+1。
完全二叉树具有以下两个性质:
性质5:具有n个结点的完全二叉树的深度为[log2n]+1。
性质6:设完全二叉树共有n个结点。如果从根结点开始,按层次(每一层从左到右)用自然数1,2,……,n给结点进行编号,则对于编号为k(k=1,2,……,n)的结点有以下结论:
①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2)。
②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点)。
③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。
满二叉树肯定是完全二叉树,完全二叉树不一定是满二叉树。
为满二叉树为完全二叉树
楼上满二叉树的图片不符合定义吧
满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。
完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为p+1。
完全二叉树具有以下两个性质:
性质5:具有n个结点的完全二叉树的深度为[log2n]+1。
性质6:设完全二叉树共有n个结点。如果从根结点开始,按层次(每一层从左到右)用自然数1,2,……,n给结点进行编号,则对于编号为k(k=1,2,……,n)的结点有以下结论:
①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2)。
②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点)。
③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。
满二叉树肯定是完全二叉树,完全二叉树不一定是满二叉树。
为满二叉树为完全二叉树
楼上满二叉树的图片不符合定义吧
- 2楼网友:深街酒徒
- 2021-01-10 02:08
最佳答案中的这幅图选的并不恰当,并不符合你所提到的第K层上有第k层上有2^(k-1)个节点的定义。这幅图符合国际上的满二叉树的观点,即“如果一棵二叉树的结点要么是叶子,要么这个结点有两个孩子结点,这样的树就是满二叉树。”问题在于如果按此定义进行推倒,下图也符合满二叉树的定义:
国内关于满二叉树的定义,通常应理解为所谓的“完美二叉树”,即所有层上的节点均为最大值,第K层上有2^(k-1)个节点。树的外观应为三角形。
此时,“满二叉树肯定是完全二叉树,完全二叉树不一定是满二叉树。”这一论断才能够成立。
- 3楼网友:長槍戰八方
- 2021-01-10 01:39
引用剑戈峥嵘的回答:
满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。
完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为p+1。
完全二叉树具有以下两个性质:
性质5:具有n个结点的完全二叉树的深度为[log2n]+1。
性质6:设完全二叉树共有n个结点。如果从根结点开始,按层次(每一层从左到右)用自然数1,2,……,n给结点进行编号,则对于编号为k(k=1,2,……,n)的结点有以下结论:
①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2)。
②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点)。
③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。
满二叉树肯定是完全二叉树,完全二叉树不一定是满二叉树。
为满二叉树为完全二叉树
满二叉树的图解是错误的
满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。
完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为p+1。
完全二叉树具有以下两个性质:
性质5:具有n个结点的完全二叉树的深度为[log2n]+1。
性质6:设完全二叉树共有n个结点。如果从根结点开始,按层次(每一层从左到右)用自然数1,2,……,n给结点进行编号,则对于编号为k(k=1,2,……,n)的结点有以下结论:
①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2)。
②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点)。
③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。
满二叉树肯定是完全二叉树,完全二叉树不一定是满二叉树。
为满二叉树为完全二叉树
满二叉树的图解是错误的
- 4楼网友:人類模型
- 2021-01-10 01:12
满二叉树肯定是完全二叉树
完全二叉树不一定是满二叉树
完全二叉树不一定是满二叉树
- 5楼网友:执傲
- 2021-01-10 00:37
满二叉树是指这样的一种二叉树,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯