二叉查找树的查找效率与二叉树的树型 有关, 在 ()时其查找效率最低 试题三（共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/21151.html
