关于二分搜索树插入操作的返回值问题
来源：5-4 二分搜索树的查找
怀瑜
2017-11-27
Node* insert(Node* root, Key key,Value value) { if (!root) {//root==NULL时，直接插入 count++; return new Node(key, value); } if (key == root->key){ root->value = value; return root;//返回根节点 } else if (key > root->value) root->right = insert(root->right, key, value); else root->left = insert(root->left, key, value); //return root;//返回根节点 } 请问老师在这里我将返回根节点的语句放在了if(key==root->key)后面，是否正确？我想的最后的return语句也是在执行到key==root->key才能执行到，放在这个地方和老师您的那个地方区别应该只在于是在上一步return还是在下一步return，请问老师这种想法对吗？
1回答
-
你的这个函数有的时候有返回值，有的时候没有返回值。在调用：
root->right = insert(root->right, key, value);
或者
root->left = insert(root->left, key, value);
接到一个空值。
这个逻辑和我的代码逻辑不等价：）在我的代码逻辑下，这个函数永远有返回值。请注意这个递归函数的语意：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/03-Binary-Search-Tree-Insert/main.cpp
// 向以node为根的二分搜索树中, 插入节点(key, value), 使用递归算法 // 返回插入新节点后的二分搜索树的根 Node* insert(Node *node, Key key, Value value)
可以尝试自己测试一下这个函数，向树中添加10个值，再用树的遍历的形式打印出来看看：）
另：劳烦下一次贴代码请使用慕课网的代码语言block形式编辑代码。
012021-05-31
相似问题