二叉树删除指定节点
【摘要】 二叉树-删除节点(1)如果删除的节点是叶子节点,则删除该节点 。(2)如果删除的节点是非叶子节点,则删除该子树。(3)测试,删除掉5号叶子节点和3号。思路分析(1)首先考虑如果树是空树root,如果只有一个root结点,则等价将二叉树置空。(2)因为我们的二叉树是单向的,所以我们要判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点。(3)如果当前结点的左子节点不...
二叉树-删除节点
(1)如果删除的节点是叶子节点,则删除该节点 。
(2)如果删除的节点是非叶子节点,则删除该子树。
(3)测试,删除掉5号叶子节点和3号。
思路分析
(1)首先考虑如果树是空树root,如果只有一个root结点,则等价将二叉树置空。
(2)因为我们的二叉树是单向的,所以我们要判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点。
(3)如果当前结点的左子节点不为空,并且左子节点就是要删除的节点,就将this.left = null;结束递归删除。
(4)如果当前结点的右子节点不为空,并且右子节点就是要删除的节点,就将this.right = null;结束地柜删除。
(5)如果第三步和第四步没有删除结点,那么我们就需要向左子树进行递归删除。
(6)如果第五步也没有删除结点,则应该向右子树进行递归删除。
案例
public class BinaryTreeDemo{
public static void main(String[] args) {
//在 BinaryTreeDemo 类增加测试代码:
//测试一把删除结点
System.out.println("删除前,前序遍历");
binaryTree.preOrder(); // 1,2,3,5,4
binaryTree.delNode(5);
//binaryTree.delNode(3);
System.out.println("删除后,前序遍历");
binaryTree.preOrder(); // 1,2,3,4
}
}
public void delNode(int no) {
//如果当前结点的左子节点不为空,并且左子节点就是要删除的节点,就将this.left = null;结束递归删除
if(this.left != null && this.left.no == no) {
this.left = null;
return;
}
//如果当前结点的右子节点不为空,并且右子节点就是要删除的节点,就将this.right = null;结束地柜删除
if(this.right != null && this.right.no == no) {
this.right = null;
return;
}
//如果第三步和第四步没有删除结点,那么我们就需要向左子树进行递归删除
if(this.left != null) {
this.left.delNode(no);
}
//如果第五步也没有删除结点,则应该向右子树进行递归删除
if(this.right != null) {
this.right.delNode(no);
}
}
//在 BinaryTree 类增加方法
//删除结点
public void delNode(int no) {
if(root != null) {
//如果只有一个 root 结点, 这里立即判断 root 是不是就是要删除结点
if(root.getNo() == no) {
root = null;
} else {
//递归删除
root.delNode(no);
}
}else{
System.out.println("空树,不能删除~");
}
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)