cj云 2023-03-11 16:53 采纳率: 40%
浏览 53
已结题

java的数据结构的删除del的方法

想问写java的大师想为什么我删除节点的方法为什么实现不了
BinaryTree创建二叉树


public class BinaryTree {


    private Hero root;
    Scanner myScanner =new Scanner(System.in);

    public Hero createBinary() {

        Hero hero = null;

        System.out.println("你是否需要创造新节点  y/n");
        String key = myScanner.next();
        if ("y".equals(key)) {
            System.out.print("请输入 id = ");
            int id = myScanner.nextInt();
            System.out.print("请输入 name = ");
            String name = myScanner.next();
            hero = new Hero(id, name);
        } else if ("n".equals(key)) {
//            hero = null;
            return null;
        }

        hero.setLeftChild(createBinary());
        hero.setRightChild(createBinary());
        return hero;
        }
//        Hero p = root;
//        if (p == null) {
//            root = hero;
//            return;
//        } else {
//            if (p.getLeftChild() == null) {
//                p.setLeftChild(hero);
//                p = p.getLeftChild();
//            } else if (p.getRightChild() == null) {
//                p.setRightChild(root);
//                p = p.getRightChild();
//            }
//        }
    public Hero getRoot() {
        return root;
    }

    public void setRoot(Hero root) {
        this.root = root;
    }
}

Hero节点类

public class Hero {
    private Hero leftChild;
    private Hero rightChild;
    private int id;
    private String name;
    private int tag = 0;//0为未遍历,1为已遍历

    public int getTag() {
        return tag;
    }

    public void setTag(int tag) {
        this.tag = tag;
    }

    public Hero(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public Hero getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(Hero leftChild) {
        this.leftChild = leftChild;
    }

    public Hero getRightChild() {
        return rightChild;
    }

    public void setRightChild(Hero rightChild) {
        this.rightChild = rightChild;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
    @Override
    public String toString() {
        return "Hero{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

}

DeleteTree删除节点的方法

public class DeleteTree {

    private static Scanner myScanner = new Scanner(System.in);
    public static void del(Hero tree, int id) {
        Stack<Hero> stack = new Stack<>();

        Hero p = tree;
        if (p == null) {
            System.out.println("该二叉树为空...");
            return;
        } else {
            while (p != null) {
                if (p.getId() == id) {
                    p = null;
                }
                else {
                    if (p.getRightChild() != null) {
                        stack.push(p.getRightChild());
                    }
                    if (p.getLeftChild() != null) {
                        p = p.getLeftChild();
                    } else if (!stack.empty()) {
                        p = stack.pop();
                    } else {
                        break;
                    }
                }
            }
        }
    }

}

TraMain实现main方法在这实现测试del方法

public class TraMain {

    static Scanner myScanner = new Scanner(System.in);

    public static void main(String[] args) {

        TraMain traMain = new TraMain();
        BinaryTree binaryTree = new BinaryTree();
        Hero BinaryTree = binaryTree.createBinary();//这样子一颗二叉树就搞好了
        System.out.println("===============递归前序遍历===============");
        traMain.preTravers(BinaryTree);//前序遍历

        DeleteTree.del(BinaryTree, 2);

        System.out.println("===============递归前序遍历===============");
        traMain.preTravers(BinaryTree);//前序遍历
        /**
        System.out.println("===============递归中序遍历===============");
        traMain.inorderTra(BinaryTree);
        System.out.println("===============递归后序遍历===============");
        traMain.postTra(BinaryTree);
        System.out.println("===============非递归前序遍历===============");
        traMain.nonRePreTra(BinaryTree);
        System.out.println("===== 中序非递归遍历(order) / 后序非递归遍历(post) =====");
        System.out.print("请输入 order 或 post: ");
        String key = myScanner.next();
        if ("order".equals(key)) {
            System.out.println("===============非递归中序遍历===============");
            traMain.nonReorderTra(BinaryTree);
        } else {
            System.out.println("===============非递归后序遍历===============");
            traMain.nonRepostTra(BinaryTree);
        }
**/
    }

    //前序遍历二叉树的方法
    public void preTravers(Hero tree) {
        Hero p = tree;

        if (p == null) {
            return;
        }

        System.out.println(p);

        preTravers(p.getLeftChild());
        preTravers(p.getRightChild());
    }

    public void inorderTra(Hero tree) {
        Hero p = tree;

        if (p == null) {
            return;
        }

        inorderTra(p.getLeftChild());
        System.out.println(p);
        inorderTra(p.getRightChild());

    }

    public void postTra(Hero tree) {
        Hero p = tree;

        if (p == null) {
            return;
        }

        postTra(p.getLeftChild());
        postTra(p.getRightChild());
        System.out.println(p);
    }

    public void nonRePreTra(Hero tree) {
        Stack<Hero> stack = new Stack<Hero>();
        Hero p = tree;

        if (p == null) {
            return;
        }

        while (p != null) {

            if (p.getRightChild() != null) {
                stack.push(p.getRightChild());
            }
            System.out.println(p);
            if (p.getLeftChild() != null) {
                p = p.getLeftChild();
            } else if (stack.size() > 0) {
                p = stack.pop();
            } else {
                    p = null;
            }

        }
    }

    public void nonReorderTra(Hero tree) {
        Stack<Hero> stack = new Stack<Hero>();
        Hero p = tree;

        if (p == null) {
            return;
        }

        while (p != null) {
            while (p.getLeftChild() != null && p.getLeftChild().getTag() == 0) {
                stack.push(p);
                p = p.getLeftChild();
            }
            System.out.println(p);
            p.setTag(1);
            if (p.getRightChild() != null) {
                p = p.getRightChild();
            } else if (stack.size() != 0){
                p = stack.pop();
            } else {
                p = null;
            }
        }
    }

    public void nonRepostTra(Hero tree) {
        Stack<Hero> stack = new Stack<Hero>();
        Hero p = tree;

        if (p == null) {
            return;
        }
        while (p != null) {
            while (p.getLeftChild() != null && p.getLeftChild().getTag() == 0) {
                stack.push(p);
                p = p.getLeftChild();
            }
            if (p.getRightChild()  != null && p.getRightChild().getTag() == 0) {
                stack.push(p);
                p = p.getRightChild();
            } else {
                System.out.println(p);
                p.setTag(1);
                if (stack.size() != 0) {
                    p = stack.pop();
                } else if (stack.size() == 0) {
                    p = null;
                }
            }
        }
    }
}
  • 写回答

3条回答 默认 最新

  • VenYy 2023-03-11 17:00
    关注

    你的代码中有一些问题需要修正。首先,在二叉树创建方法 createBinary() 中,当用户输入 'n' 时,应该返回 null 而不是赋值为 null。其次,在节点删除方法 del() 中,你只是设定要删除的节点为空,但并没有实际上删除它,所以需要对删除操作进行改进。

    以下是修改建议:

    BinaryTree类中修改如下:

    public Hero createBinary() {
        // your code...
            } else if ("n".equals(key)) {
                return null;
            }
        // your code...
    }
    

    DeleteTree类中修改如下:

    public static void del(Hero tree, int id) {
    
            if (tree == null) {
                System.out.println("该二叉树为空...");
                return;
            }
    
            Hero p = tree;
            Hero parent = null;
            boolean isLeftChild = true;
    
            while (p != null && p.getId() != id) {
                parent = p;
                if (id < p.getId()) {
                    isLeftChild = true;
                    p = p.getLeftChild();
                } else {
                    isLeftChild = false;
                    p = p.getRightChild();
                }
            }
            if (p == null) {
                System.out.println("未找到待删除节点");
                return;
            }
    
            // 如果待删除节点是叶子节点
            if (p.getLeftChild() == null && p.getRightChild() == null) {
                if (p == tree) {
                    tree = null;
                } else if (isLeftChild) {
                    parent.setLeftChild(null);
                } else {
                    parent.setRightChild(null);
                }
            }
            // 如果待删除节点只有左子节点
            else if (p.getRightChild() == null) {
                if (p == tree) {
                    tree = p.getLeftChild();
                } else if (isLeftChild) {
                    parent.setLeftChild(p.getLeftChild());
                } else {
                    parent.setRightChild(p.getLeftChild());
                }
            }
            // 如果待删除节点只有右子节点
            else if (p.getLeftChild() == null) {
                if (p == tree) {
                    tree = p.getRightChild();
                } else if (isLeftChild) {
                    parent.setLeftChild(p.getRightChild());
                } else {
                    parent.setRightChild(p.getRightChild());
                }
            }
            // 如果待删除节点有两个子节点
            else {
                Hero successor = getSuccessor(p);
    
                if (p == tree) {
                    tree = successor;
                } else if (isLeftChild) {
                    parent.setLeftChild(successor);
                } else {
                    parent.setRightChild(successor);
                }
    
                successor.setLeftChild(p.getLeftChild());
            }
        }
    
        /**
         * 获取待删除节点的后继节点
         */
        private static Hero getSuccessor(Hero delNode) {
            Hero successorParent = delNode;
            Hero successor = delNode;
            Hero current = delNode.getRightChild();
    
            while (current != null) {
                successorParent = successor;
                successor = current;
                current = current.getLeftChild();
            }
    
            if (successor != delNode.getRightChild()) {
                successorParent.setLeftChild(successor.getRightChild());
                successor.setRightChild(delNode.getRightChild());
            }
    
            return successor;
        }
    

    这里建议你创建一个新的 Hero 类型的引用来保存删除节点的父节点,这个应该在删除节点时比较容易处理。同时,如果要删除的节点有左右子节点时,需要寻找它的后继节点来替代它,保证删除后仍然是一棵二叉树。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 3月20日
  • 已采纳回答 3月12日
  • 创建了问题 3月11日

悬赏问题

  • ¥15 在获取boss直聘的聊天的时候只能获取到前40条聊天数据
  • ¥20 关于URL获取的参数,无法执行二选一查询
  • ¥15 液位控制,当液位超过高限时常开触点59闭合,直到液位低于低限时,断开
  • ¥15 marlin编译错误,如何解决?
  • ¥15 有偿四位数,节约算法和扫描算法
  • ¥15 VUE项目怎么运行,系统打不开
  • ¥50 pointpillars等目标检测算法怎么融合注意力机制
  • ¥20 Vs code Mac系统 PHP Debug调试环境配置
  • ¥60 大一项目课,微信小程序
  • ¥15 求视频摘要youtube和ovp数据集