BST方法返回Segfault

我正在寫一種方法來檢查給定的樹是否是使用inorder遍歷方法的BST。在執行這個方法時，我得到一個段錯誤。有人可以幫我糾正它嗎？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); 
}

來源

2015-01-16 WitchKingofAngmar

可能root爲空。你有沒有嘗試在調試器中運行你的代碼？ –

移動'isNull（root）;'在第一個'之前'if（root-> data ...）...;'。在訪問其數據之前，您需要檢查它是否爲NULL。 – Jeribo

@Jeribo嘗試這樣做。沒有好的 – WitchKingofAngmar

當你調用檢查（根 - >左），檢查（根 - >右）每次，我想你需要添加某物確定左，右分支爲空或不是。在你的代碼中，你只要假設左右分支有調用函數。我認爲這是主要原因。

來源

2015-01-16 22:29:14

我這樣做是在一個單獨的函數isNull – WitchKingofAngmar

@WitchKingofAngmar只要調用'isNull（root）'是不會做任何事情的。您必須使用檢查'isNull（root）'的總體if語句。如果它是假的，那麼你可以運行解引用'root'的代碼。 – 0x499602D2

您不應該指定最大值。 An elegant solution can be found here

來源

2015-01-17 00:11:55 lerman

有兩種方法可以做到這一點。

一種是自上而下的方法，首先檢查當前節點是否有效，如果是，則檢查兩個子樹。這非常直觀。你可以從@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的定義相沖突。

來源

2015-01-17 00:35:51 qqibrow

BST方法返回Segfault

回答

相關問題