首先将 28, 23, 54, 61, 98, 37 插入一棵初始为空的平衡二叉树（AVL树），然后马上插入下列选项中的一个键值。哪个键值将引起 RL 旋转？A．10B．50C．80D．100
首先将 28, 23, 54, 61, 98, 37 插入一棵初始为空的平衡二叉树（AVL树），然后马上插入下列选项中的一个键值。哪个键值将引起 RL 旋转？
A．10
B．50
C．80
D．100
参考答案和解析
C
相关考题：
在平衡二叉树中插入一个结点后引起了不平衡,设最低(最接近于叶子)的不平衡点是A,并已知A的左、右孩子的平衡因子分别为－1和0,则应进行的平衡旋转是() A.LL型B.LR型C.RL型D.RR型
下图所示平衡二叉树(树中任一结点的左右子树高度之差不超过1)中，结点A的右子树AR高度为h，结点B的左子树BL高度为h，结点C的左子树CL、右子树CR高度都为h-1。若在CR中插入一个结点并使得CR的高度增加1，则该二叉树(61)。A．以B为根的子二叉树变为不平衡B．以C为根的子二叉树变为不平衡C．以A为根的子二叉树变为不平衡D．仍然是平衡二叉树
● 下图所示平衡二叉树（树中任一结点的左右子树高度之差不超过 1）中，结点 A的右子树 AR 高度为 h，结点 B 的左子树 BL 高度为 h，结点 C 的左子树 CL、右子树 CR高度都为h-1。若在CR中插入一个结点并使得CR的高度增加1，则该二叉树 （61） 。（61）A. 以B 为根的子二叉树变为不平衡B. 以C 为根的子二叉树变为不平衡C. 以A 为根的子二叉树变为不平衡D. 仍然是平衡二叉树
阅读以下说明、C函数和问题，将解答填入答题纸的对应栏内。【说明】二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：●若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值;●若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值;●左、右子树本身就是二叉查找树。设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：typedefstructBiTnode{intkey_value;/*结点的键值，为非负整数*/structBiTnode*left,*right;/*结点的左、右子树指针*/}*BSTree;函数find_key(root,key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到，则返回空指针。【函数】BSTreefind_key(BSTreeroot,intkey){if((1))returnNULL;elseif(key==root-key_value)return(2);elseif(keykey_value)return(3);elsereturn(4);}【问题1】请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。【问题2】若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于(5).
阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树。 （1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值。 （2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值。 （3）左、右子树本身就是两棵二叉查找树。 二叉查找树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起来的，具体的过程是：每读入一个元素，建立一个新结点，若二叉查找树非空，则将新结点的值与根结点的值相比较，如果小于根结点的值，则插入到左子树中，否则插入到右子树中；若二叉查找树为空，则新结点作为二叉查找树的根结点。 根据关键码序列{46，25，54，13，29，91}构造一个二叉查找树的过程如图4-1所示。设二叉查找树采用二叉链表存储，结点类型定义如下： typedef int KeyType； typedef struct BSTNode{ KeyType key； struct BSTNode *left,*right； }BSTNode,*BSTree； 图4-1(g)所示二叉查找树的二叉链表表示如图4-2所示。图4-2 函数int InsertBST(BSTree *rootptr,KeyType kword)功能是将关键码kword插入到由rootptr指示出根结点的二叉查找树中，若插入成功，函数返回1，否则返回0。【C代码】 int lnsertBST(BSTree*rootptr，KeyType kword) /*在二叉查找树中插入一个键值为kword的结点，若插入成功返回1，否则返回0； *rootptr为二叉查找树根结点的指针 */ { BSTree p,father; (1) ; /*将father初始化为空指针*/ p=*rootptr; /*p指示二叉查找树的根节点*/ while(p （2） ){ /*在二叉查找树中查找键值kword的结点*/ father=p; if(kword＜p-＞key) p=p-＞left； else p=p-＞right； } if( (3) )return 0; /*二叉查找树中已包含键值kword，插入失败*/ p=(BSTree)malloc( (4) ); /*创建新结点用来保存键值kword*/ If(!p)return 0; /*创建新结点失败*/ p-＞key=kword； p-＞left=NULL； p-＞right=NULL； If(!father) (5) =p； /*二叉查找树为空树时新结点作为树根插入*/ else if(kword＜father-＞key) (6) ； /*作为左孩子结点插入*/ else (7) ； /*作右孩子结点插入*/ return 1； }/*InsertBST*/
试题三（共15分）阅读以下说明和C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。【说明】函数Insert _key (*root,key)的功能是将键值key插入到*root指向根结点的二叉查找树中（二叉查找树为空时*root为空指针）。若给定的二叉查找树中已经包含键值为key的结点，则不进行插入操作并返回0；否则申请新结点、存入key的值并将新结点加入树中，返回l。提示：二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：●若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；●若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；●左、右子树本身就是二叉查找树。设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：typedef struct BiTnode{int key _value; ／*结点的键值，为非负整数*／struct BiTnode *left,*right; ／*结点的左、右子树指针*／}BiTnode, *BSTree；【C函数】int Insert _key( BSTree *root,int key){BiTnode *father= NULL,*p=*root, *s;while( (1)＆＆key!=p-key_value){／*查找键值为key的结点*／father=p；if（key p-key_value）p= (2) ； ／*进入左子树*／else p= (3) ； ／木进入右子树*／}if (p) return 0； ／*二叉查找树中已存在键值为key的结点，无需再插入*／s= (BiTnode *)malloc( (4) )；／*根据结点类型生成新结点*／if (!s) return -1;s-key_value= key; s-left= NULL; s-right= NULL;if( !father)(5) ； ／*新结点作为二叉查找树的根结点*／else ／*新结点插入二叉查找树的适当位置*／if( key father-key_value)father-left = s;elsefather-right = s;retum 1：}
阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。【说明】二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树。（1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值。（2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值。（3）左、右子树本身就是两棵二叉查找树。二叉查找树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起来的，具体的过程是：每读入一个元素，建立一个新结点，若二叉查找树非空，则将新结点的值与根结点的值相比较，如果小于根结点的值，则插入到左子树中，否则插入到右子树中；若二叉查找树为空，则新结点作为二叉查找树的根结点。根据关键码序列{46，25，54，13，29，91}构造一个二叉查找树的过程如图4-1所示。设二叉查找树采用二叉链表存储，结点类型定义如下：typedef int KeyType；typedef struct BSTNode{KeyType key；struct BSTNode *left,*right；}BSTNode,*BSTree；图4-1(g)所示二叉查找树的二叉链表表示如图4-2所示。函数int InsertBST(BSTree *rootptr,KeyType kword)功能是将关键码kword插入到由rootptr指示出根结点的二叉查找树中，若插入成功，函数返回1，否则返回0。【C代码】int lnsertBST(BSTree*rootptr，KeyType kword)/*在二叉查找树中插入一个键值为kword的结点，若插入成功返回1，否则返回0；*rootptr为二叉查找树根结点的指针*/{BSTree p,father;(1) /*将father初始化为空指针*/p=*rootptr; /*p指示二叉查找树的根节点*/while(pif(kword＜p-＞key)p=p-＞left；elsep=p-＞right；}if((3))return 0; /*二叉查找树中已包含键值kword，插入失败*/ p=(BSTree)malloc((4)); /*创建新结点用来保存键值kword*/If(!p)return 0; /*创建新结点失败*/p-＞key=kword；p-＞left=NULL；p-＞right=NULL； If(!father)(5) =p； /*二叉查找树为空树时新结点作为树根插入*/elseif(kword＜father-＞key)(6)；/*作为左孩子结点插入*/else(7)；/*作右孩子结点插入*/return 1；}/*InsertBST*/
关于AVL(平衡二叉树)，下列说法错误的是()。A.左子树与右子树高度差最多为1B.插入操作的时间复杂度为0(logn)C.平衡二叉树是二叉排序树中的一种D.使用平衡二叉树的目的是为了节省空间
关于红黑树和AVL树，以下哪种说法不正确（）。A、两者都属于自平衡二叉树B、两者查找，插入，删除的时间复杂度相同C、包含n个内部节点的红黑树的高度是O（log（n））D、JDK的TreeMap是一个AVL的实现
问答题将关键字（45，87，30，33，63，27，51，76）依次插入到一棵初始为空的二叉排序树中。请回答：若在二叉排序树中插入新的关键字60，则为寻找插入位置，分别与哪些关键字进行比较。
判断题在任意一棵非空二叉树中，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉树排序树相同。A对B错