207-习题作业-作业十六1

在二叉查找树类中增加三个成员函数：删除小于某个指定值的所有元素，删除大于某个指

定值得所有元素，删除某一指定范围中的所有元素

【解】先看一下删除小于指定值

x

的操作

delLess

。这个操作可以用递归的观点来看。如果根结

点的值大于

x

，那么小于

x

根结点值小于

1. template <class Type>

2. void BinarySearchTree<Type>::delLess( const Type x )

3. { delLess(x, root); }

4.

5. template <class Type>

6. void BinarySearchTree<Type>::delLess( const Type x, BinaryNode *&t ){

7. if ( t==NULL ) return;

8. if ( t->data < x ) { // 删除根结点及左子树

9. BinaryNode *tmp = t;

10. t = t->right;

删除大于 x 的所有元素的过程与 delLess 基本类似，具体见代码清单 8-11。

代码清单

8-11

删除大于

x

的所有元素

1. template <class Type>

2. void BinarySearchTree<Type>::delGreat( const Type x )

3. { delGreat(x, root); }

4.

5. template <class Type>

6. void BinarySearchTree<Type>::delGreat( const Type &x, BinaryNode *&t )

7. { if ( t == NULL ) return;

14. }