递归添加元素问题
来源：6-3 向二分搜索树中添加元素
无心铁憨憨
2018-12-02
if(node == null){
node = new Node(e);
size ++ ;
}
if(node.e.compareTo(e) < 0 && node.left == null){
node.left = new Node(e);
}
if(node.e.compareTo(e) > 0 && node.right == null){
node.right = new Node(e);
}
if(node.e.compareTo(e) < 0 ){
add(node.left,e);
}
if(node.e.compareTo(e) > 0){
add(node.right,e);
}
我在前序遍历章节中添加元素之后打印，发现没有任何元素打印，然后DEBUG添加操作之后发现每次执行的时候node都是null，不知道是什么原因，还有，虽然我自己还没有实现非递归添加元素方式，但是看了别人的代码，有一个地方不是很理解
Node sue = null;
sue = this.root;
if(e.compareTo(sue.e) < 0){
sue = sue.left;
}
if(e.compareTo(sue.e) > 0){
sue = sue.right;
}
这是什么意思
补充：刚刚发现，如果是在递归add方法中判断node == null的话，每次都是为null，但是在
add方法中判断root是否为null的时候就是可以正常的创建元素并挂到树上
1回答
-
liuyubobobo
2018-12-02
你的这个二分搜索树添加节点的代码片段是有问题的：
首先：node为空时，没有返回；
其次：递归调用add时，需要用node.left或者node.right接add的返回值。
在修改上面两个bug以后，整体逻辑还可以化简。（前两个if没有用）
请再仔细学习课程中讲解的逻辑，仔细研究课程中的代码和你写的代码的逻辑区别，课程的所有代码都可以通过课程官方github获得，传送门：https://github.com/liuyubobobo/Play-with-Data-Structures
关于“递归调用add时，需要用node.left或者node.right接add的返回值这一点”，在链表中是同理的。可以尝试先实现一下链表的递归实现？：）
可以参考一下问答：
https://coding.imooc.com/learn/questiondetail/72115.html
https://coding.imooc.com/learn/questiondetail/90910.html
http://coding.imooc.com/learn/questiondetail/88146.html
关于非递归，我没有理解你不理解的地方在哪里？如果是sue = sue.left; 和 sue = sue.right;，这个过程和链表的添加是一样的。回忆一下，在链表的添加过程中，我们要首先找到待添加元素的前一个节点，然后进行添加。在二分搜索树的添加过程中，我们要找到待添加元素的父亲节点，然后添加。只不过二分搜索树每一个节点有两个指针，需要根据待添加元素的值和当前节点的值，来判断往哪个方向走，一步步找到待添加元素的父亲节点：）
加油！：）
==========
补充代码：
public void add(E e) { root = add(root, e); // 这里的返回值也要接住啊！ } private Node add(Node node, E e) { if (node == null) { size++; return new Node(e); } if (e.compareTo(node.e) < 0) node.left = add(node.left, e); else if (e.compareTo(node.e) > 0) node.right = add(node.right, e); return node; }032018-12-02
相似问题