精华内容
下载资源
问答
  • 二叉树删除

    千次阅读 2019-03-30 11:55:54
    二叉树删除 二叉查找树的查找、插入操作都比较简单易懂,但是它的删除操作就比较复杂了 。针对要删除节点的子节点个数的不同,我们需要分三种情况来处理。 第一种情况是,如果要删除的节点没有子节点,我们只需要...

    二叉树查找树(Binary Search Tree)

    二叉查找树是二叉树中最常用的一种类型,也叫二叉搜索树。顾名思义,二叉查找树是为了实现快速查找而生的。不过,它不仅仅支持快速查找一个数据,还支持快速插入、删除一个数据。它是怎么做到这些的呢?

    这些都依赖于二叉查找树的特殊结构。二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值。我画了几个二叉查找树的例子,你一看应该就清楚了。
    在这里插入图片描述

    二叉树查找树删除

    二叉查找树的查找、插入操作都比较简单易懂,但是它的删除操作就比较复杂了 。针对要删除节点的子节点个数的不同,我们需要分三种情况来处理。

    第一种情况(没有子节点)

    如果要删除的节点没有子节点,我们只需要直接将父节点中,指向要删除节点的指针置为 null。比如图中的删除节点 55。

    第二种情况(只有一个子节点)

    如果要删除的节点只有一个子节点(只有左子节点或者右子节点),我们只需要更新父节点中,指向要删除节点的指针,让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。

    第三种情况(有两个子节点)

    如果要删除的节点有两个子节点,这就比较复杂了。我们需要找到这个节点的右子树中的最小节点,把它替换到要删除的节点上。然后再删除掉这个最小节点,因为最小节点肯定没有左子节点(如果有左子结点,那就不是最小节点了),所以,我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。

    二叉树删除操作

    二叉树删除代码

    public void delete(int data) {
      Node p = tree; // p 指向要删除的节点,初始化指向根节点
      Node pp = null; // pp 记录的是 p 的父节点
      while (p != null && p.data != data) {
        pp = p;
        if (data > p.data) p = p.right;
        else p = p.left;
      }
      if (p == null) return; // 没有找到
     
      // 要删除的节点有两个子节点
      if (p.left != null && p.right != null) { // 查找右子树中最小节点
        Node minP = p.right;
        Node minPP = p; // minPP 表示 minP 的父节点
        while (minP.left != null) {
          minPP = minP;
          minP = minP.left;
        }
        p.data = minP.data; // 将 minP 的数据替换到 p 中
        p = minP; // 下面就变成了删除 minP 了
        pp = minPP;
      }
     
      // 删除节点是叶子节点或者仅有一个子节点
      Node child; // p 的子节点
      if (p.left != null) child = p.left;
      else if (p.right != null) child = p.right;
      else child = null;
     
      if (pp == null) tree = child; // 删除的是根节点
      else if (pp.left == p) pp.left = child;
      else pp.right = child;
    }
    

    其它

    实际上,关于二叉查找树的删除操作,还有个非常简单、取巧的方法,就是单纯将要删除的节点标记为“已删除”,但是并不真正从树中将这个节点去掉。这样原本删除的节点还需要存储在内存中,比较浪费内存空间,但是删除操作就变得简单了很多。而且,这种处理方法也并没有增加插入、查找操作代码实现的难度。

    展开全文
  • 1.二叉树删除结点 2.顺序存储二叉树 二叉树删除结点其实是将我们要删除的节点与他的父节点没有联系也就是将父结点给要删除的结点位置置空。比如说root.left = null或者root.right = null;下面我们上代码进行分析先...

    1.二叉树删除结点
    2.顺序存储二叉树

    二叉树删除结点其实是将我们要删除的节点与他的父节点没有联系也就是将父结点给要删除的结点位置置空。比如说root.left = null或者root.right = null;下面我们上代码进行分析先简单有一个思路

    //下面为实体类里面的代码块
    //二叉树删除结点
        public void delNode(int no) {   
            if (this.left != null && this.left.no == no) {//
               // if (this.left.left == null && this.left.right == null) {
                    this.left = null;
                    return;
             //   } else {
             //       HeroNode temp = this.left.left;
              //      HeroNode temp2 = this.left.right;
             //       this.left = temp;
              //      temp.right = temp2;
              //      return;
             //   }
            }
            if (this.right != null && this.right.no == no) {
              //  if (this.right.left == null && this.right.right == null) {
                    this.right = null;
                    return;
              //  } else {
              //      HeroNode temp = this.right.left;
              //      HeroNode temp2 = this.right.right;
              //      this.right = temp;
              //      temp.right = temp2;
              //      return;
              //  }
            }
            if (this.left != null) {
                this.left.delNode(no);
            }
            if (this.right != null) {
                this.right.delNode(no);
            }
        }
         //下面为树对象里面的代码块
         //二叉树删除结点
        public void delNode(int no){
            if (root != null) {
                if (root.getNo() == no) {
                    root = null;
                    return;
                } else {
                    this.root.delNode(no);
                }
            }else {
                System.out.println("空树不能删除");
            }
        }
    

    我尽可能呢在代码中注释出来首先我们肯定要先找根节点的编号,看看根节点是否是我们需要删除的结点,然后我们再找子节点。所以我们在实体类中的方法我们默认已经检查过根节点的编号了。所以我们直接1.先判断左子节点如果不为空并且左子节点就是我们需要删除的结点。2.直接让根结点的左子节点置空就可以。3.我们判断右子节点不为空并且右子节点的编号就是我们需要删除的编号4.我们直接让右子节点置空就可以。如果左右子节点都不为空并且编号并不是我们需要删除的编号,那么我们直接递归左右遍历删除即可。

    我把其中的一些代码给注释了是因为这样简单一点,大家可以放出来看一下我写的代码是什么意思。其实就是比如说我需要删除的结点他还有子节点怎么办?
    因为通过简单的删除是回把待删除结点以及他的子节点一次性全部删除的,但是我觉得这样不好,所以我做个改进使待删除结点的左子节点上来继位。右子节点跟在其后。

    二、顺序存储二叉树
    首先我先上代码块然后为各位讲解

    public class AddTree {
        public static void main(String[] args) {
            int[] arr = new int[]{1,2,3,4,5,6,7};
            Arr arr1 = new Arr(arr);
            arr1.postOrder();
        }
    }
    
    class Arr{
        private int[] arr;
        public Arr(int[] arr) {
            this.arr = arr;
        }
        public void preOrder(){
            this.preOrder(0);
        }
        //前序遍历
        public void preOrder(int index){
            if (arr == null || arr.length == 0){
                System.out.println("数组为空不能遍历");
            }
            System.out.println(arr[index]);
            if ((index*2+1)<arr.length){
                preOrder(index*2+1);
            }
            if ((index*2+2)<arr.length){
                preOrder(index*2+2);
            }
        }
        public  void initOrder(){
            this.initOrder(0);
        }
        //中序遍历
        public void initOrder(int index){
            if (arr == null || arr.length == 0){
                System.out.println("数组为空不能遍历");
            }
            if ((index*2+1)<arr.length){
                initOrder(index*2+1);
            }
            System.out.println(arr[index]);
            if ((index*2+2)<arr.length){
                initOrder(index*2+2);
            }
        }
    
        public void postOrder(){
            this.postOrder(0);
        }
        //后续遍历
        public void postOrder(int index){
            if (arr == null ||arr.length == 0){
                System.out.println("数组为空不能遍历");
            }
            if ((index*2+1)<arr.length){
                postOrder(index*2+1);
            }
            if ((index*2+2)<arr.length){
                postOrder(index*2+2);
            }
            System.out.println(arr[index]);
        }
    }
    

    在这里插入图片描述
    根据上图我们可以得出一个结论。。。当然这个结论不是我得出的。。就是每个地方的所以和父节点的索引都是有关系的 左子节点的索引值为父节点的索引值2+1 可以举个例子比如说2结点的索引值是1父节点的索引值是0 那么 1 = 02 +1 右子节点3的索引值是2 父节点索引值是0 右子节点的索引值等于父节点索引值 * 2 + 2 所以 2 = 0 * 2 + 2。如果我们搞懂这个 ,那么代码就不难看懂了。这里我只讲一个前序存储,中序和后序存储各位自己写一下吧。上面的参考代码我给了。
    前序存储呢其实很简单。首先都是通常要做的就是先判断你给我的数组是不是空的呢或者长度为0呢。如果是的话,那我们就不用继续操作了。如果不为空或者0那么我们再继续操作好吧。首先我们传入的参数是索引值因为是顺序存储所以到时候传进去我们默认是从根节点开始所以先输出的是arr[0],左边索引值如果比数组长度小的话那么就继续向左子树进行递归遍历。直到找到左子树最后一个左叶子结点并且找到一个输出一个然后再向右递归存储和左边一样。

    今天所讲的其实都挺容易的,大家多练几遍多看看代码应该是没有那么难的了。下一期我们讲一下线索化二叉树。为下下期的重头堆排序做十足的准备。

    最后还是希望大家能够指认我的错误,谢谢大家。希望能和大家一起共同进步!!!

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

    千次阅读 2018-08-21 15:33:28
    二叉树删除结点 /** * delete: 从二叉查找树中删除给定的结点. * * @param pNode 要删除的结点 前置条件: 给定结点在二叉查找树中已经存在 * 删除后要调整二叉查找树,满足左小右大结构 * @throws ...

     

    二叉树删除结点

    /** 
         * delete: 从二叉查找树中删除给定的结点. 
         *  
         * @param pNode  要删除的结点  前置条件: 给定结点在二叉查找树中已经存在 
         * 删除后要调整二叉查找树,满足左小右大结构
         * @throws Exception 
         */  
        private void delete(TreeNode pNode) throws Exception {  
            if (pNode == null) {  
                return;  
            }  
            if (pNode.leftChild == null && pNode.rightChild == null) { // 该结点既无左孩子结点,也无右孩子结点  
                TreeNode parentNode = pNode.parent;  
                if (pNode == parentNode.leftChild) { 
                    parentNode.leftChild = null;  
                } else {  
                    parentNode.rightChild = null;  
                }  
                pNode=null;
                return;  
            }  
            if (pNode.leftChild == null && pNode.rightChild != null) { // 该结点左孩子结点为空,右孩子结点非空  
                TreeNode parentNode = pNode.parent;  
                TreeNode rightNode=pNode.rightChild;
                if (pNode == parentNode.leftChild) {  
                	rightNode.parent = parentNode;  
                    parentNode.leftChild = rightNode;  
                } else {  
                	rightNode.parent = parentNode;  
                    parentNode.rightChild = rightNode;  
                }  
                pNode=null;
                return;  
            }  
            if (pNode.leftChild != null && pNode.rightChild == null) { // 该结点左孩子结点非空,右孩子结点为空  
                TreeNode parentNode = pNode.parent;  
                TreeNode leftNode=pNode.leftChild;
                if (pNode == parentNode.leftChild) {
                	leftNode.parent = parentNode;
                    parentNode.leftChild = leftNode;            
                } else {  
                	leftNode.parent = parentNode;
                    parentNode.rightChild = leftNode;                
                }  
                pNode=null;
                return;  
            }  
            if(pNode.leftChild != null && pNode.rightChild != null){// 该结点左右孩子结点均非空
            	TreeNode successorNode = successor(pNode);  
            	pNode.key = successorNode.key;  
            	delete(successorNode);  	
            }
        }  

     

    展开全文
  • 二叉树删除指定节点

    2020-12-04 11:06:42
    二叉树删除节点: 要求: 如果删除的节点是叶子结点,则删除该结点。 如果删除的节点是非叶子结点,则删除该子树。 思路: 首先处理根节点: 如果树是空树,

    二叉树删除节点:

    1.要求:

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

    2.思路:

    • 首先处理根节点:判断树是否为空,如果只有一个结点,判断此结点是不是要删除的结点。
    • 因为二叉树是单向所以我们判断当前子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除的节点。
    • 如果当前结点的左子结点不为空,并且左子结点就是要删除的结点就将this.left = null;并返回(结束递归删除)
    • 如果当前结点的右子结点不为空,并且右子结点就是要删除的结点,就将this.right = null;并返回(结束递归删除)
    • 如果上面步骤没有删除那么就需要向左右子树进行递归删除。

    3.代码演示:

    在这里插入图片描述

    (1)、主方法:

    
    public class binaryTreeDemo {
    	public static void main(String[] args) {
    	//先创建一个二叉树
    		BinaryTree binaryTree = new BinaryTree();
    	//创建需要的结点
    		HeroNode root = new HeroNode(1,"1");
    		HeroNode node2 = new HeroNode(2,"2");
    		HeroNode node3 = new HeroNode(3,"3");
    		HeroNode node4 = new HeroNode(4,"4");
    		HeroNode node5 = new HeroNode(5,"5");
    		
    	//说明:手动创建二叉树
    		root.setLeft(node2);
    		root.setRight(node3);
    		node3.setLeft(node5);
    		node3.setRight(node4);
    	//测试:
    		binaryTree.setRoot(root);
    		System.out.println("删除前,前序遍历");
    		binaryTree.centerOrder();
    		binaryTree.del(5);
    		System.out.println("删除后,前序遍历");
    		binaryTree.centerOrder();
    	}
    }
    

    (2)、定义一个二叉树:

    //定义一个二叉树
    class binaryTree{
    	//根节点
    	private Node root;
    	//一个set方法
    	public void setRoot(Node root) {
    		this.root = root;
    	}
    	
    	//删除结点
    	public void del(int no){
    		if(this.root!=null){
    			//是否只有一个结点,这里立即判断root是不是就是要删除结点
    			if(root.getNo() == no) {
    				root = null;
    			}else {
    				//递归删除
    				root.delNode(no);
    			}
    		}else{
    			System.out.println("空树不能删除");
    		}
    	}
    
    	//前序遍历
    	public void preOrder() {
    		if(this.root != null) {
    			this.root.preOrder();
    		}else {
    			System.out.println("二叉树为空,无法遍历");
    		}
    	}
    	
    }
    

    (3)、创建结点:

    //创建结点
    class Node{
    	private int no;
    	private String name;
    	private HeroNode left;//默认null
    	private HeroNode right;//默认null
    	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 + "]";
    	}
    
    	//递归删除节点
    	//1、如果删除的结点是叶子结点,则删除该结点
    	//2、如果删除的结点是非叶子结点,则删除该子树
    	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 preOrder() {
    		System.out.println(this);//先输出父结点
    		//递归向左子树前序
    		if(this.left != null) {
    			this.left.preOrder();
    		}
    		//递归向右子树前序遍历
    		if(this.right != null) {
    			this.right.preOrder();
    		}
    	}
    
    }
    

    代码分析:

    del方法: 以当前根结点1为例首先进入del方法中判断当前结点是否为空和是否是要查找的结点,如果不是则进入delNode方法中。

    //删除结点
    	public void delNode(int no){
    		if(this.root!=null){
    			//是否只有一个结点,这里立即判断root是不是就是要删除结点
    			if(root.getNo() == no) {
    				root = null;
    			}else {
    				//递归删除
    				root.delNode(no);
    			}
    		}else{
    			System.out.println("空树不能删除");
    		}
    	}
    

    delNode方法:

    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);
    		}
    		
    	}
    
    1. 此时this.left指的是2,但是此结点不是我们要查找的结点。
    2. 接着进行右结点判断,此时this.right指的是3不是我们要查找的结点。
    3. 回到root结点(归),向左子树进行递归删除,此时左结点为2不为空进入delNode函数(递),this.left为空、this.right为空,向左子树尝试递归删除失败、向右子树尝试递归删除失败,则回到1号结点(归)。
    4. 向右子树进行递归删除,此时左结点this.left不为空并且是我们要查找的数5,此时就会将3号的左边置空。
    5. 此时代码回到binaryTree里面的else
    6. 回到主方法结束。
    展开全文
  • 二叉树删除节点

    2017-11-04 12:53:02
    二叉树删除节点比较麻烦,一般可能会设置一个isdeleted标记删除的节点而不真的删除节点,删除情况有以下几种: 1,删除的节点是根节点 2,删除的节点无子节点 3,删除的节点只有一个子节点 4,删除的节点有2个子...
  • 二叉树删除节点 在自己研究二叉树删除节点时,查网上资料时发现,网上大部分写的都是错的,主要错在当删除节点既存在左子树,又存在右子树时,在中序遍历后获取后继节点后,大部分文章未考虑后继节点存在右子树的...
  • 二叉树删除指定节点 规定: 1.1 如果删除的节点是叶子节点,则删除该节点。 1.2 如果删除的节点是非叶子节点,则删除该子树。 步骤: 2.1 如果树是空树,无需操作直接返回。如果根节点是要删除的节点,则直接将...
  • 二叉树删除子树

    2021-01-10 17:03:04
    编写程序对给定二叉树执行若干次删除子树操作,输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。 输入格式: 输入第1行为一...
  • 首先定义结点类 class Node :public class Node {public Node leftchild=null;public Node rightchild=null;...}然后再定义二叉树类 class Btreepublic class Btree{// 删除值为val的节点public void delete(In...
  • 二叉树删除 二叉树-删除节点 要求 如果删除的节点是叶子节点,则删除该节点 如果删除的节点是非叶子节点,则删除该子树. 测试,删除掉 5号叶子节点 和 3号子树 思路分析 代码实现 public class Treedemo { public ...
  • 二叉树删除节点-简答版 要求 1.如果是叶子节点则删除该节点 2.如果是非叶子节点则删除子树 代码实现 class BinaryTree { private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } ...
  • 一、二叉树删除节点的思路图解 二、二叉树删除节点的示例代码 1、代码 package com.rf.springboot01.dataStructure.tree; /** * @description: 二叉树删除节点示例 * @author: xiaozhi * @create: 2020-08-28 ...
  • 二叉树删除涉及到多种情况,需要逐个处理 1.当前节点为叶子节点  直接删除 2.当前节点右子树为空  复制左子树中最大的值,用该值替代当前节点,删除左子树中原节点。 3.当前节点右子树不为空  复制右子树中...
  • 二叉树删除节点时,分为两种情况,删除节点为叶子节点与非叶子节点。 首先判断根节点是否要删除的节点。如果是,则将该二叉树变为空树;否则判断左子节点与右子节点是否要删除的节点。 如果是,删除以该节点为根...
  • 二叉树删除结点 思路分析 完成删除的操作 规定: 如果删除的结点是叶子节点,则删除该节点 如果删除的结点是非叶子节点,则删除该子树 思路: 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要...
  • 二叉树最复杂的步骤即为删除操作,此处只简单介绍一下具体思路:(1)如果待删除的节点是一片树叶,那么它可以被立即删除。然后将其父节点的相应子节点(左节点或右节点)至空。(2)如果被删除的节点有一个子节点,那么把...
  • 排序二叉树删除指定节点 (一)基本思路 {分3种情况} 情况一:若删除节点为叶子节点,那理论上直接删除就行。但操作上,会找到删除节点的父节点 parent,后判断删除节点是其左子节点还是右子节点,后指针置空即可...
  • 今天所讲的是二叉树的删除,小伙伴们点进来,肯定是对二叉树有说了解的吧啊,首先学习二叉树删除,建议先了解诶二叉树的建立,遍历,插入和查找,以便小伙伴们能够很好的掌握今天小编所讲的内容,接下来让我们一起来...
  • 二叉树删除子树 编写程序对给定二叉树执行若干次删除子树操作,输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。 输入格式: ...
  • 用Java语言实现二叉树删除结点

    千次阅读 2015-04-01 21:13:57
    用Java语言实现二叉树删除节点功能
  • 平衡二叉树删除

    2021-02-18 17:35:22
    http://ddrv.cn/a/43964

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,626
精华内容 3,850
关键字:

二叉树删除