Как определить, является ли Binary Tree BST

Question

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

   public bool CheckBST(BstNode root)
        {
            BstNode prev = new BstNode(Int32.MinValue);
            if (root == null)
                return true;
            if (root.left != null)
            {
                return CheckBST(root.left);
            }
            if (prev != null && prev.data >= root.data) // means data  is not sorted hence NOT   BST
                return false;
            prev = root;
            if(root.right!=null)
            {
                return CheckBST(root.right);
            }
            return true;
        }

Answer 1

Если бы вы могли заставить CheckBST возвращать диапазон (мин., Макс.) Проверяемого BST, тогда должна выполнить следующая рекурсивная функция:

// Defines the return value that represents BST check failure.
const pair<int, int> kCheckFailed(Int32.MaxValue, Int32.MinValue);

pair<int, int> CheckBST(const BstNode& curr)
{
  pair<int, int> left_ret(curr.value, curr.value);
  pair<int, int> right_ret(curr.value, curr.value);

  // Makes sure the left subtree, if any, is a BST, and its max
  // (`left_ret.second`) is no greater than `curr.value`
  if (curr.left) {
    left_ret = CheckBST(*curr.left);
    if (left_ret == kCheckFailed || left_ret.second > curr.value)
      return kCheckFailed;
  }

  // Makes sure the right subtree, if any, is a BST, and its min
  // (`right_ret.first`) is not less than `curr.value`.
  if (curr.right) {
    right_ret = CheckBST(*curr.right);
    if (right_ret == kCheckFailed || right_ret.first < curr.value)
      return kCheckFailed;
  }

  // Returns range by combining min of left subtree and max of right subtree.
  return make_pair(left_ret.first, right_ret.second);
}

Обратите внимание, что CheckBST принимает (суб) корень дерева по ссылке, чтобы убедиться, что узел (curr) всегда действителен.Однако curr.left или curr.right могут по-прежнему иметь значение NULL, и в этом случае соответствующие минимальные или максимальные значения, соответственно, равны просто curr.value, как инициализировано как ret_left, так и ret_right.

Answer 2

Учитывая двоичное дерево, следующее определяет, является ли оно действительным двоичным деревом поиска (BST).

• Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла.
• Правое поддерево узла содержит только узлы с ключами, которые больше ключа узла.
• И левое, и правое поддеревья также должны быть двоичными деревьями поиска.

Давайтесм. пример ниже:

Если вы видите вышеупомянутое двоичное дерево, это BST.

Теперь давайте рассмотрим другой пример:

Значение корневого узла равно 5, но значение его правого дочернего элемента равно 4, что не удовлетворяет условию, указанному выше.Таким образом, данное дерево не является BST.

Код решения:

Учитывая, что TreeNode определен как

public class TreeNode 
{
    public int Val { get; set; }
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }
    public TreeNode(int x) { this.Val = x; }
}

Код для проверкипроверка

public bool IsValidBST(TreeNode root) 
{
    return IsValidBST(root, int.MinValue, int.MaxValue);
}

private bool IsValidBST(TreeNode root, int minValue, int maxValue)
{
    if (root == null)
    {
        return true;
    }

    int nodeValue = root.Val;
    if (nodeValue < minValue || nodeValue > maxValue)
    {
        return false;
    }

    return IsValidBST(root.Left, minValue, nodeValue - 1) && IsValidBST(root.Right, nodeValue + 1, maxValue);
}

Теперь IsValidBST можно вызвать с корневым узлом

 bool isValidBST = IsValidBST(rootNode);

Answer 3

Вам не нужно пред .

1. Рекурсивно проверьте, что max (слева) меньше или равно корню.

2. Рекурсивно проверьте, что min (справа), если больше root.

3. Проверьте, является ли левым BST.

4. Проверьте, является ли правым BST.

Конечно, проверяйте нули там, где это необходимо.

Answer 4

Вы не можете инициализировать prev каждый раз в CheckBST.Вы можете сделать prev глобальным.Также я сделал prev как тип integer.

int prev = Int32.MinValue; //made this global and integer type

public bool CheckBST(BstNode root) {
 if (root == null)
  return true;
 bool isLeftBST = CheckBST(root.left);
 if (isLeftBST == false) return false;

 if (prev != Int32.MinValue && prev >= root.data) // means data  is not sorted hence NOT   BST
  return false;

 prev = root.data; //mark the prev before traversing the right subtree

 return isLeftBST && CheckBST(root.right);

}

Игнорировать проблемы синтаксиса, если таковые имеются.Я попробовал больше псевдокода.

Конечно, есть и другие способы решения этой проблемы.Как и отслеживание минимального и максимального значений (в ответе @ user1672994).

Answer 5

Так что обычно в BST есть три вещи в каждом узле.Это данные, и два указателя влево и вправо.Если в любом узле доступно более двух указателей, то это не BST.Вероятно, лучше всего определить на уровне узла, есть ли в нем больше указателей, чем должно быть.Вы будете тратить время и ресурсы на поиск в дереве.

Вот хороший способ сделать это https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/