平衡二叉树中查找关键字结点 |
您所在的位置:网站首页 › 二叉排序树关键字值 › 平衡二叉树中查找关键字结点 |
二叉排序树的定义: (1)若它的左子树不为空,则左子树所有结点均小于它的根结点的值; (2)若它的右子树不为空,则右子树所有结点均大于它的根结点的值; (3)它的左右子树都是二叉排序树。 平衡二叉树本质上是二叉排序树。 平衡二叉树的性质: (1)根结点的左子树和右子树的深度最多相差1。 (2)根结点的左子树和右子树叶都是一棵平衡二叉树。 平衡二叉树查找关键字是否存在? 解析思路: (1)先根据结点个数计算平衡二叉树深度,根据深度将不符合要求的排除 计算过程如下: ni表示深度为h的平衡二叉树中含有的最少结点数,有n0=0,n1=1,n2=2; 计算公式为: 实例: 1、在含有15个结点的平衡二叉树上,查找关键字为28(存在该结点)的结点,则依次比较的关键字可能是()。 A.30,36 B.38,48,28 C.48,18,38,28 D.60,30,50,40,38,36 答案:C 解析如下: n0=0,n1=1,n2=2, n3=n2+n1+1=4 n4=n3+n2+1=7 n5=n4+n3+1=12 n6=n5+n4+1=20>15 高度为6的平衡二叉树最少有20个结点,因此15个结点的平衡二叉树高度为5,而最小的叶子结点的层数为3.
而C的查找路径,如下图所示: 2、在含有14个结点的平衡二叉树上,查找关键字为40的结点,则依次比较的关键字可能是() A.27,48,25,43,40 B.47,45,18,27,36,40 C.46,42,18,20,28,40 D.15.45.40 答案:D 解析如下: n0=0,n1=1,n2=2, n3=n2+n1+1=4 n4=n3+n2+1=7 n5=n4+n3+1=12 n6=n5+n4+1=20>14 因此平衡二叉树的高度为5. 如下图所示: 各选项构成的二叉树如下: 显然,A选项中蓝色圆圈的25元素比根结点27小,不符合平衡二叉树的定义。 B,C选项的树高均为6,不满足平衡二叉树的深度为5的要求。 D选项符合要求。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |