0

嘿伙计们，我只是在二叉搜索树上练习递归代码。我遇到了一个段错误，但我不确定问题出在哪里（可能是一些愚蠢的东西盯着我的脸）。我还有其他运行良好的功能，例如计算节点数或计算树的高度。特别是这个功能给我带来了麻烦。我正在用 C++ 编写代码。

//wrapper function
int table::in_order_successor()
{
    node * temp;
    temp = root;
    in_order_successor(root, temp);  
}

//Find the in-order successor
int table::in_order_successor(node * root, node * temp)
{
    if(root == NULL) return 0;

    if(root->right != NULL)
             if(root->data == temp->data)
                    in_order_successor(root, temp->right);

    in_order_successor(root, temp->left);

    return temp->data;
}

我的想法是让函数从根开始向右走一次，然后尽可能向左走。如果我的 root->data 等于我的 temp->data （数据只是随机生成的 int），我只想让它正确运行。

4

2 回答 2

0

对于 Seg 错误，您应该检查是否temp是null，因为您的代码可能会传递给它temp->right，temp->left这可能是null.

  if(temp == NULL) return 0; // add this check

但是您的代码中还有另一个问题：您永远不会重用返回值。然后它只会迭代。假设您想在遍历后返回存储在叶子节点中的数据，那么代码可能如下所示：

//Find the in-order successor
int table::in_order_successor(node * root, node * temp) {
  if(root == NULL) return 0;
  if(temp == NULL) return 0; // add this check

  if(root->right != NULL) {
     // check by pointer instead of the data unless each
     // node->data is unique.  Otherwise unwanted moving
     // right will occur.
     if(root == temp) {           
       if (temp->right != null) {
         // use `return` here instead of plain function call to get
         // the update of the rest of the recursion.
         return in_order_successor(root, temp->right);
       }
     }
  }

  if (temp->left != null) {
    // if have left child, return what you will find in the next step
    return in_order_successor(root, temp->left); // use return here
  } else {
    // reach the left-most leaf after first steping right at root node.
    return temp->data;
  }
}
于 2013-06-13T22:22:18.863 回答
0

还

 if(temp->left != NULL)
    in_order_successor(root, temp->left);

和

if(!temp-> left)
  return temp->data;
于 2013-06-13T22:27:26.687 回答