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

    2021-03-17 20:27:28
    1 如果删除的节点是叶子节点,则删除该节点。 2 如果删除的节点是非叶子节点,则删除该子树。 二算法 三代码 package com.atguigu.tree; /** * @className: BinaryTreeDemo * @description: 二叉树实战 * ...

    一 需求

    1 如果删除的节点是叶子节点,则删除该节点。

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

    二 算法

    三 代码

    package com.atguigu.tree;
    
    /**
    * @className: BinaryTreeDemo
    * @description: 二叉树实战
    * @date: 2021/3/16
    * @author: cakin
    */
    public class BinaryTreeDemo {
        /**
         * 功能描述:二叉树测试
         *
         * @param args 命令行
         * @author cakin
         * @date 2021/3/16
         */
        public static void main(String[] args) {
            // 创建一颗二叉树
            BinaryTree binaryTree = new BinaryTree();
            // 创建需要的结点
            HeroNode root = new HeroNode(1, "宋江");
            HeroNode node2 = new HeroNode(2, "吴用");
            HeroNode node3 = new HeroNode(3, "卢俊义");
            HeroNode node4 = new HeroNode(4, "林冲");
            HeroNode node5 = new HeroNode(5, "关胜");
    
            // 先手动创建该二叉树
            root.setLeft(node2);
            root.setRight(node3);
            node3.setRight(node4);
            node3.setLeft(node5);
            binaryTree.setRoot(root);
    
            // 删除结点
            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
        }
    }
    
    /**
    * @className: BinaryTreeDemo
    * @description: 二叉树
    * @date: 2021/3/16
    * @author: cakin
    */
    class BinaryTree {
        private HeroNode root;
    
        public void setRoot(HeroNode root) {
            this.root = root;
        }
    
        /**
         * 功能描述:删除结点
         *
         * @param no 节点号
         * @author cakin
         * @date 2021/3/17
         */
        public void delNode(int no) {
            if (root != null) {
                // 如果只有一个root结点, 立即判断root是不是就是要删除结点
                if (root.getNo() == no) {
                    root = null;
                } else {
                    // 递归删除
                    root.delNode(no);
                }
            } else {
                System.out.println("空树,不能删除~");
            }
        }
    
        /**
         * 功能描述:前序遍历
         *
         * @author cakin
         * @date 2021/3/16
         */
        public void preOrder() {
            if (this.root != null) {
                this.root.preOrder();
            } else {
                System.out.println("二叉树为空,无法遍历");
            }
        }
    
        /**
         * 功能描述:中序遍历
         *
         * @author cakin
         * @date 2021/3/16
         */
        public void infixOrder() {
            if (this.root != null) {
                this.root.infixOrder();
            } else {
                System.out.println("二叉树为空,无法遍历");
            }
        }
    
        /**
         * 功能描述:后序遍历
         *
         * @author cakin
         * @date 2021/3/16
         */
        public void postOrder() {
            if (this.root != null) {
                this.root.postOrder();
            } else {
                System.out.println("二叉树为空,无法遍历");
            }
        }
    }
    
    /**
    * @className: HeroNode
    * @description: 英雄节点
    * @date: 2021/3/16
    * @author: cakin
    */
    class HeroNode {
        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 + "]";
        }
    
        /**
         * 功能描述:递归删除结点
         *
         * @param no 待删除的节点
         * @author cakin
         * @date 2021/3/17
         * @description: 算法描述
         * 1 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点。
         * 2 如果当前结点的左子结点不为空,并且左子结点就是要删除结点,就将this.left = null;并且就返回(结束递归删除)。
         * 3 如果当前结点的右子结点不为空,并且右子结点就是要删除结点,就将this.right= null;并且就返回(结束递归删除)。
         * 4 如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除。
         * 5 如果第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);
            }
        }
    
        /**
         * 功能描述:前序遍历
         *
         * @author cakin
         * @date 2021/3/16
         */
        public void preOrder() {
            System.out.println(this); //先输出父结点
            //递归向左子树前序遍历
            if (this.left != null) {
                this.left.preOrder();
            }
            //递归向右子树前序遍历
            if (this.right != null) {
                this.right.preOrder();
            }
        }
    
        /**
         * 功能描述:中序遍历
         *
         * @author cakin
         * @date 2021/3/16
         */
        public void infixOrder() {
            // 递归向左子树中序遍历
            if (this.left != null) {
                this.left.infixOrder();
            }
            // 输出父结点
            System.out.println(this);
            // 递归向右子树中序遍历
            if (this.right != null) {
                this.right.infixOrder();
            }
        }
    
        /**
         * 功能描述:后序遍历
         *
         * @author cakin
         * @date 2021/3/16
         */
        public void postOrder() {
            if (this.left != null) {
                this.left.postOrder();
            }
            if (this.right != null) {
                this.right.postOrder();
            }
            System.out.println(this);
        }
    }

    四 测试

    1 删除节点5

    删除前,前序遍历
    HeroNode [no=1, name=宋江]
    HeroNode [no=2, name=吴用]
    HeroNode [no=3, name=卢俊义]
    HeroNode [no=5, name=关胜]
    HeroNode [no=4, name=林冲]
    删除后,前序遍历
    HeroNode [no=1, name=宋江]
    HeroNode [no=2, name=吴用]
    HeroNode [no=3, name=卢俊义]
    HeroNode [no=4, name=林冲]

    2 删除节点3

    删除前,前序遍历
    HeroNode [no=1, name=宋江]
    HeroNode [no=2, name=吴用]
    HeroNode [no=3, name=卢俊义]
    HeroNode [no=5, name=关胜]
    HeroNode [no=4, name=林冲]
    删除后,前序遍历
    HeroNode [no=1, name=宋江]
    HeroNode [no=2, name=吴用]

     

    展开全文
  • 平衡二叉树的删除

    千次阅读 多人点赞 2018-03-05 11:16:58
    平衡二叉树的删除也涉及到删除后的连接问题。其删除一般分为4种情况: 1)删除叶子结点; 2)删除左子树为空,右子树不为空的结点: 3)删除左子树不为空,右子树为空的结点; 4)删除左右子树都不为空的结点。 ...

    平衡二叉树的删除也涉及到删除后的连接问题。其删除一般分为4种情况:
    1)删除叶子结点;
    2)删除左子树为空,右子树不为空的结点:
    3)删除左子树不为空,右子树为空的结点;
    4)删除左右子树都不为空的结点。

    删除叶子结点很简单,直接删除即可,此处不再赘述。接下来分别学习其他三种删除情况。

    左子树为空,有子树不为空


    以图中的平衡二叉树为例。
    现要删除结点105,结点105有右子树,没有左子树,则删除后,只需要将其父结点与其右子树连接即可。
    这里写图片描述
    删除结点会使相应子树的高度减小,可能会导致树失去平衡,如果删除结点后使树失去平衡,要调整最小不平衡子树使整棵树达到平衡。插入和删除一样,在删除的过程中要时刻保持树的平衡性。

    做子树不为空,右子树为空


    要删除一个结点,结点有左子树没有右子树,这种情况与上一种情况相似,只需要将其父结点与其左子树连接即可。例如要删除图中的结点100,其删除过程如图所示:
    这里写图片描述

    左右子树均不为空


    如果要删除的结点既有左子树又有右子树,则要分情况进行讨论。

    (1)如果该结点x的平衡因子为0或者1 ,找到其左子树中具有最大值的结点max,将max的内容与x的元素进行交换,则max即为要删除的结点。由于树是有序的,因此找到的max结点只可能是一个叶子结点或者一个没有右孩子的结点。

    例如现在有一棵平衡二叉树。现在要删除结点20,结点20的平衡因子是1,则在其左子树中找到最大结点15,将两个结点的数值互换。
    这里写图片描述

    然后删除结点20。
    在删除结点20之后,平衡二叉树失去了平衡,结点10的平衡因子为2,则需要对此最小不平衡子树进行调整,此次调整类似于插入,先进性一次左旋转再进行一次右旋转即可,调整后的结果如图:
    这里写图片描述
    (2)如果要删除的结点其平衡因子为-1,则找到其右结点中具有最小值的结点min,将min与x的数据值进行互换,则min即为新的要删除的结点,将结点删除后,如果树失去了平衡,则需要重新调整。由于平衡二叉树是有序的,因此这样的结点只可能是一个叶子结点,或者是一个没有左子树的结点。

    展开全文
  • 主要介绍了JavaScript数据结构之二叉树的删除算法,简单分析了javascript删除数据结构中二叉树节点时所遇到的各种情况与相关的处理原理与算法实现技巧,需要的朋友可以参考下
  • 二叉树的删除操作

    2019-04-08 09:00:33
    二叉树的删除时二叉树中所以操纵中做繁杂的一个,分为三种情况 1.被删除的节点点为叶节点 2.被删除的节点错在左子树或存在右子树 3.被删除节点左右节点均存在(最为繁杂的一种,需要通过与后继交换转化为前两种情况)...

    二叉树的删除时二叉树中所以操纵中做繁杂的一个,分为三种情况

     1.被删除的节点点为叶节点
    2.被删除的节点错在左子树或存在右子树
    3.被删除节点左右节点均存在(最为繁杂的一种,需要通过与后继交换转化为前两种情况)
    
    
    	下面我们对这些情况逐一分析
    	1.![在这里插入图片描述](https://img-blog.csdnimg.cn/20190408085857963.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L215SVRsaXZlQUFB,size_16,color_FFFFFF,t_70)
    
    展开全文
  • 二叉树的删除有很多种方法,只要删除后满足二叉树的性质即可。我们先看先看一颗二叉树。 例如我们要删除20这个节点。 1、把30变成根,10变成25的左孩子。 2、把10变成根,30变成10的右孩子。 这两种办法都可以...

      二叉树的删除有很多种方法,只要删除后满足二叉树的性质即可。我们先看先看一颗二叉树。

    例如我们要删除20这个节点。

    1、把30变成根,10变成25的左孩子。

    2、把10变成根,30变成10的右孩子。

    这两种办法都可以达到删除20的节点目的。

    我们可以这么做,是由二叉树的性质决定的。

    仔细观察这个树,我们会发现,20的左孩子都小于它,20的右孩子都大于它。所以经过1或2的操作,二叉树的性质并没有变。

    当然不止这两种方法,接下来介绍红黑树中使用的删除方法。

    还是以第一幅图为例,删除20节点。但在这里并不是删除20这个节点,而是找到一个适当的节点来替换20这个节点。

    这棵树中,我们还是可以找到两个点来替换20这个节点。10或者25。

    那么我们是怎么找到这两个点的呢?

    1、从删除节点的左子树找,找左子树中最大的节点。

      比如x是删除节点,他有左右孩子,Node *y = x->left; while (y->right != NULL ) y=y->right; 这样y就是x的左子树中的最大值。

    2、从删除节点的右子树找,找右子树中最小的节点。

      操作与找最大节点类似,把left变成right。

    找到这个替换节点后,将替换节点的其他信息替换成删除节点(值的信息除外)。这个替换节点,就是之前说的真正的删除节点。而20节点删除节点。

    无论哪种方法,都是为了维持二叉树的性质,只要在我们的操作之后,还能保持二叉树的性质,那我们的操作就算完成了。其次我们尽量让代码简洁易懂。

    转载于:https://www.cnblogs.com/ITgaozy/p/5153981.html

    展开全文
  • 二叉树的删除,要完成的操作(要求): 删除的是叶子结点,那就删除叶子结点 如果删除的是非叶子节点,将该节点置空 思路: 注意:如果是空树 root==null, 或者只有一个root节点,等价于把二叉树置空 1.二叉树是单向...
  • 本篇文章为博主对实现平衡二叉树的各种算法的补充,以下代码为平衡二叉树的删除算法的实现。 参考文章:https://blog.csdn.net/sysu_arui/article/details/7897017 具体代码实现 bool DeleteAVL(BiTree &T,int e...
  • 对于二叉树的删除节点的操作一般有三种情况 1.后继无人 就是该节点没有左孩子 右孩子 2.后继有右 就是该节点只有一个节点(可以是左孩子 也可以是右孩子) 3.后继有俩 就是该节点有左右孩子 情况1: 删除了该节点 则...
  • C#实现二叉查找树以及二叉树的删除 首先需要知道二叉树的基础知识,比父节点小的元素放在左边,大的放在右边 一.实现二叉查找树 对二叉树进行遍历查找 没有找到返回-1 二.实现二叉树的节点删除 二叉树的节点删除...
  • 二叉树的删除原理以及java实现

    千次阅读 2019-03-05 11:28:20
    相对于增查改,二叉树的删除是较为复杂的,必须保证删除后所有节点大于其左节点,小于其右节点。 删除节点分为几种情况: 1.删除的节点为叶子节点:直接删除。 2.删除的节点只存在左子树或右子树:删除节点的父...
  • 几分钟学会二叉树的删除

    千次阅读 2018-05-19 21:07:15
    树相对于链表等数据结构有很多优点,比如增删改查时间复杂度是O(lgn)(平均情况下),而链表需要逐一比较,故时间复杂度是O(n),今天讲下二叉树的删除。网上资料也很多,总感觉分析思路不是很清晰,希望可以帮助到...
  • 二叉树最复杂步骤即为删除操作,此处只简单介绍一下具体思路:(1)如果待删除的节点是一片树叶,那么它可以被立即删除。然后将其父节点相应子节点(左节点或右节点)至空。(2)如果被删除的节点有一个子节点,那么把...
  • Python 实现二叉树的创建、添加、删除、修改、查找
  • 平衡二叉树的删除也涉及到删除后的连接问题。其删除一般分为4种情况: (1)删除叶子结点 (2)删除的结点只有左子树,没有右子树 (3)删除的结点只有右子树,没有左子树 (4)删除的结点既有左子树,又有右子树 ...
  • 二叉树的删除策略

    2017-09-08 09:44:31
    删除有两个节点的二叉树节点的删除策略 找到右子树中值最小的节点,或者找到左子树中最大的节点,称之为最优值节点,这个节点的值是最适合提替换要删除节点的,替换值之后,删除最优值节点,因为最优值节点一定是...
  • 搜索二叉树的删除

    2018-08-29 19:56:31
    搜索二叉树删除比较麻烦,具体看代码里解释:(删除带有两个子节点节点需要用到中序后继节点)  //先寻找中序后继节点,再进行删除  //寻找中序后继节点  public Node getHouJiNode(Node delNode) { //...
  • 当一个白嫖党太久了,今儿写个作业,发现java顺序二叉树的删除的帖子不怎么多,于是乎打算自己也写一下。 二叉树的建立、遍历等暂且不论,直接搞上核心删除部分,但总感觉怪麻烦的,归根结底还是too vegetable,哎~~...
  • 最近在学习二叉树,对于二叉树的代码实现着实有些头疼,因为二叉树的实现主要依靠递归,而递归需要将节点的地址传入,那么该如何定义根节点呢? 难道要定义在类模板外面,主函数里面吗? 很明显这样是不可行的。那该...
  • 二叉树的删除操作 PTA

    2018-12-09 17:07:30
    分析:首先按照题目要求删除节点(书上的二叉树删除操作规则与这个略有不同,所以需要自己重新写) #include<stdio.h> #include<stdlib.h> #define max 105//看要求 #define FALSE 0...
  • 二叉树的删除节点2

    2019-03-16 12:02:55
    第二张情况: ... //只有两个节点的二叉树 删除了根节点 那么原来根节点右孩子 //就是新根节点 if(cur == root){ root = cur.rc; } //就是左孩子就是要寻找节点 else if(islc){ pre...
  • 2.网上数据结构和算法课程不少,但存在两个问题:1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好学员来说,还好一点,对基础不好学生来说,基本上就是听天书了2)说是讲数据...

空空如也

空空如也

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

二叉树的删除