二叉查找树的查找效率与二叉树的树型 有关, 在 ()时其查找效率最低 试题三(共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: }
2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/43873.html