Проблемы с классом двоичного дерева с isLeaf, isParent и неуверенностью в весе - PullRequest
Новая
       7

Проблемы с классом двоичного дерева с isLeaf, isParent и неуверенностью в весе

1 голос
/ 05 ноября 2011

Я работаю над завершением класса Binary Tree, данного нам нашим профессором, и у меня есть методы, которые работают довольно хорошо, но я столкнулся с некоторыми проблемами с 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()));
        }
    }

1 Ответ

0 голосов
/ 05 ноября 2011

Пожалуйста, найдите ответ на свой вопрос ниже.

Во-первых, вес бинарного дерева определяется следующим образом: вес (emptyTree) = 0 | вес (вилка (e, T, T ')) = 1 + вес (T) + вес (T')

где e - узел, в котором выполняется разветвление, а T и T '- левое и правое поддеревья.

Кроме того, ваш метод веса нуждается в небольшом изменении, как показано ниже 

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

Если у вас все еще есть проблемы, вставьте полный класс.

Надеюсь, это поможет.

Приветствия

...