Как написать базовый вариант для этой рекурсивной функции, которая удаляет потомков узлов, содержащих нечетные ключи?

Вот код, который у меня есть до сих пор, я думал, что возврат его из функции, если мое условие не будет выполнено, сработает, но его стек переполняется... Я знаю, что мне нужно установить базовый случай, но на самом деле не как....

 public void removeOddSubtrees() {
   if (root == null) {
     return;
   }
   removeOddSubtrees(root);
 }
 private void removeOddSubtrees(Node root) {    
   removeOddSubtrees(root);
   if (root.key % 2 != 0) {
     root.right = null;
     root.left = null;
     root = null;
    } else {
      return;
    }
}

java recursion recursive-datastructures binary-tree binary-search-tree
person gorgatron    schedule 19.04.2015    source источник
comment
Итак, в чем проблема? Где написано, что выбрасывается исключение? (Почему вы вызываете рекурсивный метод перед определением, является ли это узлом с нечетным ключом?)   -  person Makoto    schedule 19.04.2015
comment
у меня действительно нет базового случая, я не думаю... исключение составляет removeOddSubtrees (root)   -  person gorgatron    schedule 19.04.2015

Ответы (2)


arrow_upward
0
arrow_downward

я изменил свою вспомогательную функцию на следующую, и я думаю, что теперь она может работать:

private void removeOddSubtrees(Node root){
        if(root != null){
        removeOddSubtrees(root.left);
        removeOddSubtrees(root.right);
        if(root.key % 2 != 0){
            root.right = null;
            root.left = null;
            root = null;
        }else{
            return;
        }
    }
    }
person gorgatron    schedule 19.04.2015

arrow_upward
0
arrow_downward

код, который вы разместили в ответе, работает, но к нему можно применить некоторые упрощения. Вот как я бы это написал:

 private void removeOddSubtrees(Node root) {    
   if (root == null) {
     return;
   }

   if (root.key % 2 != 0) {
     root.right = null;
     root.left = null;
     return;
   }

   removeOddSubtrees(root.left);
   removeOddSubtrees(root.right);
}

Во-первых, я обычно проверяю условие выхода в самом верху и сразу же выхожу из метода. То есть мое условие делает return, если root == null.

Во-вторых, нет необходимости делать root = null, если root.key % 2 != 0. на самом деле это не имеет никакого эффекта: он помещает null в параметр, который получает функция, но поскольку этот параметр не используется после этого в этом методе, никто никогда не увидит этот null. Обратите внимание, что вызывающий код также не будет затронут. присвоение параметрам не распространяется за пределы вызываемого метода.

Наконец, я думаю, что имеет смысл вызывать removeOddSubtrees() для root.left и root.right только в том случае, если ключ четный. когда ключ нечетный, вы удаляете левое и правое поддеревья из дерева, поэтому выполнение рекурсивного вызова этих поддеревьев, вероятно, бессмысленно, поскольку вскоре после этого все это поддерево будет удалено из дерева. Таким образом, в моем коде я делаю рекурсивные вызовы, только если ключ четный.

person Itay Maman    schedule 19.04.2015