BST中的 insert 方法非递归实现

Question

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 应该是哪一个）

Answer 1

liuyubobobo 2017-05-03 01:34:41

使用非递归的时候，就不需要返回值了，也不需要写辅助函数__insert了，直接在可以对外调用的函数insert中，使用循环的方式找到待插入位置的父亲节点，然后让父亲节点的左孩子或者右孩子指向一个新的节点就好了。再想想看：）加油！

• 提问者 Karen_Ng #1

  非常感谢！

Answer 2

提问者 Karen_Ng 2017-05-09 14:38:49

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

• 追风的云 #1

  /**
  	 * java 插入元素
  	 * 使用非递归的方式插入
  	 * @param key
  	 * @param value
  	 */
  	public void insert2(Key key, Value value){
  		if(root == null){
  			root = new Node(key, value);
  			return;
  		}
  		Node node = root;
  		while(node !=null){
  			if(key.compareTo(node.key) == 0){
  				node.value = value;
  				break;
  			}else if(key.compareTo(node.key) < 0){
  				if(node.left == null){
  					count++;
  					node.left = new Node(key, value);
  					break;
  				}
  				node= node.left;
  			}else{
  				if(node.right == null){
  					count++;
  					node.right = new Node(key, value);
  					break;
  				}
  				node = node.right;
  			}
  			
  		}
  	}

• 追风的云 #2

  为啥格式是这样子？