Метод BST возвращает Segfault

Question

Я пишу метод проверки, является ли данное дерево BST, используя метод обхода порядка. При выполнении этого метода я получаю segfault. Может ли кто-нибудь помочь мне исправить это?

здесь максимальное значение наибольшего значения в BST, а k инициализировано равным 0. Предполагается, что BST имеет уникальные положительные значения. isNull (root) проверяет, является ли текущий узел нулевым узлом или нет.

bool check(BstNode* root) 
{ 

    if (root->data==maximum) return true; 
    isNull(root); 

    check(root->left); 

    if (root->data>k) 
    { 
     k=root->data; 

    } 
    else 
    { 
     return false; 
    } 

    check(root->right); 
} 

Answer 1

Каждый раз, когда вы звоните чек (корне-> слева) и проверьте (корне-> справа), я полагаю, вам нужно добавить н определить левый и правый ветви равна нулю или нет. В вашем коде вы просто предполагаете, что есть sth в левой и правой ветви и вызывают функцию проверки. Я думаю, что это главная причина.

Answer 2

Вам не нужно указывать максимальное значение. An elegant solution can be found here

Answer 3

Существует два подхода, которые вы можете сделать.

Один подход сверху вниз, сначала проверьте, действителен ли текущий узел, если да, то проверьте два поддерева. Это очень интуитивно. Вы можете найти код из @lerman's post:

struct TreeNode { 
    int data; 
    TreeNode *left; 
    TreeNode *right; 
}; 

bool isBST(TreeNode *node, int minData, int maxData) { 
    if(node == NULL) return true; 
    if(node->data < minData || node->data > maxData) return false; 

    return isBST(node->left, minData, node->data) && isBST(node->right, node->data, maxData); 
} 

if(isBST(root, INT_MIN, INT_MAX)) { 
    puts("This is a BST."); 
} else { 
    puts("This is NOT a BST!"); 
} 

Другой способ представляет собой подход снизу вверх: сначала проверьте левый substree затем правый substree и проверить текущее дерево наконец. ниже приведен код этого подхода.

bool isValidBST(TreeNode *root) { 
     int mmin, mmax; 
     return helper(root, mmin, mmax); 
    } 

    bool helper(TreeNode* root, int& mmin, int& mmax) { 
     if(!root) { 
      mmin = INT_MAX; 
      mmax = INT_MIN; 
      return true; 
     } 
     int leftmin, leftmax, rightmin, rightmax; 
     if(!helper(root->left, leftmin, leftmax)) 
      return false; 
     if(!helper(root->right, rightmin, rightmax)) 
      return false; 
     if(root->val > leftmax && root->val < rightmin) { 
      mmin = min(min(leftmin, rightmin), root->val); 
      mmax = max(max(leftmax, rightmax), root->val); 
      return true; 
     } 
     else 
      return false; 
    } 

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