二叉树递归删除结点的两种写法

一、无返回值版本--尚硅谷韩老师version

结点类

class Node {
  public void delNode(int no){
        // 2. 如果当前节点的左节点不为空，并且左节点就是删除节点，就将this.left = null; 并且就返回（结束递归删除）
        if (this.left != null && this.left.no == no){
            this.left = null;
            return;
        }
        // 3. 如果当前节点的右节点不为空，并且左节点就是删除节点，就将this.left = null; 并且就返回（结束递归删除）
        if (this.right != null && this.right.no == no){
            this.right = null;
            return;
        }
        // 4. 我们需要向左子树递归
        if (this.left != null){
            cnt++;
            this.left.delNode(no);
        }
        // 5. 我们需要向右子树递归
        if (this.right != null){
            cnt++;
            this.right.delNode(no);
        }

    }
}

连接类

class BinaryTree {
  // ...
  // 删除节点--韩老师代码
    public void delNode(int no){
        if (root != null){
            // 如果只有一个root节点，这里要立即判断root是不是就是要删除的节点
            if (root.getNo() == no){
                root = null;
            } else {
                root.delNode(no);
                System.out.println("遍历的节点数："+root.getCnt());
            }
        } else{
            //
            System.out.println("空树，不能删除！");;
        }
    }
}

二、有返回值版本--DIY版本

其实删除操作就是在查找操作之上再做文章，还是脑海中要有三序遍历的框架

三序遍历框架：

public void threeOrderTraverse(){
   System.out.println("前序遍历");
   if (this.left != null) {
     this.left.threeOrderTraverse();
   }
   System.out.println("中序遍历");
   if (this.right != null) {
     this.right.threeOrderTraverse();
   }
   System.out.println("后序遍历");
}

三序查找框架（三序遍历框架2.0）

具体的查找代码为

if ( this.no == no ) {
   return this;
}

整体代码为

public Node threeOrderSearch(int no){
   /*
   // 前序查找
  */
   Node resNode = null;  // 返回变量
   if (this.left != null) {
     resNode = this.left.threeOrderSearch(no);
   }
   // 拦截代码
   if (resNode != null) {
      return resNode;
   }
   /*
   // 中序查找
   */
   if (this.right != null) {
     resNode = this.right.threeOrderSearch(no);
   }
   /*
   // 后序查找
   */
}

---

以下就是具体的删除代码，返回类型从查找的返回Node类型改为返回boolean类型

---

结点类

class Node {
  // ...
  public boolean preOrderDelete(int no){
        if (this.left != null && this.left.no == no){
            this.left = null;
            return true;
        } else if (this.right != null && this.right.no == no){
            this.right = null;
            return true;
        }

        boolean isFind = false;
        if (this.left != null) {
            isFind = this.left.preOrderDelete(no);
        }
        if (isFind){ //
            return true;
        }

        // 否则进行右子结点的递归
        if (this.right != null){
            isFind = this.right.preOrderDelete(no);
        }

        return isFind;
    }
}

连接类：

class preorderDelete(int no){
  // 删除节点--DIY
    public void preorderDelete(int no){
        if (root != null){
            // 如果只有一个root节点，这里要立即判断root是不是就是要删除的节点
            if (root.getNo() == no){
                root = null;
            } else {
                boolean isFind;
                isFind = root.preOrderDelete(no);
                if (isFind){
                    System.out.println("已删除节点！");
                    System.out.println("遍历的节点数："+root.getCnt());
                } else {
                    System.out.println("查无此节点！");
                }
            }
        } else{
            //
            System.out.println("空树，不能删除！");;
        }
    }
}

三、比较两种删除写法的效率

相比之下，有返回值的写法效率会很多，因为它具有拦截功能，在找到要删除的结点后不会再往下右搜索，而不带返回值的写法会继续往右搜索。