关于指针left、right

Question

bobo老师，我们在结构体中定义了指向node的左指针和右指针，而在下面函数中：

 Node* insert(Node *node, Key key, Value value){

      if( node == NULL ){
          count ++;
          return new Node(key, value);
      }

      if( key == node->key )
          node->value = value;
      else if( key < node->key )
          node->left = insert( node->left , key, value); //这里是如何实现将left指向该节点的左孩子的呢？
      else    // key > node->key
          node->right = insert( node->right, key, value);//这里又是如何实现将right指向该节点的右孩子的呢？

      return node;
  }
  

//它是本来就可以指向它相应的左右孩子的嘛？还是怎样？

Answer 1

liuyubobobo 2021-03-27 18:58:43

想象我们现在整棵树中只要一个节点，是根节点。比如根节点的值是 10。

现在，如果我们向这棵树中添加一个节点，比如 8 吧。

首先运行 insert，node 是 root，进入下面的 key 和 node->key 的比较。

因为 key 是 8，node->key 是 10，所以走：node->left = insert( node->left , key, value);

因为 node->left 是空，这次 insert 的执行，会直接运行 if(node == null) 的部分，相当于新创建一个节点，然后返回去。

返回取得节点被 node->left = insert( node->left , key, value); 接住，相当于让 root->left 链接了一个新节点。

==========

你可以使用这种方式，实际的去玩儿一下这个代码，向这棵树中添加节点，然后仔细观察，程序中的每一个变量，每一个节点，他们的 left 和 right 在怎样变化，为什么这个节点可以被添加上。这是学习算法，乃至学习计算机的重要方式，而不是对着代码生想。

另外，这个课程其实并不适合算法与数据结构初学。你可以根据需要，看一下是否需要这个课程，其中涵盖的内容更丰富，同时对注入你的问题这类底层运行机制，介绍的也更清晰。比如对与这类递归过程的运行，you风场详细的微观解读。https://class.imooc.com/sale/datastructure

继续加油！：）

• 提问者 慕移动9586716 #1

  非常感谢！

Answer 2

提问者 慕移动9586716 2021-03-28 10:07:29

懂了，谢谢老师