当前位置:首页
>
查试题
>
阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。【说明】函数Insert_key(*root ,key)的功能是将键值 key 插入到*boot指向根结点的二叉查找树中(二叉查找树为空时 *root 为空指针)。若给定的二叉查找树中已经包含键值为 key 的结点,则不进行插入操作井返回 0;否则申请新结点、存入 key 的值并将新结点加入树中,返回1。提示:二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树:若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值;若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值;左、右子树本身就是二叉查找树。设二叉查找树采用二叉链表存储结构,链表结点类型定义如下: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; else father->right = s; return 1;}