02331数据结构
在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
题目
在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
参考答案和解析
相似问题和答案
第1题：
[算法描述]
int Height(BSTree t)
// 求平衡二叉树t的高度
{level=0;p=t;
while(p)
{level++; // 树的高度增1
if(p->bf<0)p=p->rchild;//bf=-1 沿右分枝向下
//bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存储定义
else p=p->lchild; //bf>=0 沿左分枝向下
}//while
return (level);//平衡二叉树的高度
} //算法结束
第2题：
在平衡的二叉排序树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。()
第3题：
A．错误
B．正确
第4题：
平衡二叉树中任意结点的平衡因子只能是(50)之一。
A．0，1，2
B．0，1
C．-1，+1
D．0，-1，+1
解析：平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树：它的左子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。平衡因子定义为该结点的左子树的深度减去其右子树的深度，所以平衡二叉树中任意结点的平衡因子只能是0、-1、+1之一。
第5题：
下图所示平衡二叉树(树中任一结点的左右子树高度之差不超过1)中，结点A的右子树AR高度为h，结点B的左子树BL高度为h，结点C的左子树CL、右子树CR高度都为h-1。若在CR中插入一个结点并使得CR的高度增加1，则该二叉树(61)。
A．以B为根的子二叉树变为不平衡
B．以C为根的子二叉树变为不平衡
C．以A为根的子二叉树变为不平衡
D．仍然是平衡二叉树
解析：本题考查平衡查找树。由于平衡二叉树中任一结点的左右子树高度之差不超过1，因此，若在CR中插入一个结点并使得CR的高度增加1，则结点C的左右子树高度之差为-1，同时以C为根的子树高度增加了1，所以结点B的左右子树高度之差变为-1。如此一来，A的左子树的高度为h+2、右子树的高度为h，根据定义，以A为根的子二叉树变为不平衡。
第6题：
A.LL
B、LR
C、RL
D、RR
第7题：
A.LL型
B.LR型
C.RL型
D.RR型
第8题：
下面关于哈夫曼树的叙述中，正确的是(58)。
A．哈夫曼树一定是完全二叉树
B．哈夫曼树一定是平衡二叉树
C．哈夫曼树中权值最小的两个结点互为兄弟结点
D．哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点
解析：哈夫曼树又称最优二叉树或最优搜索树，是一种带权路径长度最短的二叉树。具有以下特征：
(1)当叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。即哈夫曼树不一定是完全二叉树。
(2)在最优二叉树中，权值越大的叶子离根越近。
(3)最优二叉树的形态不唯一，但WPL最小。
哈夫曼树的构造：
(1)根据给定的n个权值{w1，w2，…，wn}构造n棵二叉树的集合F={Tl，T2，…，Tn}，其中Ti中只有一个权值为wi的根结点，左右子树为空；
(2)在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右予树上根结点的权值之和。
(3)将新的二叉树加入到F中，删除原两棵根结点权值最小的树；
(4)重复(2)和(3)直到F中只含一棵树为止，这棵树就是哈夫曼树。
平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。而哈夫曼树并未要求左右两个子树的高度差的绝对值不超过1，根据其构造可知，是从上往下顺序排下来的，且左孩子结点大于父孩子结点。
第9题：
由元素序列(27,16,75,38,51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)为(46)。
A．27
B．38
C．51
D．75
解析：平衡二叉树(AVL树)或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。二叉树结点的平衡因子(Balance Factor, BF)定义为该结点的左子树的深度减去其右子树的深度。平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。由元素序列(27,16,75,38,51)构造平衡二叉树的过程如下图所示，将元素51加入树中之前，二叉树保持平衡，加入结点51后，结点38的平衡因子由0变为-1，75所在结点的平衡因子由1变为2，27所在结点的平衡因子由-1变为-2。因此，75所在结点是离插入结点最近且平衡因子的绝对值为2的结点。
第10题：
在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做(14)型调整以使其平衡。
A．LL
B．LR
C．RL
D．RR
解析：见平衡二叉树的调整。