1回答

liuyubobobo

2017-08-08

在这个课程的实现中，最外层调用的insert是没有返回值的：

// 向二分搜索树中插入一个新的(key, value)数据对    
void insert(Key key, Value value){    
    root = insert(root, key, value);    
}

相应的insert的具体实现，在这个课程中均使用递归实现。以insert为例，我们BST类内部的私有成员函数insert的定义如下：

// 向以node为根的二分搜索树中, 插入节点(key, value), 使用递归算法    
// 返回插入新节点后的二分搜索树的根    
Node* insert(Node *node, Key key, Value value)

 

在这里，要注意，我的实现是基于我对insert的定义的，事实上，你完全可以设计一个insert的递归实现，不需要返回值，但是insert里的逻辑都要相应的调整。不妨试试看：）

另外，insert逻辑本身也可以很容易的修改为非递归的实现，也强烈建议自己试试看，对于理解二分搜索树，递归和非递归，都是非常好的练习。事实上，这一章的所有算法都可以使用非递归的方式实现，强烈建议自己试试看：）

通过这些思考和练习，希望能够更深刻的体会，算法的实现不是一成不变的，不是那一种实现一定是对的，很多种实现思路都是对的，关键是自己如何定义自己的算法函数，之后在具体实现时，要维护这个定义。

最后，关于递归返回值的问题，对于remove函数也有其他同学问过，不妨参考：http://coding.imooc.com/learn/questiondetail/18441.html

通过这些思考和练习，希望能够更深刻的体会，算法的实现不是一成不变的，不是那一种实现一定是对的，很多种实现思路都是对的，关键是自己如何定义自己的算法函数，之后在具体实现时，要维护这个定义。

0

0