精华内容
下载资源
问答
  • 单链表之删除节点

    2021-08-14 15:49:14
    1.删除节点的步骤 (1)找到要删除的这个节点:通过遍历来查找节点,从头指针+头节点开始,顺着链表依次将各个节点拿出来,按照一定的方法比对,找到我们要删除的那个节点。 (2)删除这个节点 (2.1)如果不是尾...

    1.删除节点的步骤
    (1)找到要删除的这个节点:通过遍历来查找节点,从头指针+头节点开始,顺着链表依次将各个节点拿出来,按照一定的方法比对,找到我们要删除的那个节点。
    (2)删除这个节点
    (2.1)如果不是尾节点:首先把待删除节点的前一个节点的pNext指向待删除节点的后一个节点的首地址,然后再将摘出来这个节点free掉。
    (2.2)如果这个节点是尾节点,首先把待删除这个节点的前一个节点的pNext指针指向NULL,然后再将摘出来这个节点free掉。

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    //构建链表节点
    struct node
    {
            int data;       //有效数据
            struct node *pNext;     //指向下一个节点的指针
    
    };
    
    
    //函数功能,创建链表节点
    //返回值:指针,指向我们本函数新创建的一个节点的首地址
    struct node *creat_node(int data)
    {
    
            //创建一个链表节点
            struct node *p = (struct node *)malloc(sizeof(struct node));
            if(NULL == p)
            {
                    printf("malloc error\n");
                    return NULL;
            }
    
    
            //清理申请到的堆内存
            // void bzero(void *s, size_t n);
            bzero(p,sizeof(struct node));
    
            //填充节点
            p->data = data;
            p->pNext = NULL;       //将来要指向下一个节点的首地址
    
            return p;
    }
    
    //重头部加入新节点
    void insert_head(struct node *pH,struct node *new)
    {
    
    /*      方法一:
             
            //第一步:新节点的pNext指向第一个节点
            new->pNext = pH->pNext;
            //第二部:头结点的pNext指向新节点
            pH->pNext = new;
            //第三部:头结点的计数加1
            pH->data += 1;
    */
            //方法二:
    
            //先保存第一个节点
            struct node *p1 = pH->pNext;
            //让头结点的pNext指向新节点
            pH->pNext = new;
            //新节点的pNext指向保存好的第一个节点
            new->pNext = p1;
            //头结点计数加1
            pH->data += 1;
    }
    
    /有头节点遍历
    void bianli2(struct node *pH)
    {
            struct node *p = pH;  //头指针后面是头节点这样初始化下面会打印头结点的数据
    
            printf("开始遍历==================\n");
    
            while(NULL != p->pNext)
            {
                    p = p->pNext;
                    printf("node data = %d\n",p->data);
            }
    
            printf("遍历完成==================\n");
    }
    
    //从链表pH中删除节点,待删除节点的数据区的值等于data
    //返回值:当找到节点并成功删除返回0,未找到这个节点返回-1
    int delete_node(struct node *pH,int data)
    {
            struct node *p = pH;    //头指针后面的头节点(用来指向当前节点)
            struct node *pp = NULL;         //用来指向当前节点的前一个节点
    
            while(NULL != p->pNext) //判断是不是最后一个节点
            {
                    pp = p;         //用来保留前一个节点的状态
                    p = p->pNext;   //走向下一个节点,也就是循环增量
    
                    if(p->data == data)     //判断这个节点是否是我们想要删除的那个节点
                    {
                            if(NULL == p->pNext)    //1.如果找到的是尾节点
                            {
                                    pp->pNext = NULL;       //原来尾节点的前一个为节点变成了新尾节点
                                    free(p);        //释放原来尾节点的内存
                            }
                            else    //如果找到的是普通节点
                            {
                                    pp->pNext = p->pNext;   //要删除的节点的前一个节点和后一个节点相连
                                    free(p);
                            }
    
    
                            return 0;
                    }
            }
            //到这里还没有找到,就说明链表中没有我们想要的那个节点
            printf("没找到这个节点\n");
            return -1;
    
    }
    
    int main(void)
    {
            //定义头指针
            //struct node *pHeader = NULL;  这里如果把pHeader赋值为NULL在加入节点这个函数内就会出现段错误
            struct node *pHeader = creat_node(0);
    
            insert_head(pHeader,creat_node(1));
    
            insert_head(pHeader,creat_node(2));
    
            insert_head(pHeader,creat_node(3));
    
    
            printf("header node data = %d\n",pHeader->data);        //打印有多少个节点
    
            //bianli(pHeader);
            printf("删除前================\n");
            bianli2(pHeader);
            delete_node(pHeader,1);
            printf("删除后================\n");
            bianli2(pHeader);
    
            return 0;
    }
    
    

    输出结果

    展开全文
  • 数据结构 - 二叉树(删除节点)

    千次阅读 2020-02-02 15:35:41
    因为二叉树是单向的,所以要判断当前节点的子节点(左... //规定:如果是叶子节点就删除节点,如果非叶子节点就删除子树 public void delNode(int no){ if (this.left !=null && this.left.no == no){ thi...

    在这里插入图片描述

    因为二叉树是单向的,所以要判断当前节点的子节点(左或右)是否是被删除的节点

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

        //递归删除节点
        //规定:如果是叶子节点就删除节点,如果非叶子节点就删除子树
        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 (root != null){//判断root是不是要删除的节点
                if (root.getNo() == no){
                    root = null;
                }else {
                    root.delNode(no);
                }
            }
        }
    

    完整代码

    package tree;
    
    public class BinaryTreeDemo {
        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, "关胜");
    
            //说明,先手动创建该二叉树,后面学习递归方式创建二叉树
            binaryTree.setRoot(root);
            root.setLeft(node2);
            root.setRight(node3);
            node3.setRight(node4);
            node3.setLeft(node5);
    
            //测试
    //        System.out.println("前序遍历");
    //        binaryTree.preOrder();
    //        System.out.println("中序遍历");
    //        binaryTree.infixOrder();
    //        System.out.println("后序遍历");
    //        binaryTree.postOrder();
    
            //测试查找
            //前序遍历查找
    //        System.out.println("前序遍历查找:~~~~");
    //        HeroNode heroNode1 = binaryTree.preOrederSearch(5);
    //        if (heroNode1 != null){
    //            System.out.println("找到节点:" + heroNode1.toString());
    //        }else {
    //            System.out.println("没有找到");
    //        }
    //
            //中序遍历查找
    //        System.out.println("中序遍历查找:~~~~");
    //        HeroNode heroNode2 = binaryTree.infixOrderSeach(5);
    //        if (heroNode2 != null){
    //            System.out.println("找到节点:" + heroNode2.toString());
    //        }else {
    //            System.out.println("没有找到");
    //        }
    //
    //        //后序遍历查找
    //        System.out.println("后序遍历查找:~~~~");
    //        HeroNode heroNode3 = binaryTree.postOrderSeach(5);
    //        if (heroNode3 != null){
    //            System.out.println("找到节点:" + heroNode3.toString());
    //        }else {
    //            System.out.println("没有找到");
    //        }
    
    
            //删除前
            System.out.println("删除前,前序遍历");
            binaryTree.preOrder();
            binaryTree.delNode(3);
            System.out.println("删除后,前序遍历");
            binaryTree.preOrder();
        }
    }
    
    class BinaryTree{
        private 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 infixOrder(){
            if (this.root != null){
                this.root.infixOrder();
            }else {
                System.out.println("二叉树为空无法遍历");
            }
        }
        //后序遍历
        public void postOrder(){
            if (this.root != null){
                this.root.postOrder();
            }else {
                System.out.println("二叉树为空无法遍历");
            }
        }
    
        //前序查找
        public HeroNode preOrederSearch(int no){
            if (root != null){
                return root.preOrderSearch(no);
            }else {
                return null;
            }
        }
        //中序查找
        public HeroNode infixOrderSeach(int no){
            if (root != null){
                return root.infixOrderSearch(no);
            }else {
                return null;
            }
        }
        //后序查找
        public HeroNode postOrderSeach(int no){
            if (root != null){
                return root.postOrderSearch(no);
            }else {
                return null;
            }
        }
    
        //删除节点
        public void delNode(int no){
            if (root != null){//判断root是不是要删除的节点
                if (root.getNo() == no){
                    root = null;
                }else {
                    root.delNode(no);
                }
            }
        }
    
    }
    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 + '\'' +
                    '}';
        }
        //编写前序遍历方法
        public void preOrder(){
            System.out.println(this);//先输出父节点
            //递归向左子树前序遍历
            if (this.left != null){
                this.left.preOrder();
            }
            //递归向右子树前序遍历
            if (this.right != null){
                this.right.preOrder();
            }
        }
        //编写中序遍历方法
        public void infixOrder(){
    
            //递归向左子树前序遍历
            if (this.left != null){
                this.left.infixOrder();
            }
    
            System.out.println(this);//输出父节点
    
            //递归向右子树前序遍历
            if (this.right != null){
                this.right.infixOrder();
            }
        }
        //编写后序遍历方法
        public void postOrder(){
            if (this.left != null){
                this.left.postOrder();
            }
    
            if (this.right != null){
                this.right.postOrder();
            }
            System.out.println(this);
        }
        public static int i = 1, j = 1, k =1;
        //编写前序查找方法
        public HeroNode preOrderSearch(int no){
            System.out.println("前序遍历"+(i++)+"次");
            if (this.no == no){
                return this;
            }
            HeroNode heroNode = null;
            if (this.left != null){
                heroNode = this.left.preOrderSearch(no);
            }
            //不等于空说明在左边找到了
            if (heroNode != null){
                return heroNode;
            }
            if (this.right != null){
                heroNode = this.right.preOrderSearch(no);
            }
            return heroNode;
        }
    
        //中序遍历查找
        public HeroNode infixOrderSearch(int no){
    
            HeroNode heroNode = null;
            //先判断当前节点的左子节点是否为空,不为空继续进行中序查找
            if (this.left != null){
                heroNode = this.left.infixOrderSearch(no);
            }
            if (heroNode != null){
                return heroNode;
            }
            System.out.println("中序遍历"+(j++)+"次");
            if (this.no == no){
                return this;
            }
            if (this.right != null){
                heroNode = this.right.infixOrderSearch(no);
            }
    
            return heroNode;
        }
    
        //后序遍历查找
        public HeroNode postOrderSearch(int no){
    
            HeroNode heroNode = null;
            //判断当前节点的左子节点是否为空,不为空,则递归后序遍历查找
            if (this.left != null){
                heroNode = this.left.postOrderSearch(no);
            }
            if (heroNode != null){
                return heroNode;
            }
            //判断当前节点的右子节点是否为空,不为空,则递归后序遍历查找
            if (this.right != null){
                heroNode = this.right.postOrderSearch(no);
            }
            if (heroNode != null){
                return heroNode;
            }
            System.out.println("后序遍历"+(k++)+"次");
            //左右子树都没有找到,比较当前节点是不是
            if (this.no == no){
                return this;
            }
            return heroNode;
        }
    
        //递归删除节点
        //规定:如果是叶子节点就删除节点,如果非叶子节点就删除子树
        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);
            }
    
        }
    }
    
    
    
    展开全文
  • 最完整二叉树删除节点

    千次阅读 2020-11-26 18:40:34
    二叉树删除节点 在自己研究二叉树删除节点时,查网上资料时发现,网上大部分写的都是错的,主要错在当删除节点既存在左子树,又存在右子树时,在中序遍历后获取后继节点后,大部分文章未考虑后继节点存在右子树的...

    二叉树删除节点

    在自己研究二叉树删除节点时,查网上资料时发现,网上大部分写的都是错的,主要错在当删除的节点既存在左子树,又存在右子树时,在中序遍历后获取后继节点后,大部分文章未考虑后继节点存在右子树的情况。

    1.二叉树图

    在这里插入图片描述
    删除的节点有4种情况

    1. 叶子节点
    2. 只存在左节点
    3. 只存在右节点
    4. 既存在左节点,又存在右节点

    以上四种情况分别如下处理:

    1只需要将引用去除就行
    2将删除节点的左子树,挂到父节点上
    3将删除节点的右子树,挂到父节点上
    4中序遍历树,获取删除节点的后继节点,即大于删除节点的最小节点,后继节点可以确定的是肯定不存在左子树,因为后继节点就是删除节点右子树里面最小的节点了,肯定不存在比他还小的节点。但是还是有可能存在右子树的 。处理逻辑就是将后继节点的值覆盖删除节点的值,并将后继节点的右子树挂到后继节点的父节点上。

    下面就是硬干代码了,有个技巧,中序遍历出来的结果正好是升序排列的树,所以在删除后,可以通过打印中序遍历的结果,查看整棵树是不是正确的。

    2.节点数据结构

    public static class Node<T>{
            private T data;
            private Node<T> left;
            private Node<T> right;
            private Node<T> parent;
            public Node(T data) {
                this.data = data;
            }
            public T getData() {
                return data;
            }
            public Node<T> getParent() {
                return parent;
            }
            public void setParent(Node<T> parent) {
                this.parent = parent;
            }
            public void setData(T data) {
                this.data = data;
            }
            public Node<T> getLeft() {
                return left;
            }
            public void setLeft(Node<T> left) {
                this.left = left;
            }
            public Node<T> getRight() {
                return right;
            }
            public void setRight(Node<T> right) {
                this.right = right;
            }
        }
    

    3.先序创建树

    // 创建树
    public static Node<String> createTree(List<String> dataList,Node<String> parent){
            Node<String> root = null;
            if(!dataList.isEmpty()){
                String data = dataList.remove(0);
                if(data!=null){
                    root=new Node<>(data);
                    root.setParent(parent);
                    root.setLeft(createTree(dataList,root));
                    root.setRight(createTree(dataList,root));
                }
            }
    
            return root;
        }
        
        //二叉树初始化
        List<String> strings = new ArrayList<>();
            strings.add("20");
            strings.add("7");
            strings.add("3");
            strings.add("2");
            strings.add(null);
            strings.add(null);
            strings.add("4");
            strings.add(null);
            strings.add(null);
            strings.add("10");
            strings.add("8");
            strings.add(null);
            strings.add("9");
            strings.add(null);
            strings.add(null);
            strings.add("12");
            strings.add(null);
            strings.add(null);
            strings.add("30");
            strings.add("25");
            strings.add(null);
            strings.add("26");
            strings.add(null);
            strings.add(null);
            strings.add("35");
            strings.add(null);
            strings.add(null);
            tree = createTree(strings,null);
            
    

    4.删除操作

    // 删除节点
    public static String deleteNode(Node<String> tree,String value){
    
            //找到指定节点
            Node<String> deleteNode = findNode(tree, value);
            //节点不存在直接返回
            if(deleteNode==null){
                return null;
            }
    		//原值
            String result = deleteNode.getData();
    
            //判断子节点情况
            //及存在左子树又存在右子树
            if(deleteNode.getLeft()!=null && deleteNode.getRight()!=null){
                //对整个树中序遍历,以获取删除节点的后继节点(大于删除节点的最小节点)
                Node<String> afterNode = findAfterNode(tree, deleteNode);
                //删除节点与后继节点值替换
                deleteNode.setData(afterNode.getData());
    
                //当前节点一定不存在左子树,有可能存在右子树
                if(afterNode.getRight()==null){
                    //当不存在右子数时,直接跟删除节点交换
                    deleteNode.setData(afterNode.getData());
                    //将对后继节点的引用置空
                    Node<String> parent = afterNode.getParent();
                    if(parent.getLeft()==afterNode){
                        parent.setLeft(null);
                    }else{
                        parent.setRight(null);
                    }
                    afterNode.setParent(null);
                }else{
                    //当存在右子树时,将右子数挂在后继节点的父节点下
                    Node<String> parent = afterNode.getParent();
                    if(parent.getLeft()==afterNode){
                        parent.setLeft(afterNode.getRight());
                    }else{
                        parent.setRight(afterNode.getRight());
                    }
                     afterNode.getRight().setParent(parent);
                }
    
            }else if(deleteNode.getLeft()!=null && deleteNode.getRight()==null){
                //只存在左子树
                //父节点指向左子树
                Node<String> parent = deleteNode.getParent();
                if(parent.getLeft()==deleteNode){
                    parent.setLeft(deleteNode.getLeft());
                }else{
                    parent.setRight(deleteNode.getLeft());
                }
                afterNode.getLeft().setParent(parent);
    			afterNode.setParent(null);
            }else if(deleteNode.getLeft()==null && deleteNode.getRight()!=null){
                //只存在右子树
                Node<String> parent = deleteNode.getParent();
                if(parent.getLeft()==deleteNode){
                    parent.setLeft(deleteNode.getRight());
                }else{
                    parent.setRight(deleteNode.getRight());
                }
                afterNode.getRight().setParent(parent);
                afterNode.setParent(null);
            }else{
                //叶子节点
                //将指向该节点父节点置空
                Node<String> parent = deleteNode.getParent();
                if(parent.getLeft()==deleteNode){
                    parent.setLeft(null);
                }else{
                    parent.setRight(null);
                }
                afterNode.setParent(null);
            }
            return result;
        }
    
    //节点查询
    public static <A extends String> Node<A> findNode(Node<A> root,A value){
            if(root ==null){
                return null;
            }
            Node<A> cnode = root;
            while(cnode!=null){
                if(value.compareTo(cnode.getData())==0){
                    return cnode;
                }
    
                if(Integer.parseInt(value)<Integer.parseInt(cnode.getData())){
                    cnode=cnode.left;
                    continue;
                }
    
                if(Integer.parseInt(value)>Integer.parseInt(cnode.getData())){
                    cnode=cnode.right;
                    continue;
                }
            }
            return null;
        }
    
    // 找到指定节点的后继节点
    public static Node<String> findAfterNode(Node<String> root,Node<String> targetNode){
            ArrayList<Node<String>> list = new ArrayList<>();
            midSercharStack(root,list);
            for (int i = 0; i < list.size(); i++) {
                if(Integer.valueOf(list.get(i).getData())==Integer.valueOf(targetNode.getData())){
                    return list.get(++i);
                }
            }
            return null;
        }
    //中序遍历树,并保存到列表中	
     public static void midSercharStack(Node<String> root, ArrayList<Node<String>> list){
         if(root==null){
             return;
         }
         midSercharStack(root.left,list);
         list.add(root);
         midSercharStack(root.right,list);
     }
    

    5.中序遍历方法 递归+非递归

    
    //非递归 中序遍历
    public static void midPrintNoback(Node<String> root){
       LinkedList<Node<String>> stack = new LinkedList<>();
        Node<String> p = root;
        while(p!=null || !stack.isEmpty()){
    
            if(p!=null){
                stack.push(p);
                p=p.left;
    
            }else{
                Node<String> pop = stack.pop();
                System.out.println(pop.getData());
                p=pop.right;
            }
        }
     }
     //递归中序遍历
    public static void midPrint(Node<String> root){
        if(root==null){
            return;
        }
        midPrint(root.getLeft());
        System.out.println(root.getData()==null?"":root.getData());
        midPrint(root.getRight());
    }
    

    6.测试

     public static void main(String[] args) {
    		//先打印一遍树
            midPrint(tree);
            System.out.println("-------");
            //删除最复杂的 7节点
            String s = deleteNode(tree, "7");
            //打印删除后的树
            midPrint(tree);
        }
    

    结果如下,可以发现,删除后,节点7已经不在了
    在这里插入图片描述

    7.附插入时,定位要插入的父节点

    public static <A extends String> Node<A> findInsertNode(Node<A> root,A value){
       if(root ==null){
           return null;
       }
       Node<A> cnode = root;
       Node<A> pnode=null;
       while(cnode!=null){
           if(Integer.parseInt(value)<=Integer.parseInt(cnode.getData())){
               pnode=cnode;
               cnode=cnode.left;
               continue;
           }
    
           if(Integer.parseInt(value)>Integer.parseInt(cnode.getData())){
               pnode=cnode;
               cnode=cnode.right;
               continue;
           }
       }
       return pnode;
    }
    
    展开全文
  • 删除节点分为三种情况:1,当要删除节点的是叶子结点的时候;2,当要删除节点只有一个子节点或子树的时候;3,当要删除节点同时有左右两棵子树的时候。 对于第一种情况,要删除节点是叶子结点的时候,...

    步骤:首先,我们先从根节点开始查找到要删除的这个节点,然后删除该节点,然后再妥善安置该该节点的子树或子节点。

    要删除的节点分为三种情况:1,当要删除的节点的是叶子结点的时候;2,当要删除的节点只有一个子节点或子树的时候;3,当要删除的节点同时有左右两棵子树的时候。

    对于第一种情况,要删除的节点是叶子结点的时候,删除的办法是直接删除掉该节点即可;

    对于第二种情况,要删除的节点有一个子节点或子树的时候,删除的办法是先将该节点删除,然后将它的子节点或子树直接挪到该节点的位置即可。

    对于第三种情况,要删除的节点同时有左右两颗子树的时候,删除的办法是分为两种情况:

    1,先找到右子树中最小的那个节点、或者左子树中最大的那个节点,然后删除该删除的节点,然后将右子树中最小的那个节点或者左子树中最大的那个节点,挪到删除的位置即可。

    2,如果右子树中最小的那个节点有一个右子节点,或者左子树中最大的那个节点有一个左子结点,此时删除的办法是:先删除该删除的节点,然后将右子树中最小的那个节点或者左子树中最大的那个节点,挪到删除的位置,然后将右子树中最小的那个节点的右子节点,或者左子树中最大的那个节点的左子结点,挪到右子树中最小的那个节点、或者左子树中最大的那个节点的位置即可。

    3,如果右子树中最小的那个节点有左右两个节点,或者左子树中最大的那个节点有左右两个结点,这种情况是不可能的,因为此时右子树中最小的那个节点肯定就是该节点的左子结点了,左子树中最大的那个节点肯定就是该节点的右子节点了。

    写不下去、烂尾的代码...

     /**
           * 删除节点:
           * @param rootNode:根节点,用来找到指定的要删除的节点
           * @param value:要删除的节点的值
           */
          public void deleteLeafNode(BinaryTreeNode rootNode, int value) {
                //1,寻找该节点:
                if (null == rootNode) {
                      return;
                } else {
                      BinaryTreeNode leftNode = rootNode.getLeftNode();
                      BinaryTreeNode rightNode = rootNode.getRightNode();
                      if (leftNode != null) {
                            if (leftNode.getNodeValue() == value) {
                                  //1,如果该节点是叶子结点:—— 则直接删除该节点
                                  if (null == leftNode.getLeftNode() && null == leftNode.getRightNode()) {
                                        rootNode.setLeftNode(null);
                                  }
                                  //2,如果该节点有一个子节点/子树:——先删除该节点,然后将其子节点上位挪到该节点的位置;
                                  if (null == leftNode.getLeftNode() && null != leftNode.getRightNode()) {
                                        rootNode.setLeftNode(leftNode.getRightNode());
                                  } else if (null != leftNode.getLeftNode() && null == leftNode.getRightNode()) {
                                        rootNode.setLeftNode(leftNode.getLeftNode());
                                  }
                                  //3,如果该节点有两个子节点/子树:——先删除该节点,然后将其该节点的左子树的最大节点或者右子树的最小节点上位挪到该节点的位置;
                                  if (null != leftNode.getLeftNode() && null != leftNode.getRightNode()) {
                                        //以将该节点的右子树的最小节点上位为例:
                                        BinaryTreeNode leftNodeRightNode = leftNode.getRightNode();
                                        BinaryTreeNode minNode = qryRightChildMinNode(leftNodeRightNode);
                                        //3.1,如果该节点的右子树的最小节点为叶子结点,则直接上位挪到该节点的位置即可;
    
                                        //3.2,如果该节点的右子树的最小节点有一个右子节点,
                                        //          则先将这个右子树的最小节点上位到该节点的位置,
                                        //          然后将这个右子树的最小节点的右子节点上位到这个右子树的最小节点的位置;
                                        //写不下去了,就这吧...
    
    
                                  }
    
    
                            }
                      }
                      if (rightNode != null) {
    
                      }
    
                }
          }
    
    
          /**
           * 查找该节点的右子树中的最小节点:
           * @param node 该节点的右子节点
           */
          BinaryTreeNode minBinaryTreeNode = null;
    
          public BinaryTreeNode qryRightChildMinNode(BinaryTreeNode node) {
                if (null == node) {
                      return minBinaryTreeNode;
                } else {
                      minBinaryTreeNode = node;
                      BinaryTreeNode leftNode = node.getLeftNode();
                      BinaryTreeNode rightNode = node.getRightNode();
                      minBinaryTreeNode = leftNode.getNodeValue() < minBinaryTreeNode.getNodeValue() ? leftNode : minBinaryTreeNode;
                      minBinaryTreeNode = rightNode.getNodeValue() < minBinaryTreeNode.getNodeValue() ? rightNode : minBinaryTreeNode;
                      qryRightChildMinNode(leftNode);
                      qryRightChildMinNode(leftNode);
                }
                return minBinaryTreeNode;
          }

    展开全文
  • 单链表的算法之删除节点 1.为什么要删除节点 (1)有时候链表节点中的数据不想要了,因此要删掉这个节点。 2.删除节点的2个步骤 (1)第一步:找到要删除的节点;第二部:删除这个节点 3.如何找到待删除的节点 (1)通过遍...
  • 二叉树删除节点(C语言)

    千次阅读 2021-05-02 15:31:17
    二叉树删除节点 删除分为四种情况 这个节点左右孩子都有 这个节点没有左右孩子 这个节点只有左孩子 这个节点只有右孩子 1.查找节点位置 struct TreeNode *p = NULL;//遍历指针 struct TreeNode *fp = NULL;//...
  • 单链表删除节点

    千次阅读 2020-11-07 11:09:50
    //给定单向链表的头指针和一个要删除节点的值,定义一个函数删除节点。 //返回删除后的链表的头节点
  • 二叉树删除结点

    2019-11-02 21:18:41
    跳到结点遍历删除部分,判断根结点的左子树是否为空且判读左节点是否为删除结点,是则左子树置空; 判断右子树是否为空且是否为删除结点,是则右子树置空; 递归左子树; 递归右子树; //删除结点 public...
  • 首先看一下普通搜索二叉树的删除操作,普通搜索二叉树删除结点找替代结点有3种情情景: 情景1:删除结点无子结点,直接删除 情景2:删除结点只有一个子结点 情景3:删除结点有两个子结点 在这里有一个...
  • 二叉树——删除节点

    2020-02-28 23:28:26
    二叉树-删除节点 思路分析
  • 二叉排序树的定义:形如图1所示,每棵二叉树有一个根节点,根节点下面至多有两个子节点,每个节点只能最多有两个分支节点,并且左侧分支子节点数值小于父节点数值,右侧子节点数值大于父节点数值。 ...
  • 【3】彻底删除节点标签名,需要删除前期对该标签名建立的索引 问题描述: 数据库里已经创建好了节点和关系,现在想删除BC_Company、BC_Knowledge、BC_Person、Coin这4类节点,但是它们之间存在复杂的关系。 先...
  • 二叉排序树删除结点

    2021-06-20 22:28:19
    由于删去叶子结点不破坏整棵树的结构,则可以直接删除此子结点。 若p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点f的左子树(当p是左子树)或右子树(当p是右子树)即可,作此修改也不破坏二叉...
  • 红黑树删除节点——这一篇就够了

    千次阅读 多人点赞 2019-10-11 11:38:24
    红黑树常用的操作是插入、删除和查找,并且它对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保,对于红黑树的概念、性质、插入、查找和旋转等这里不再多讲,不了解的请点击wikipedia rb-tree,这里重点...
  • jquery删除节点

    千次阅读 2018-05-23 22:20:04
    jquery提供了3中删除节点的方法。分别是remove()、detach()、empty()。1、remove()方法1.1、$(selector).remove()的使用 解释:删除匹配到的文档中的元素节点,同时返回删除的节点引用。我们可以在后面的业务如果...
  • QTreeWidget删除节点及子节点

    千次阅读 2020-09-06 17:53:58
    QTreeWidget删除节点及子节点方案一方案二 方案一 删除当前选中的节点及其子节点。 该代码存在问题,在删除子节点的时候,并未对孙子节点进行处理。 QTreeWidgetItem* item=ui->analogTreeWidget->currentItem...
  • 一、链表中删除第i个结点 int main() { int i; Node *p,*head,*k; head=setlink(); scanf("%d",&i); int v=1; for(p=head->next;p!=NULL;k=p,p=p->next) { if(v==i)break; else{ v++; ...
  • 二叉树是每个结点最多有两个子树的树结构。使用广泛,使用C来实现对二叉树的操作。 示例:代码实现构造如下二叉树 #include <iostream> using namespace std; typedef struct BinaryTree { int data; ...
  • 9.5.1 为什么要删除节点 (1)一直在强调,链表到底用来干嘛的? (2)有时候链表节点中的数据不想要了,因此要删掉这个节点。 9.5.2 删除节点的2个步骤 (1)第一步:找到要删除的节点;第二步:删除这个节点; ...
  • 双链表删除节点

    千次阅读 2021-02-22 15:22:20
    编写一个程序,从双链表中移除一个节点,函数的原型如下 int dll_remove(struct NODE *rootp, struct NODE *node); 你可以假设节点数据结构在头文件double_linked_list_node.h文件中定义,函数第一个参数是一个...
  • 如果删除结点是叶子节点,则删除节点 如果删除结点是非叶子节点,则删除该子树 思路: 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要...
  • 删除节点 删除一个BST的节点要比插入困难一点,但同样是要遵循一个原则,即:删除节点后仍然要保持“小-中-大”的逻辑关系。 假设要删除的节点是x,大体思路如下: 若要删除的节点小于根节点,则递归地在左子树中...
  • 删除树的结点是树的操作之中相对比较复杂的。 本文基于二叉排序树的基础上进行树的结点删除操作,删除结点后还要保持二叉树的有序。 考虑三种情况: (1)要删除的是叶结点:先查找到这个结点,直接删除, 并再...
  • 主要介绍了C语言实现带头结点的链表的创建、查找、插入、删除操作方法,对于了解数据结构中链表的各项操作有很好的借鉴价值,需要的朋友可以参考下
  • k8s添加删除节点

    千次阅读 2019-07-30 16:08:29
    kubectl get nodes #查看节点 添加节点: master初始化成功后注意将kubeadm join xxx保存下来,等下node节点需要使用。如果忘记了,可以在master上通过kubeadm token list得到。 默认token 24小时就会过期,后续...
  • 二叉查找树 - 删除节点 详解(Java实现)

    万次阅读 多人点赞 2018-05-17 12:18:31
    在浏览 二叉查找树(三)之 Java的实现 时,发现所有操作都很容易理解,只有删除看的很糊涂。原文作者在方法上也没有任何注释,因此理解起来很不容易。因此本文是在这篇的基础上,对删除操作进行详细的讲解,所以如果...
  • 单链表删除节点的方法

    千次阅读 2019-02-27 14:12:07
    public class ListNode { int val; ListNode next;...删除一个单链表里的某个指定的节点: 1.修改指针指向的对象   public static void deleteNodeV2(ListNode head, ListNode node) { if(...
  • 邻接表O(1)删除节点

    2019-09-29 10:45:34
    文章目录邻接表建图删除节点...以前我就以为删除节点要从头结点开始找,找到之后才删除,这个方法的复杂度就是线性的 然后今天才知道阔以O(1)O(1)O(1)删除,就是把后面的节点直接覆盖上去 比如这里以删除③节点为...
  • 二分搜索树的删除节点操作

    千次阅读 多人点赞 2017-12-23 21:50:45
    本节我们来讨论一下对二叉搜索树的删除节点操作。 首先,我们先来研究一下稍微简单一点的问题,如何删除二叉树中的最小值和最大值。 例如上图的这一棵二叉树中,最小值节点和最大值节点都在哪里呢?我们可以很清楚...
  • //从链表中删除节点: 需要找到带删除节点前面的节点,找到这个节点后,修改它的next属性,使其不再指向带删除的节点,而是指向带删除节点的下一个节点 function findPrevious(item) { var currentNode=this.head...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,006,816
精华内容 402,726
关键字:

删除节点

友情链接: 电子锁.zip