BST中的 insert 方法非递归实现
来源：5-3 二分搜索树的节点插入
Karen_Ng
2017-05-02
Node* __insert2(Node* node, Key key, Value value){
Node* tmpNode = node;
while(true){
if (tmpNode == NULL){
tmpNode = new Node(key, value);
count++;
break;
}
if( key == tmpNode->key)
tmpNode->value = value;
break;
if( key < tmpNode->key )
tmpNode = tmpNode->left;
else
tmpNode = tmpNode->right;
}
return tmpNode;// 这里应该 return tmpNode 还是 node 本身？
}这是我理解的非递归实现，但是总感觉有什么不对，还请老师指点（我看了一下后面的测试用例，一步步调试还是没搞清楚最后 return 的 node 应该是哪一个）
写回答
2回答
-
使用非递归的时候，就不需要返回值了，也不需要写辅助函数__insert了，直接在可以对外调用的函数insert中，使用循环的方式找到待插入位置的父亲节点，然后让父亲节点的左孩子或者右孩子指向一个新的节点就好了。再想想看：）加油！
012017-05-09 -
Karen_Ng
提问者
2017-05-09
template <typename Key, typename Value> void insert(Node* node, Key key, Value value) { Node *prev = NULL; Node *current = node; // 查找插入位置 while (current != NULL) { prev = current; if (key < current->key) current = current->left; else current = current->right; } //插入节点 newNode Node* newNode = new Node(key, value); if (prev==NULL) node = newNode; else if (newNode->key < prev->key) prev->left = newNode; else prev->right = newNode; }谢谢波波的解释，我重新改写了之前的算法，但是我总感觉少了点什么，又看不出来，QAQ
022018-01-04
相似问题