Поиск, содержится ли значение в двоичном дереве

Question

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

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

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

Я хочу написать рекурсивный метод содержит (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.Я часами ковырялся в этом, и я уверен, что есть относительно тривиальное решение, но, похоже, я не могу его найти.

Answer 1

Примерно так:

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

Answer 2

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

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

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

    return false;
}

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

Answer 6

Ваш код не компилируется, потому что класс 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 result;
}

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

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 && 
        (node.value == i || contains(node.left, i) || contains(node.right, i));
}

Answer 7

Неправильно возвращать результат рекурсивного вызова без предварительной проверки, является ли он 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 && right != null) {
            found right.find(i);
        }
        return found;
    }
}