为了从一棵普通树中 bst

Question

为什么第一个写的代码产生错误而第二个没有。 我不明白的是，在这两个代码中我们都在操纵根指针那么为什么第一个不起作用但第二个起作用 （向量是正常 bst 的有序遍历） //代码1（显示分段错误

Node* makebst(Node* &root, vector<Node*> &vect, int start, int end){
    if(start>end){
        return NULL;
    }
    root=vect[((start+end)/2)+1];
    root->left=makebst(root->left, vect, start, (start+end)/2);
    
    root->right=makebst(root->left, vect, ((start+end)/2)+2, end);
    return root;
}
//code 2(corrected by chatgpt that actually worked
Node* makebst(Node* &root, vector<Node*>& vect, int start, int end) {
    if (start > end) {
        return NULL;
    }
    int mid = (start + end) / 2;
    root = vect[mid];
    root->left = makebst(root->left, vect, start, mid - 1);
    root->right = makebst(root->right, vect, mid + 1, end);
    return root;
}

代码 1 最初是我写的，但它不起作用我不明白为什么

Answer 1

当

start

和

end

相等时，表达式

((start+end)/2)+1

将返回

end+1

，这在

start..end

（含）范围之外。

这是一个双重问题：

• 当

  end

  是向量的最后一个有效索引时，

  vect

  中的这种访问会导致未定义的行为，这可能是一个分段错误。当向量的大小为 1 时会发生这种情况。

• 当

  end

  不是向量的最后一个有效索引时，这会导致递归调用具有相同的

  start

  和

  end

  值，从而导致无限递归并最终导致堆栈限制溢出。

更正后的代码使用

mid

的表达式，保证保持在

start

和

end

的范围内。

第二个问题（与您的问题无关）是您的代码从不对

root->right

做任何事情。