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

    千次阅读 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);  	
            }
        }  

     

    展开全文
  • 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],左边索引值如果比数组长度小的话那么就继续向左子树进行递归遍历。直到找到左子树最后一个左叶子结点并且找到一个输出一个然后再向右递归存储和左边一样。

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

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

    展开全文
  • 二叉树删除结点 思路分析 完成删除的操作 规定: 如果删除的结点是叶子节点,则删除该节点 如果删除的结点是非叶子节点,则删除该子树 思路: 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要...

    二叉树删除结点

    思路分析

    完成删除的操作

    规定:

    1. 如果删除的结点是叶子节点,则删除该节点
    2. 如果删除的结点是非叶子节点,则删除该子树

    思路:

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

    代码实现

    删除方法delNode(int no):

    // 递归删除结点
    	// 1. 如果删除的结点是叶子节点,则删除该节点
    	// 2. 如果删除的结点是非叶子节点,则删除该子树
    	public void delNode(int no) {
    		// 思路:
    		// 1. 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点
    		// 2. 如果当前结点的左子结点不为空,并且左子结点就是要删除结点,就将this.left=null;并且就返回(结束递归删除)
    		// 3. 如果当前结点的右子结点不为空,并且右子结点就是要删除结点,就将this.right=null;并且就返回(结束递归删除)
    		// 4. 如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除
    		// 5. 如果第4步也没有删除结点,则应当向右子树进行递归删除。
    		// 6. 如果考虑树是空树root,如果只有一个root结点,则等价将二叉树置空
    		// 2. 如果当前结点的左子结点不为空,并且左子结点就是要删除结点,就将this.left=null;并且就返回(结束递归删除)
    		if (this.left != null && this.left.no == no) {
    			this.left = null;
    			return;
    		}
    		// 3. 如果当前结点的右子结点不为空,并且右子结点就是要删除结点,就将this.right=null;并且就返回(结束递归删除)
    		if (this.right != null && this.right.no == no) {
    			this.right = null;
    			return;
    		}
    		// 4.先左子树进行递归删除
    		if (this.left != null) {
    			this.left.delNode(no);
    		//	return
    		}
    		// 5.向右子树递归删除
    		if (this.right != null) {
    			this.right.delNode(no);
    		}
    	}
    

    delNode(int no)方法的实现:

    //删除结点
    	public void delNode(int no) {
    		if (root!=null) {
    			//如果只有一个root结点,立即判断root是不是要删除的结点
    			if(root.getNo()==no) {
    				root=null;
    			}else {
    				//递归删除
    				root.delNode(no);
    			}
    		}else {
    			System.out.println("空树,不能删除");
    		}
    	}
    
    展开全文
  • 首先定义结点类 class Node :public class Node {public Node leftchild=null;public Node rightchild=null;...}然后再定义二叉树类 class Btreepublic class Btree{// 删除值为val的节点public void delete(In...

    首先定义结点类 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();

    }

    }

    展开全文
  • 平衡二叉树删除结点的情况

    千次阅读 2019-03-04 12:59:12
    这样做的用意是,删除结点左子树的最大结点后,AVL树仍然满足二叉搜索树的性质:任意结点的左孩子均不大于根结点,任意结点的右孩子均不小于根结点 2.如果左右子树均不为空,且右子树比左子树高 ...
  • 删除结点值为x的子树 方法一递归:
  • 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫...二叉树二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS...
  • 把判断root的逻辑写在BinaryTree二叉树删除方法里,然后递归的逻辑写在HeroNode节点的删除方法里。 思路: 首先处理: 考虑如果树是空树,和如果只有一个root节点,则等价于将二叉树置空。 public void delNode...
  • 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一般来说,删除节点可分为两个步骤: 首先找到...
  • 用Java语言实现二叉树删除结点

    千次阅读 2015-04-01 21:13:57
    用Java语言实现二叉树删除节点功能
  • 本篇讲解搜索二叉树删除结点时的N多种情况,附C实现代码。 关于搜索二叉树的有序创建、查找、查找最大最小节点 以及求父节点,可查看此篇。 https://blog.csdn.net/qq_41958529/article/details/99669751 ::...
  • 二叉树结点删除 二叉树结点分叶子结点、单子树结点和双子树结点删除也要分这三种情况进行,叶子结点和单子树结点只需将双方的父子几点重新搭建好,再delete掉要删除结点,然后m_nCount --即可。 对于双子树...
  • 总结一下从平衡二叉树中删除结点可以分为以下三步:找到要删除的结点完成节点的删除找到因为删除而导致不满足平衡二叉树要求的子树并对其进行调整平衡二叉树删除的精髓在于,把要删除的结点数据与真正需要保留的结点...
  • 用C++实现的,一般说来二叉树结点删除比较复杂
  • 二叉树——删除结点

    2019-09-14 15:56:02
    删除结点有三个情况 1.被删除的结点是叶子结点: 直接删除即可 2.被删除的结点有一个叶子结点: 将其唯一子节点与父结点相连,原来是父结点的左结点,那么其儿子节点仍连为父结点的左结点,右同。 3.被删除的....
  • 二叉树删除结点的操作思路 2.2. 二叉树结点删除代码实现 2.2.1. 结点类新增 2.2.2. 二叉树类新增 2.2.3. 测试类新增 2.3. 二叉树删除结点测试结果 2.3.1. 删除结点编号为 2 的非叶子结点 2.3.2. 删除结点编号为 4 ...
  • 二叉树结点删除操作

    2018-08-23 11:00:53
    二叉树结点删除要分为三类: 1、没有子结点 2、有一个子结点 3、有两个子结点 可以看一下这个
  • 3.二叉树结点删除操作 4.二叉树结点的清除操作 5.小结 1.二叉树结点的查找操作 查找的方式: 基于数据元素值的查找 BTreeNode<T>* find(const T& value) const 基于结点的查找 BTreeNode<T...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,377
精华内容 950
关键字:

二叉树删除结点