本文共 1418 字，大约阅读时间需要 4 分钟。

二叉树之删除节点

思路分析

1. 要求：

• 如果删除的是叶子节点，那就直接删除该节点
• 如果删除节点时非叶子节点，那就直接删除该子树

2. 思路：

• 同单向链表的删除操作相同，仅仅找到当前节点是无法完成操作的，所以必须找到待删除节点的上一个节点
• 首先，链表是否为。不为空，观察根节点是否为待删除结点，是那就直接置空整个树。
• 判断当前节点的左子节点是否为空，然后判断是否为待删除结点，是就删除，退出。
• 然后再判断当前节点的右子节点是否为空，然后判定是否为待删除结点，是就删除，退出。
• 都没找到，对左子树进行递归循环
• 然后对右子树进行递归循环
• 最后没找到就退出

代码实现

BinaryTree类： public void delete(int no) {
           if (isEmpty()) {
               System.out.println("树为空");            return;        }        //判定是否仅仅只有根节点，是由根节点就退出程序        if (root.getHeroNo() == no) {
               root = null;            return;        }        this.root.delete(no);    }

HeroNode类：

public void delete(int no) {
           //判断左右子节点是否为空        if (this.left != null && this.left.getHeroNo() == no) {
                   //判定当前结点的左子节点是否为待删除结点，是的话删除推出                this.left = null;                return;        }        if (this.right != null && this.right.getHeroNo() == no) {
                   this.right = null;                return;        }        //左右子节点都不是那就分别进行左右递归循环        if (this.left != null) {
               this.left.delete(no);            //这里不能加return，因为可能没有找到        }        if (this.right != null) {
               this.right.delete(no);        }        return;        //达到最后一层，全是叶子结点，已经在上一轮遍历过了，就意味着完全退出    }

分析与总结：

1. 二叉树是单向的，所以要删除某结点就要找到待删除结点的前一个结点，同单向链表，所以用this.left或者this.right进行遍历
2. 同三种查找方式相同，没有找到。所有递归都走完没找到才是真的没找到。只要有一条路找到了，再找到的地方直接退出就行了。两个出口：全找完了，没找到；或者找到了。直接退出。
3. 调用子节点的相关信息是必须判定是否为空在进行使用。

转载地址：http://iqgpb.baihongyu.com/