递归添加元素问题

Question

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的时候就是可以正常的创建元素并挂到树上

Answer 1

liuyubobobo 2018-12-02 14:02:29

你的这个二分搜索树添加节点的代码片段是有问题的：

首先：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;
}

• 提问者 无心铁憨憨 #1

  public void add(E e) {
  
          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;
      }
  
  这样写，结果也还是一样，每次node都是为null

• liuyubobobo 回复 提问者 无心铁憨憨 #2

  我在上面补充了代码：）

• 提问者 无心铁憨憨 回复 liuyubobobo #3

  我.................谢谢老师