Что такое min и max в этой функции, чтобы проверить, является ли двоичное дерево действительным BST?

Question

Код ниже Определение, является ли Двоичное дерево бинарным деревом поиска .

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
     return true;

    if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

Как здесь используются MIN и MAX?Какие ценности они представляют?И зачем их нужно пропускать через функцию?

Answer 1

[MIN, MAX] представляет диапазон, в котором может быть допустимое значение в текущем узле.Для первого узла это будут INT_MIN и INT_MAX, потому что он может иметь произвольные значения, но для его дочерних элементов нам нужно проверить свойство BST - все левые дочерние элементы не должны быть больше текущего узла, а все правые не должны быть меньше.,Вот почему мы меняем значения MIN и MAX для них уважительно.

ПРИМЕЧАНИЕ: если в дереве вы можете иметь повторяющиеся значения, измените проверку на:

 if(node.element >= MIN 
   && node.element <= MAX
   && IsValidBST(node.left,MIN,node.element)
   && IsValidBST(node.right,node.element,MAX))

Или вы получитеневерные результаты.

Answer 2

Вы должны вызвать функцию, как показано ниже.В которой INT_MIN и INT_MAX являются постоянными.

IsValidBST (root, INT_MIN, INT_MAX)

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

Чтобы выяснить, является ли данный BT BST для какого-либо типа данных, вам нужно пойти по следующему подходу.1. вызовите рекурсивную функцию до конца конечного узла, используя обход inorder. 2. Создайте свои минимальные и максимальные значения самостоятельно.

При условии, что элемент дерева должен иметь значение меньше или больше, чем определено оператором.

#define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal)
#define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal)

template <class T>
bool IsValidBST (treeNode &root)
{

   T min,  max;
   return IsValidBST (root, &min, &max);
}

template <class T>
bool IsValidBST (treeNode *root, T *MIN , T *MAX)
{
   T leftMin, leftMax, rightMin, rightMax;
   bool isValidBST;

   if (root->leftNode == NULL && root->rightNode == NULL)
   {
      *MIN = root->element;
      *MAX = root->element;
      return true;
   }

  isValidBST = IsValidBST (root->leftNode, &leftMin, &leftMax);

  if (isValidBST)
    isValidBST = IsValidBST (root->rightNode, &rightMin, &rightMax);

  if (isValidBST)
  {
     *MIN = MIN (leftMIN, rightMIN);
     *Max = MAX (rightMax, leftMax);
  }

  return isValidBST;
}

Answer 3

Здесь MIN MAX указывает минимальное значение, хранимое в дереве, и максимальное значение, хранимое в дереве.

I think simplest way to check the valid BST tree is traverse inorder and check if
the values are in sorted order or not? if all the values are in sorted order that
means its valid BST.

Осуществление http://justprogrammng.blogspot.com/2012/06/check-if-tree-is-bst-on-code-interview.html

Answer 4

Они должны быть переданы через функцию, чтобы она вызывалась рекурсивно с увеличением сокращенных диапазонов, как здесь.

Конечно, для первого вызова вы можете определить MIN и MAX издерево, но для последующих вы должны пройти как это.