BST中的 insert 方法非递归实现

Question

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

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

  为啥格式是这样子？