设为首页 - 加入收藏
广告 1000x90
您的当前位置:78345黄大仙救世网挂牌 > 结点 > 正文

求解具有n个结点的完全二叉树的深度写出计算过程

来源:未知 编辑:admin 时间:2019-06-25

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  假设当n=2^k-1时具有n个结点的完全二叉树的深度为「log2n」+1,

  剩余的1(或2,...,2^k)个结点均填在第「log2n」+2层上(作为“叶子”),深度刚好增加了1,

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

  3、对任何一棵二叉树T,如果其终端结点数为N0,度为2的结点数为N2,则N0=N2+1;

  2011-01-11展开全部K层完全二叉树,就是前(K-1)层为满二叉树,第K层均为叶结点,可以不满。所以结点与深度的关系为:

  2 ^ ( K - 1 ) - 1 n = 2 ^ K - 1。 所以K = [ ( n + 1 ) 以 2 为底取对数,然后向上取整 ]。

  若一棵二叉树为空,则其深度为0,否则其深度等于左子树和右子树的最大深度加1,即有如下递归模型:

  8、如果将树中结点的各子树看成从左至右是有次序的(即不能互换),则称该树为有序树,否则称为无序树。在有序树中,最左边的子树的根称为第一个孩子,最右边的称为最后一个孩子。

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

  性质三 对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1

  性质五 如果对一棵有n个结点的完全二叉树(其深度为「log2n」+1)的结点按层序编号(从第1层到第「log2n」+1层,每层从左到右),则对任一结点i(1≤i≤n),有

  ①如果i=1,则结点i是二叉树的根,无双亲;如果i1,则其双亲PARENT(i)是结点「i/2」

  ②如果2in,则结点n无左孩子(结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i

本文链接:http://anicburst.com/jiedian/355.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top