违法和不良信息举报 联系客服
免费注册 登录

在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡点为A,并已知A的左孩子的平衡因子为－1

题目

在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做(14)型调整以使其平衡。

A．LL

B．LR

C．RL

D．RR

如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

假设一棵平衡二叉树的每个结点都表明了平衡因子b,试设计一个算法,求平衡二叉树的高度。


参考答案：因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左(当b=1时)或右(当b=-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题：

在平衡二叉树中，(55)。

A．任意结点的左、右子树结点数目相同

B．任意结点的左、右子树高度相同

C．任意结点的左、右子树高度之差的绝对值不大于1

D．不存在度为1的结点


正确答案：C
解析：本题考查平衡二叉树的基本概念。平衡二叉树又称为AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树结点的平衡因子(Balance　Factor，BF)定义为该结点的左子树的深度减去其右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

第4题：

一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为(57)个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则(58)。

A．m+2

B．m+1

C．m

D．m-1


正确答案：B

第5题：

由元素序列{27，16，75，38，51}构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入节点最近且平衡因子的绝对值为2的节点)为(9)。

A．27

B．38

C．51

D．75


正确答案：D
解析：二叉排序树的构造方法如下：每读入一个数据，建立一个新节点，若二叉排序树非空，则将新节点的值与根节点的值比较，。如果小于根节点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空，则新节点作为二叉排序树的根节点。节点的平衡因子是指节点右子树深度与左子树深度之差。由数据{27，16，75，38，51}构造平衡二叉树，插入51后首次出现不平衡子树，易知最小不平衡子树的节点为75。

第6题：

在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。

A.LL

B、LR

C、RL

D、RR


参考答案：C

第7题：

在平衡二叉树中插入一个结点后引起了不平衡,设最低(最接近于叶子)的不平衡点是A,并已知A的左、右孩子的平衡因子分别为－1和0,则应进行的平衡旋转是()

A.LL型

B.LR型

C.RL型

D.RR型


参考答案：B

第8题：

已知二叉树T的结点形式为(lling,data,count,rlink),在树中查找值为X的结点,若找到,则记数(count)加1,否则,作为一个新结点插入树中,插入后仍为二叉排序树,写出其非递归算法。


参考答案：
　　[算法描述]
　　void SearchBST(BiTree &T,int target){
　　BiTree s,q,f; //以数据值target,新建结点s
　　s=new BiTNode;
　　s->data.x=target;
　　s->data.count=0;
　　s->lchild=s->rchild=NULL;
　　if(!T){
　　T=s;
　　return ;
　　} //如果该树为空则跳出该函数
　　f=NULL;
　　q=T;
　　while (q){
　　if (q->data.x==target){
　　q->data.count++;
　　return ;
　　} //如果找到该值则计数加一
　　f=q;
　　if (q->data.x>target) //如果查找值比目标值大，则为该树左孩子
　　q=q->lchild;
　　else //否则为右孩子
　　q=q->rchild;
　　} //将新结点插入树中
　　if(f->data.x>target)
　　f->lchild=s;
　　else
　　f->rchild=s;
　　}

第9题：

下图所示平衡二叉树(树中任一结点的左右子树高度之差不超过1)中，结点A的右子树AR高度为h，结点B的左子树BL高度为h，结点C的左子树CL、右子树CR高度都为h-1。若在CR中插入一个结点并使得CR的高度增加1，则该二叉树(61)。

A．以B为根的子二叉树变为不平衡

B．以C为根的子二叉树变为不平衡

C．以A为根的子二叉树变为不平衡

D．仍然是平衡二叉树


正确答案：C
解析：本题考查平衡查找树。由于平衡二叉树中任一结点的左右子树高度之差不超过1，因此，若在CR中插入一个结点并使得CR的高度增加1，则结点C的左右子树高度之差为-1，同时以C为根的子树高度增加了1，所以结点B的左右子树高度之差变为-1。如此一来，A的左子树的高度为h+2、右子树的高度为h，根据定义，以A为根的子二叉树变为不平衡。

第10题：

由元素序列(27,16,75,38,51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)为(46)。

A．27

B．38

C．51

D．75


正确答案：D
解析：平衡二叉树(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的结点。

更多相关问题
相关内容