java - 使用 isLeaf、isParent 构建二叉树类问题，并且不确定权重

Question

我正在努力完成教授给我们的二叉树类(class)，并且我已经得到了运行得相当好的方法，但是在 isLeaf(E value) 和 isParent(E value) 方面遇到了一些问题。每种方法都有效，直到您添加与树中已有对象具有相同数据的内容为止。有什么方法可以确保它检查每个节点，而不是多次检查初始节点？我也不确定我的体重方法是否正确？到底如何计算二叉树的权重？

    public boolean isLeaf(E value){
            return this.isLeaf(root, value);
    }

    private boolean isLeaf(TreeNode<E> current, E value) {
        if (current == null){
            return false;
        }
        else if(current.getData().equals(value)) {
            if (current.getLeft() == null && current.getRight() ==null) {
                return true;
            }
            else{
                return false;
            }
        }
        else if (this.contains(current.getLeft(), value)) {
            return this.isLeaf(current.getLeft(), value);
        }
        else {
            return this.isLeaf(current.getRight(), value);        }
    }
    public boolean isParent(E value){
            return this.isParent(root, value);
    }

    private boolean isParent(TreeNode<E> current, E value) {
        if (current == null){
            return false;
        }
        else if(value.equals(current.getData())) {
            if (current.getLeft() != null || current.getRight() != null) {
                return true;
            }
            else{
                return false;
            }
        }
        else if (this.contains(current.getLeft(), value)) {
            return this.isParent(current.getLeft(), value);
        }
        else {
            return this.isParent(current.getRight(), value);
        }
    }

    public int height(){
        return this.height(root);
    }

    private int height(TreeNode<E> current) {
        if(current == null){
            return 0;
        }
        else{
            if(this.height(current.getRight()) < this.height(current.getLeft())){
                return 1 + this.height(current.getLeft());
            }
            else{
                return 1 + this.height(current.getRight());
            }
        }
    }

    public int weight(){
        return this.weight(root);
    }

    private int weight(TreeNode<E> current){
        if(current == null){
            return 0;
        }
        else{
            return 1 + this.height(current) * (this.weight(current.getLeft())
                     +  this.weight(current.getRight()));
        }
    }

Answer 1

请在下面找到您的问题的答案。

首先，二叉树的权重定义如下:重量(空树)= 0 |重量( fork (e,T,T')) = 1+重量(T)+重量(T')

其中 e 是完成 fork 的节点，T 和 T' 是左子树和右子树。

此外，您的重量方法需要稍作更改，如下所示

private int weight(TreeNode current){
            if(current == null){
                return 0;
            }
            else{
                return 1 + (this.weight(current.getLeft())
                         +  this.weight(current.getRight()));
            }

如果您仍然遇到任何问题，请粘贴完整的类(class)。

希望这有帮助。

干杯