精华内容
下载资源
问答
  • 用Java语言实现二叉树删除结点
    2021-02-27 22:41:12

    首先定义结点类 class Node :

    public class Node {

    public Node leftchild=null;

    public Node rightchild=null;

    public Node parent=null;

    }

    然后再定义二叉树类 class Btree

    public class Btree{

    // 删除值为val的节点

    public void delete(Integer val) {

    //先找到值为val的结点,调用函数Search(val)

    Node p = this.Search(val);

    //找到节点后进行删除

    //如果右孩子不为空,那么找到右孩子树中最小的值的结点,与节点的值进行交换,然后后继结点结点的父亲的孩子指向他的右孩子。在此用到了中序后继函数successor

    //(val),下面有定义。

    if (p.rightchild != null) {

    Node succ = this.successor(val);

    Integer i = p.value;

    p.value = succ.value;

    succ.value = i;

    //既然找到后继结点即最小值的结点,那么他就没有左孩子。

    if (succ == succ.parent.leftchild)

    succ.parent.leftchild = succ.rightchild;

    if (succ == succ.parent.rightchild)

    succ.parent.rightchild = succ.rightchild;

    }

    //如果右孩子为空,找其父亲,

    //如果是父亲的左孩子,那么直接让父亲的左孩子指向此节点的左孩子即直接将此节点删除

    //如果是父亲的右孩子,那么直接让父亲的右孩子指向此节点的左孩子即直接将节点删除

    //最后孩子的父亲指向此节点的父亲,实现双向指向

    else {

    if ( p.parent.leftchild==p)

    p.parent.leftchild = p.leftchild;

    if ( p.parent.rightchild==p)

    p.parent.rightchild = p.leftchild;

    p.leftchild.parent = p.parent;

    }

    }

    // 找到此节点,用到递归

    public Node Search(Integer val) {

    return this.search(this.root, val);

    }

    public Node search(Node p, Integer val) {

    if (p == null)

    return null;

    else {

    if (p.value == val) {

    return p;

    }

    else {

    if (p.value < val) {

    return search(p.rightchild, val);

    } else {

    return search(p.leftchild, val);

    }

    }

    }

    }

    // 找到此节点的中序后继,中序后继:就是比此节点大的最小值,在此处用到了min(p.rightchild),下面有定义。顺便说一句:前驱:比此节点小的最大值,其操作和min函数

    //类似

    public Node successor(Integer val) {

    Node p = this.Search(val);

    if (p.rightchild != null) {

    return this.min(p.rightchild);

    }

    else {

    while (p.parent != null) {

    if (p == p.parent.leftchild)

    break;

    p = p.parent;

    }

    return p.parent;

    }

    }

    // 找到后继树中最小的节点

    public Node min(Node r) {

    if (r == null)

    return null;

    else {

    while (r.leftchild != null) {

    r = r.leftchild;

    }

    return r;

    }

    }

    }

    最后是主函数类 class Main

    public class Main {

    public static void main(String[] args) {

    Btree b =new Btree();

    Integer[] data={3,2,5,4,8,7,9};

    for(Integer i=0;i

    b.insert(data[i]);//insert(val)函数详见链接点击打开链接

    }

    b.preTravel();//二叉树的三种遍历,详见链接点击打开链接

    b.inTravel();

    b.postTravel();

    b.delete(8);

    b.preTravel();

    b.inTravel();

    b.postTravel();

    }

    }

    更多相关内容
  • 二叉树删除节点

    2022-02-06 17:27:08
    二叉树删除节点 完成删除结点的操作 规定:①如果删除的结点是叶子结点,则删除该结点    ②如果删除的结点是非叶子结点,则删除该子树 思路: 1.考虑如果树是空树root,如果只有一个root结点,则等价将二叉树置空...

    二叉树删除节点

    完成删除结点的操作
    规定:①如果删除的结点是叶子结点,则删除该结点
       ②如果删除的结点是非叶子结点,则删除该子树
    思路:
    1.考虑如果树是空树root,如果只有一个root结点,则等价将二叉树置空。
    2.因为二叉树数单向的,所以判断当前结点的子结点是否需要删除结点,而不能去判断当前结点是不是需要删除的结点。
    3.如果当前结点的左子结点不为空,并且左子结点就是要删除的结点,就将this.left = null;并且就返回(结束递归删除)
    4.如果当前结点的右子结点不为空,并且右子结点就是要删除的结点,就将this.right = null;并且就返回(结束递归删除)
    5.如果第3步和第4步没有删除的结点,那么就需要向左子树进行递归删除
    6.如果第5步也没有删除的结点,则应当向右子树进行递归删除

    public class BinaryTreeDemo {
        public static void main(String[] args) {
            BinaryTree binaryTree = new BinaryTree();
            HeroNode root = new HeroNode(1,"宋江");
            HeroNode node1 = new HeroNode(2,"吴用");
            HeroNode node2 = new HeroNode(3,"卢俊义");
            HeroNode node3 = new HeroNode(4,"林冲");
            HeroNode node4 = new HeroNode(5,"关胜");
            root.setLeft(node1);
            root.setRight(node2);
            node2.setRight(node3);
            node2.setLeft(node4);
            binaryTree.setRoot(root);
            System.out.println("结点删除前的二叉树");
            binaryTree.preOrder();
            binaryTree.delNode(5);
            System.out.println("结点删除后的二叉树");
            binaryTree.preOrder();
        }
    }
    class BinaryTree{
        HeroNode root;
        public void setRoot(HeroNode root){
            this.root = root;
        }
        public void preOrder(){
            if (this.root != null){
                this.root.preOrder();
            }else{
                System.out.println("当前二叉树为空,无法遍历");
            }
        }
        public void delNode(int no){
            if (root != null){
                if(root.getNo() == no){
                    root = null;
                }else{
                    root.delNode(no);
                }
            }else{
                System.out.println("该二叉树为空,无法删除");
            }
        }
    }
    
    class HeroNode{
        private int no;
        private String name;
        private HeroNode left;
        private HeroNode right;
    
        public HeroNode(int no, String name) {
            this.no = no;
            this.name = name;
        }
    
        public int getNo() {
            return no;
        }
    
        public void setNo(int no) {
            this.no = no;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public HeroNode getLeft() {
            return left;
        }
    
        public void setLeft(HeroNode left) {
            this.left = left;
        }
    
        public HeroNode getRight() {
            return right;
        }
    
        public void setRight(HeroNode right) {
            this.right = right;
        }
    
        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
    
        //编写前序遍历的方法
        public void preOrder(){
            System.out.println(this);
            if (this.left != null){
                this.left.preOrder();
            }
            if (this.right != null){
                this.right.preOrder();
            }
        }
    
        public void delNode(int no){
            if (this.left != null && this.left.no == no){
                this.left = null;
                return;
            }
            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);
             }
        }
    }
    

    结果如下:
    在这里插入图片描述
    若要删除的结点是非叶子结点,现在不将非叶子结点为根结点的子树删除,而是做如下操作:
    如果要删除的结点有一个子结点,则将该子结点替代为删除结点,如果要删除的结点既有左结点又有右结点,则将左结点替代为要删除的结点。

    关键代码如下:

     public void delNode(int no){
            if (this.left != null && this.left.no == no){
                if (this.left.left != null && this.left.right == null){
                    this.left = this.left.left;
                    return;
                }
                if (this.left.right != null && this.left.left == null){
                    this.left = this.left.right;
                    return;
                }
                if (this.left.left != null &&this.left.right != null){
                    HeroNode thisRight = this.left.right;
                    this.left = this.left.left;
                    this.left.right = thisRight;
                    return;
                }
                this.left = null;
                return;
            }
            if (this.right != null && this.right.no == no){
                if (this.right.left != null && this.right.right == null){
                    this.right = this.right.left;
                    return;
                }
                if (this.right.right != null && this.right.left == null){
                    this.right = this.right.right;
                    return;
                }
                if (this.right.left != null &&this.right.right != null){
                    HeroNode thisRight = this.right.right;
                    this.right = this.right.left;
                    this.right.right = thisRight;
                    return;
                }
                this.right = null;
                return;
            }
            if (this.left != null){
                this.left.delNode(no);
            }
             if (this.right != null){
                 this.right.delNode(no);
             }
        }
    

    结果如下:
    在这里插入图片描述
    可能有错误或者实现的很麻烦,希望大佬指正

    展开全文
  • 二叉树删除结点

    2022-02-04 20:13:29
    由于我现在所学习的二叉树并不是二叉有序树所以对二叉树删除条件做了些变动: 如果删除结点是叶子结点,则删除结点 如果删除结点是非叶子结点,则删除该子树 思路分析 1、如果该树只有一个根结点 那么将树...

    删除要求

    由于我现在所学习的二叉树并不是二叉有序树所以对二叉树的删除条件做了些变动:

    • 如果删除的结点是叶子结点,则删除该结点
    • 如果删除的结点是非叶子结点,则删除该子树

    思路分析

    1、如果该树只有一个根结点 那么将树置空
    2、如果当前结点的左子结点不为空并且左子结点就是要删除的结点就将当前结点的左子结点置空并且返回结束递归
    3、如果当前结点的右子结点不为空并且右子结点就是要删除的结点就将当前结点的右子结点置空并且返回结束递归
    4、如果当前结点的左右子节点并不是要删除的结点,则向左子树递归删除
    5、如果左子树中没有要删除的结点就向右子树递归删除

    代码实现

    /**
     * 模拟结点
     */
    public class Node {
        private int id;
        private String name;
        /*左节点*/
        private Node left;
        /*右节点*/
        private Node right;
    
        /*构造方法*/
        public Node(int id, String name) {
            this.id = id;
            this.name = name;
        }
        /*前序遍历*/
        public void preDisplay(){
            System.out.println(this);
            if (this.left != null) {
                this.left.preDisplay();
            }
            if (this.right != null) {
                this.right.preDisplay();
            }
    
        /**
         * 根据id删除结点
         * 说明:
         *  这里删除的如果是叶子结点就删除该节点
         *  如果删除的不是叶子节点就删除那个结点及其子树
         * @param id
         * @return true表示删除成功 false表示没找到结点
         */
        public boolean delete(int id){
            if (this.left != null && this.left.id == id) {
                /*如果当前结点的左子结点不为空并且是要删除的结点就删除左子结点*/
                this.left = null;
                return true;
            }
            if (this.right != null && this.right.id == id) {
                /*如果当前结点的右子结点不为空并且是要删除的结点就删除右子结点*/
                this.right = null;
                return true;
            }
            /*当前结点的左子节点和右子节点都不是要删除是的结点*/
            if (this.left != null) {
                //向左子树递归删除
                this.left.delete(id);
            }
            if (this.right != null){
                //向右子树递归删除
                boolean delete = this.right.delete(id);
                if (delete){
                    return delete;
                }
            }
            return false;
        }
    
    	getter and setter 方法
    
        @Override
        public String toString() {
            return "[" + "id=" + id + ", name=" + name  + ']';
        }
    }
    
    public class BinaryTree {
    
        /*根结点*/
        private Node root;
    
        public void setRoot(Node root) {
            this.root = root;
        }
        /*前序遍历*/
        public void preShow(){
            if (this.root != null) {
                this.root.preDisplay();
            }else{
                System.out.println("二叉树为空");
            }
        }
    
        /*删除结点*/
        public void delNode(int id){
            if (root != null) {
                /*判断根节点是否为要删除的结点*/
                if (root.getId() == id) {
                    root = null;
                    System.out.println("删除成功");
                }else{
                    boolean isDelete = root.delete(id);
                    System.out.println(isDelete ? "删除成功" : "删除失败没找到结点");
                }
            }else{
                System.out.println("二叉树为空");
            }
        }
    }
    
    public class BinaryTreeTest {
        public static void main(String[] args) {
            /*手动创建结点*/
            Node node1 = new Node(1,"张三");
            Node node2 = new Node(2,"李四");
            Node node3 = new Node(3,"王五");
            Node node4 = new Node(4,"赵六");
            node1.setLeft(node2);
            node1.setRight(node3);
            node3.setRight(node4);
    
            /*创建二叉树*/
            BinaryTree tree = new BinaryTree();
            tree.setRoot(node1);
    
            System.out.println("删除前的前序遍历:");
            tree.preShow();
            tree.delNode(4);
            System.out.println("删除后的前序遍历:");
            tree.preShow();
        }
    }
    

    运行结果

    删除前的前序遍历:
    [id=1, name=张三]
    [id=2, name=李四]
    [id=3, name=王五]
    [id=4, name=赵六]
    删除成功
    删除后的前序遍历:
    [id=1, name=张三]
    [id=2, name=李四]
    [id=3, name=王五]
    
    Process finished with exit code 0
    
    展开全文
  • java二叉树删除节点

    2022-01-02 22:23:13
    找到删除节点是父节点的左子树还是右子树 根据前边情况进行删除 右子树:p.rc=null 左子树:p.lc=null 删除的节点只有一个子树 找到删除的叶子结点tNode 找到目标节点的父节点pNode(考虑是否有父节点) 找到删除...

    二叉树的删除要考虑三种情况
    1.删除的节点是叶子节点2.删除的节点只有一个子树3.删除的节点有两个子树

    删除的节点是叶子节点
    找到删除的叶子结点tNode
    找到目标节点的父节点pNode(考虑是否有父节点)
    找到删除节点是父节点的左子树还是右子树
    根据前边情况进行删除
    右子树:p.rc=null
    左子树:p.lc=null

    删除的节点只有一个子树
    找到删除的叶子结点tNode
    找到目标节点的父节点pNode(考虑是否有父节点)
    找到删除节点是父节点的左子树还是右子树
    确定删除节点是左子树还是右子树
    根据前边情况进行删除
    tNode是它父节点的左子树
    tNode有左子树 : pNode.lc=tNode.lc
    tNode有右子树 : pNode.lc=tNode.rc
    tNode是是它父节点的右子树
    tNode有左子树 : pNode.rc=tNode.lc
    tNode有右子树 : pNode.rc=tNode.rc

    删除的节点有两个子树
    找到删除的叶子结点tNode
    找到目标节点的父节点pNode(考虑是否有父节点)
    找到删除节点右子树中最小的或找到左子树中最大的
    将右子树当中最大的值替换掉删除节点的值
    使删除叶子节点的逻辑,删除最小值

    //找到要删除的节点
    	public TreeNode searchDelnode(TreeNode node,Integer val) {
    		if(node==null) {
    			return null;
    		}
    		if(node.val==val) {
    			return node;
    		}else if(val>node.val){
    			if(node.rightNode==null) {
    				return null;
    			}
    			return searchDelnode(node.rightNode, val);
    		}else {
    			if(node.leftNode==null) {
    				return null;
    			}
    			return searchDelnode(node.leftNode, val);
    		}
    	}
    
    //找到要删除节点的父节点
    	public TreeNode searchDelpartent(TreeNode node,Integer val) {
    		if(node==null) {
    			return null;
    		}
    		if((node.leftNode!=null&&node.leftNode.val==val)||(node.rightNode!=null&&node.rightNode.val==val)) {
    			return node;
    		}else {
    			if(node.leftNode!=null&&val<node.val) {
    				return searchDelpartent(node.leftNode, val);
    			}else if(node.rightNode!=null&&val>node.val){
    				return searchDelpartent(node.rightNode, val);
    			}else {
    				return null;
    			}
    		}
    	}
    
    //二叉树删除节点
    	public void del(TreeNode node,Integer val) {
    		if(node==null) {
    			return;
    		}
    		//1.找到要删除的节点
    		TreeNode targetNode=searchDelnode(node, val);
    		//2.没有找到要删除的节点
    		if(targetNode==null) {
    			return;
    		}
    		//3.找到要删除节点的父节点
    		TreeNode parentNode=searchDelpartent(node, val);
    		if(node.rightNode==null&&node.leftNode==null) {
    			root=null;
    			return;
    		}
    		if(parentNode==null&&(targetNode.rightNode!=null||targetNode.leftNode!=null)) {
    			int min=searchRightMin(targetNode.rightNode);
    			targetNode.val=min;
    			return;
    		}
    		if(targetNode.leftNode==null&&targetNode.rightNode==null) {
    			if(parentNode.rightNode!=null&&parentNode.rightNode.val==targetNode.val) {
    				parentNode.rightNode=null;
    			}else if(parentNode.leftNode!=null&&parentNode.leftNode.val==val){
    				parentNode.leftNode=null;
    			}
    		}else if(targetNode.leftNode!=null&&targetNode.rightNode!=null) {
    //在删除节点由左右两个子树时,我们选择找删除节点右子树的最小值,我们可以写一个方法,在这个方法里不仅找到最小值,并把这个位置的元素进行删除
    			int min=searchRightMin(targetNode.rightNode);
    			targetNode.val=min;
    		}else {
    			if(targetNode.rightNode!=null) {
    				if(parentNode.rightNode.val==targetNode.val) {
    					parentNode.rightNode=targetNode.rightNode;
    				}else {
    					parentNode.leftNode=targetNode.rightNode;
    				}
    			}else{
    				if(targetNode.rightNode.val==targetNode.val) {
    					parentNode.rightNode=targetNode.leftNode;
    				}else {
    					parentNode.leftNode=targetNode.leftNode;
    				}
    			}
    		}
    	}
    
    展开全文
  • 最完整二叉树删除节点

    千次阅读 2020-11-26 18:40:34
    二叉树删除节点 在自己研究二叉树删除节点时,查网上资料时发现,网上大部分写的都是错的,主要错在当删除节点既存在左子树,又存在右子树时,在中序遍历后获取后继节点后,大部分文章未考虑后继节点存在右子树的...
  • 找到删除节点是父节点的左子树还是右子树 根据前边情况进行删除 右子树:p.rc=null 左子树:p.lc=null 删除的节点只有一个子树 找到删除的叶子结点tNode 找到目标节点的父节点pNode(考虑是否有父节点) ...
  • 二叉树删除节点(C语言)

    千次阅读 2021-05-02 15:31:17
    二叉树删除节点 删除分为四种情况 这个节点左右孩子都有 这个节点没有左右孩子 这个节点只有左孩子 这个节点只有右孩子 1.查找节点位置 struct TreeNode *p = NULL;//遍历指针 struct TreeNode *fp = NULL;//...
  • 二叉树删除结点 思路分析 完成删除的操作 规定: 如果删除的结点是叶子节点,则删除该节点 如果删除的结点是非叶子节点,则删除该子树 思路: 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要...
  • 本篇博客是根据b站尚硅谷的数据结构教程,学习后写的学习笔记,本篇博客的重点在自己编写的代码注释和过程分析...因为我们的二叉树是单向的,所以我们是判断当前节点的子节点是否是需要删除节点,而不能判断当前的这
  • 二叉树删除指定节点

    千次阅读 2020-12-04 11:06:42
    二叉树删除节点: 要求: 如果删除的节点是叶子结点,则删除该结点。 如果删除的节点是非叶子结点,则删除该子树。 思路: 首先处理根节点: 如果树是空树,
  • 13.1.2 二叉树-删除节点(简单) 要求: 如果删除的节点是叶子节点,则删除该节点 入关删除的节点是非子叶节点,则删除该子树 思路: 因为我们的二叉树是单向的,没办法找到前驱节点,所以我们判断当前节点的子...
  • 本文将详细介绍二叉树的创建,节点删除节点增加等一系列操作方法,需要的朋友可以参考下
  • 删除节点。 1)如果需要删除的节点有左子树(不管有没有右子树),其方法是将左子树中最大值替换掉该节点。 第一步:通过递归寻找到需要删除的节点。 第二步:找到删除的那个节点的左子树的最大值。 第三步:将这个...
  • 二叉树~删除节点

    2022-04-14 09:22:19
    1)因为二叉树是单向的,所以我们是判断当前节点的子节点是否需要删除节点,而不能判断当前这个节点上是不是需要删除的节点 2)如果当前节点的左子节点不为空,且左子节点就是要删除的节点,就将this.left == null;...
  • 一、二叉树删除节点的思路图解 二、二叉树删除节点的示例代码 1、代码 package com.rf.springboot01.dataStructure.tree; /** * @description: 二叉树删除节点示例 * @author: xiaozhi * @create: 2020-08-28 ...
  • 删除节点 删除一个BST的节点要比插入困难一点,但同样是要遵循一个原则,即:删除节点后仍然要保持“小-中-大”的逻辑关系。 假设要删除的节点是x,大体思路如下: 若要删除的节点小于根节点,则递归地在左子树中...
  • 数据结构——平衡二叉树删除

    千次阅读 2021-07-08 08:15:25
    目录 前言 删除结点 调整结点 代码实现 ... 我们知道,在平衡二叉树中插入一个... 平衡二叉树删除结点和插入操作类似,首先先删除一个结点,然后对自下向上最近的平衡因子超过1的结点进行调整。 删除结点 首先...
  • 平衡二叉树删除结点的情况

    千次阅读 2019-03-04 12:59:12
    这样做的用意是,删除结点左子树的最大结点后,AVL树仍然满足二叉搜索树的性质:任意结点的左孩子均不大于根结点,任意结点的右孩子均不小于根结点 2.如果左右子树均不为空,且右子树比左子树高 ...
  • C语言实现二叉树节点删除

    千次阅读 2019-05-02 20:12:46
    二叉树节点删除 C C++
  • 平衡二叉树删除

    2021-11-25 20:24:05
    平衡二叉树的删除平衡二叉树的删除平衡二叉树删除节点的三种情况删除叶子节点被删的结点只有左子树或只有右子树被删的结点既有左子树又有右子树   平衡二叉树的删除 平衡二叉树是最优的二叉排序树,因此删除操作...
  • 二叉树删除结点其实是将我们要删除的节点与他的父节点没有联系也就是将父结点给要删除的结点位置置空。比如说root.left = null或者root.right = null;下面我们上代码进行分析先简单有一个思路 //下面为实体类里面的...
  • 结点类 public class BinaryTreeNodeDel { //结点类 private BinaryTreeNodeDel leftNode; private BinaryTreeNodeDel rightNode; public int id; public String name; //构造方法,toString, setget方法 ...
  • 顺序二叉树的建立及删除某个节点后仍然保持顺序二叉树特性..
  • 排序二叉树-删除节点

    2020-06-23 15:40:50
    前面( https://blog.csdn.net/jsjsjs1789/article/details/106772632 ),我们已经了解了什么是排序二叉树以及排序二叉树的遍历和添加元素,现在我们一起来看一下,排序二叉树是如何删除元素的。 package xmht....
  • 主要介绍了JavaScript数据结构与算法之二叉树添加/删除节点操作,涉及javascript二叉树的定义、节点添加、删除、遍历等相关操作技巧,需要的朋友可以参考下
  • 排序二叉树删除指定节点 (一)基本思路 {分3种情况} 情况一:若删除节点为叶子节点,那理论上直接删除就行。但操作上,会找到删除节点的父节点 parent,后判断删除节点是其左子节点还是右子节点,后指针置空即可...
  • 二叉树删除节点+思路分析

    千次阅读 2021-03-25 19:32:10
    思路分析 代码实现 ![在这里插入代码片](https://img-blog.csdnimg.cn/20210325193201194.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ...t_70)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 104,481
精华内容 41,792
关键字:

二叉树删除节点

友情链接: 294531.rar