没有合适的资源?快使用搜索试试~ 我知道了~
208-习题作业-作业十七1
需积分: 0 0 下载量 8 浏览量
2022-08-04
11:27:55
上传
评论
收藏 65KB PDF 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/86320909/0001-c871c2c0be710123628b5f5ec47769e7_thumbnail.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
3页
208-习题作业-作业十七1
资源详情
资源评论
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/86320909/bg1.jpg)
将二叉查找树类中的插入、删除和查找函数改成非递归函数。
【解】插入操作的实现见代码清单
8-13
。先为被插入的元素申请一个结点(第
3
行)。最简单
的情况是当前的树为空,那么插入元素被作为根结点(第
5
行)。第
7
行开始考虑一般的情
况。从根结点开始往下寻找。如果
x
大于当前结点,
x
应该插入到右子树上,所以检查当前
结点有没有右孩子。如果有右孩子,则将当前结点设为右孩子,继续寻找,否则
x
插入为当
前结点的右孩子。如果
x
不大于当前结点,
x
应该插入到左子树上,所以检查当前结点有没
有左孩子。如果有左孩子,则将当前结点设为左孩子,继续寻找,否则
x
插入为当前结点的
左孩子。
代码清单
8-13
插入操作的非递归实现
1. template <class Type>
2. void BinarySearchTree<Type>::insert(const Type &x)
3. { BinaryNode* nd = new BinaryNode(x, NULL, NULL); // 为插入元素申请结点
4.
5. if (root == NULL) { root = nd; return; } // 在空树上插入
6.
7. BinaryNode* now = root;
8. while (true) { // 寻找插入位置并插入
9. if (x > now->data){
10. if( now->right == NULL ){
11. now->right = nd;
12. break;
13. }
14. now = now->right;
15. }
16. else if ( now->left == NULL ) {
17. now->left = nd;
18. break;
19. }
20. else now = now->left;
21. }
22. }
查找操作是最简单的一个操作,它的实现见代码清单 8-14。它也是从根结点按层往下
查找的过程。如果被查找的元素 x 大于当前结点,x 应该在右子树上,将当前结点设为右孩
子,继续寻找。如果 x 小于当前结点,x 应该在左子树上,将当前结点设为左孩子,继续寻
找。如果 x 等于当前结点,返回 true 表示找到。如果在寻找的过程中发现当前结点是空结点,
表示 x 不存在,返回 false。
代码清单
8-14
查找操作的非递归实现
1. template <class Type>
2. bool BinarySearchTree<Type>::find(const Type &x) const
3. { BinaryNode* now = root;
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![avatar](https://profile-avatar.csdnimg.cn/9d907a8d736541679694c8ec7ac863fe_weixin_35795512.jpg!1)
韩金虎
- 粉丝: 29
- 资源: 285
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)
评论0