请问老师关于向二分搜索树中添加元素的问题
来源：6-3 向二分搜索树中添加元素
精慕门6573819
2019-08-28
关于这段代码，假如我添加一个元素，根据递归的逻辑，假如找到node.left为null，然后将元素添加到这个null的位置，这个时候程序执行是不是就结束了？但是由于递归已经把原二分搜索树给分解成了规模更小的问题，也就是分成了多棵树，但最后有没有把这棵树再给拼装起来呢？
写回答
1回答
-
准确的说，没有结束，因为return的过程还会层层调用回去。但是，每层调用回去，不会做任何事情了。
不需要“拼”。
我要想在以 node 为根节点的二分搜索树上添加一个元素，需要或者在以node->left 为根节点的二分搜索树上添加一个元素；或者在以node->right 为根节点的二分搜索树上添加一个元素。
在以以node->left 为根节点的二分搜索树上添加一个元素；或者在以node->right 为根节点的二分搜索树上添加一个元素以后，就等同于在以node为根节点的二分搜索树上添加了元素
因为，这个过程，node和node->left和node->right没有断裂。从node转向node->left或者node->right，只是我们不再看node了而已，但是，整棵树没有被我们拆看，也就没有必要“拼接”。
这一小节的代码，和下一小节的代码，核心是递归的终止条件不同，导致了逻辑上的区别。一个终止到node为空的情况（下一小节），一个终止到待添加位置的父亲节点（这一小节）。
请仔细比较这两小节的代码，对理解递归很重要：）
加油！：）
012019-08-28
相似问题