第1题
typedef struet BSTNode{//二叉排序树的结点结构
int data; //数据域
struct BSTNode*lchild,*rchild;//左、右孩子指针
}BSTNode,*BSTree;
设计递归算法,统计一棵二叉排序树T中值小于a的结点个数。
第2题
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。
【说明】
二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树:
●若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值;
●若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值;
●左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构,链表结点类型定义如下:
typedefstructBiTnode{
intkey_value;/*结点的键值,为非负整数*/
structBiTnode*left,*right;/*结点的左、右子树指针*/
}*BSTree;
函数find_key(root,key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到,则返回空指针。
【函数】
BSTreefind_key(BSTreeroot,intkey)
{
if((1))
returnNULL;
else
if(key==root->key_value)
return(2);
elseif(keykey_value)
return(3);
else
return(4);
}
【问题1】
请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。
【问题2】
若某二叉查找树中有n个结点,则查找一个给定关键字时,需要比较的结点个数取决于(5).
第6题
设二叉树以二叉链表方式存储,试完成下列问题的递归算法。 设二叉树结点和二叉树结构体定义如下: typedef struct btnode { ElemType element; struct btnode* lchild, *rchild; }BTNode; typedef struct binarytree{ BTNode* root; }BinaryTree; (1)求一棵二叉树的高度; int Depth(BTNode *p) { int lh, rh; if (!p) return 0; lh = ______________; rh = _____________; if (lh > rh) return _________; else return ________; } int DepthofBT(BinaryTree Bt) { return ___________; } (2)求一棵二叉树中的结点个数; int Size(BTNode * p) { if (!p) return _____ ; else return Size(p->lchild)+______________+1; } int SizeofBT(BinaryTree Bt) { return ______________); } (3)交换一棵二叉树中每个结点的左、右子树。 void exchange ( BTNode * p) { if(!p) return; if ( p->lchild != NULL || p->rchild != NULL ) { temp = p->lchild; p->lchild = ____________; p->rchild = temp; exchange (___________ ); exchange ( p->rchild ); } } void exchange(BinaryTree *bt) { ____________________; }
第7题
【Test-9-3】假设二叉树存放于二叉链表中,树中结点的关键字值互不相同。下面算法的功能是:判别给定的二叉树是否二叉排序树。请在空白处填入正确的语句。 void binSearchTree(BiTNode *t, BiTNode *&pr, int& bs) { //在以 t 为根的子树中判断该子树是否二叉排序树。是则引用参数 bs 为 1,否则 bs //为 0。引用参数 pr 是当前子树根结点 t 的前驱指针,在主调程序中应为各参数初 //始化: t 赋予根结点指针 root, pr 赋予 NULL, bs 赋予 1。 if(t != NULL && bs) { _______________①_________________; //递归到左子树判断 if(pr == NULL) { pr = t; //t 为中序第一个结点 bs = 1; } else { if(__________②___________) { pr = t; bs = 1; } else bs = 0; } if(bs) ____________③__________________; //递归到右子树判断 } }
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!