关于指针指向问题？

Question

bobo老师，在这个二分搜索树的插入元素的时候，当该树有多层的时候，我代入了小数据量去，但是仍然无法解决指针它是怎样指向它的左右孩子节点的呀，在这个指向过程它会有key值的比较，它不应该在相应节点的时候进行key值的比较嘛？挺疑惑的！

Answer 1

liuyubobobo 2021-03-31 05:18:54

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

这个 node 在每一次函数调用的过程中在变化呀。

Node* insert(Node *node, Key key, Value value){
      
    if( node == NULL ){
        count ++;
        return new Node(key, value);
    }
    
    // 在这打印 node 里的 key 值，看看当前的 key 到底在和谁做比较？
    ...
}

我不确定我是否正确理解了你的问题。如果还有疑问的话，看看你能否把问题改成如下形式：

你认为对于某个数据用例，在某一步逻辑里，应该发生什么？或者变量的取值应该是什么？但是实际却是什么？这是你无法理解的？

Answer 2

提问者 慕移动9586716 2021-03-31 09:28:33

老师，我把问题和数据放在图片中吧（这样好表达一点）

• liuyubobobo #1

  我们一步一步来。我们先讨论 node->left 是如何指向 40 这个问题。因为，在你画的这棵树上，root->left 已经指向 40 了。那 root->left 是什么时候指向 40 的？是在添加 40 这个节点的时候。
  
  所以现在，你用课程的代码，创建一棵空的 BST，先加入一个 70，再加入一个 40。加入这两个节点以后，70->left 就指向 40 了，你能不能理解这个过程？如果不能，就针对这两个节点的添加过程，你哪里不理解？
  
  （P.S. 这个课程可能不是特别适合你，这个课程的定位本身不是基础，参考这里：http://coding.imooc.com/learn/questiondetail/16248.html 我推荐你看一下是否需要学习一下这个课程，这个课程是我最新的算法课程，整体将桔梗基础，涵盖的内容也更丰富，对于递归过程的分析也更细致。但注意，使用的是 Java 语言：https://class.imooc.com/sc/105/learn）

• 提问者 慕移动9586716 回复 liuyubobobo #2

  瞬间恍然大悟了，这种感觉真好，原来如此，原来我思维被禁锢到这里了，谢谢bobo老师，在bobo老师的引导下我觉得我能学好这门课（前面的归并排序和快速排序都已经理解了并且能实现了），太感谢老师了！

• liuyubobobo 回复 提问者 慕移动9586716 #3

  赞！如果能理解这个课程前面介绍的归并和快排，那没问题的。加油！：）