请问老师关于向二分搜索树中添加元素的问题

Question

关于这段代码，假如我添加一个元素，根据递归的逻辑，假如找到node.left为null，然后将元素添加到这个null的位置，这个时候程序执行是不是就结束了？但是由于递归已经把原二分搜索树给分解成了规模更小的问题，也就是分成了多棵树，但最后有没有把这棵树再给拼装起来呢？

Answer 1

liuyubobobo 2019-08-28 15:42:23

准确的说，没有结束，因为return的过程还会层层调用回去。但是，每层调用回去，不会做任何事情了。

不需要“拼”。

我要想在以 node 为根节点的二分搜索树上添加一个元素，需要或者在以node->left 为根节点的二分搜索树上添加一个元素；或者在以node->right 为根节点的二分搜索树上添加一个元素。

在以以node->left 为根节点的二分搜索树上添加一个元素；或者在以node->right 为根节点的二分搜索树上添加一个元素以后，就等同于在以node为根节点的二分搜索树上添加了元素

因为，这个过程，node和node->left和node->right没有断裂。从node转向node->left或者node->right，只是我们不再看node了而已，但是，整棵树没有被我们拆看，也就没有必要“拼接”。

这一小节的代码，和下一小节的代码，核心是递归的终止条件不同，导致了逻辑上的区别。一个终止到node为空的情况（下一小节），一个终止到待添加位置的父亲节点（这一小节）。

请仔细比较这两小节的代码，对理解递归很重要：）

加油！：）

• 提问者 精慕门6573819 #1

  非常感谢！