Блог

У меня есть класс TreeNode, как показано ниже:

 class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

public TreeNode(int x) {
    value = x;
}
  

Я хочу написать рекурсивный метод contains(int i), который вернет true, если i является значением узла в дереве, и false в противном случае.

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

 public boolean contains(int i) {
    if (value == x) {
        return true;
    } else {
        if (left != null) {
            return left.find(i);
        }
        if (right != null) {
            return right.find(i);
        }
    }
    return false;
}
  

Мои мысли, стоящие за этим, заключались в том, что он проверил бы, равно ли значение текущего узла значению, которое мы ищем, и если нет, то он должен рекурсивно вызвать метод с левым и правым узлами, если они не равны null, в противном случае метод вернет false .

Этот метод в конечном итоге возвращает true, если мы ищем значение, соответствующее узлу слева от дерева, однако, как только мы ищем значение за пределами этого (справа), он вернет false . Я часами ломал голову над этим, и я уверен, что есть относительно тривиальное решение, но, похоже, я не могу до него добраться.

Что-то вроде этого:

 public boolean contains(int i) {
    return value == i ||
       left != null amp;amp; left.contains(i) ||
       right != null amp;amp; right.contains(i);
}
  

Неверно возвращать результат рекурсивного вызова, не проверив сначала, является ли это true или false .

Вам все равно следует выполнить поиск в правом поддереве, если поиск в левом поддереве возвращает false .

 public boolean contains(int i) {
    if (value == x) {
        return true;
    } else {
        boolean found = false;
        if (left != null) {
            found = left.find(i);
        }
        if (!found amp;amp; right != null) {
            found right.find(i);
        }
        return found;
    }
}
  

Это кажется более правильным:

 public boolean contains(int i) {
    if (value == x) {
        return true;
    } else {
        if (left != null amp;amp; left.find(i)) {
            return true;
        }
        if (right != null amp;amp; right.find(i)) {
            return true;
        }
    }
    return false;
}
  

     if (left != null) {
        return left.find(i);
    }
  

В этом проблема. Если есть как левый, так И правый узел, код вернет только то, было ли что-либо найдено с левой стороны.

Вместо этого вы хотите что-то вроде:

     boolean found = false;
    if (left != null) {
        found = left.find(i);
    }
    if (!found amp;amp; right != null) {
        found = right.find(i);
    }
    return found;
  

Ваша реализация предпочитает левое поддерево; она неправильно выполняет поиск в обоих поддеревьях. Это можно исправить следующим образом.

 public boolean contains(int i) {
    boolean Result = value == x;
    if (left != null) {
        Result |= left.find(i);
    }
    if (right != null) {
        Result |= right.find(i);
    }
    return Resu<
}
  

Эта реализация может быть дополнительно оптимизирована следующим образом для раннего возврата.

 public boolean contains(int i) {
    boolean Result = value == x;
    if (!Result amp;amp; left != null) {
        Result |= left.find(i);
    }
    if (!Result amp;amp; right != null) {
        Result |= right.find(i);
    }
    return Resu<
}
  

Ваш код, похоже, не является сложным, потому что у TreeNode класса нет find(int i) метода.

Я думаю, что contains() метод скорее должен выглядеть как:

 public boolean contains(TreeNode node, int i) {
  boolean result = node.value == i;
  if (left != null) result |= contains(node.left, i);
  if (right != null) result |= contains(node.right, i);
  return resu<
}
  

Конечно, вы можете завершить работу, как только значение найдено, и пропустить две != null проверки, добавив дополнительную рекурсию bottom в начале метода:

 public boolean contains(TreeNode node, int i) {
  if (node == null) return false;
  if (node.value == i) return true;
  return contains(node.left, i) || contains(node.right, i);
}
  

который может быть дополнительно упрощен до однострочного:

 public boolean contains(TreeNode node, int i) {
  return node != null amp;amp; 
        (node.value == i || contains(node.left, i) || contains(node.right, i));
}
  

Хотя я бы предпочел создать второй статический метод, который имеет в качестве параметров TreeNode и int , правильное исправление для вашего метода примерно такое:

 public boolean contains(int i) {
    if (value == x) {
        return true;
    }

    if (left != null amp;amp; left.find(i)) {
        return true;
    }
    if (right != null amp;amp; right.find(i)) {
        return true;
    }

    return false;
}
  

Ошибка в вашем коде заключается в том, что вы не даете шанса правому поддереву, если левое поддерево не содержит значения. Не возвращайте значение, если вы не уверены, что нет никаких других результатов.