英文:
inorder to bst from a normal tree
问题
第一个写的代码为什么会出错，而第二个却没有。我不明白的是，在这两段代码中，我们都在操作根指针，为什么第一个不起作用，而第二个却可以（向量是普通二叉搜索树的中序遍历）。
//代码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;
}
//代码2（由ChatGPT修改后实际有效）
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;
}
第一个代码是我最初写的，但它不起作用，我不明白为什么。
英文:
why is the first written code generating error while second doesnt .
what i dont get is that in both the codes we are manipulating the root pointer then why is it that first one doesnt work but second one does
(vector is inorder traveral of a normal bst)
//code1 (showin segmentation fault
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;
}
code 1 was written by me at first but its not working i dont get it why
答案1
得分: 0
当start和end相等时，表达式((start+end)/2)+1将返回end+1，这超出了start..end（包括）范围。
这是一个双重问题：
-
当
end是向量的最后一个有效索引时，在vect中访问会导致未定义行为，可能会导致分段错误。当向量的大小为1时，会发生这种情况。 -
当
end不是向量的最后一个有效索引时，这会导致对具有相同值的start和end的递归调用，从而导致无限递归，并最终超出堆栈限制。
更正后的代码使用一个保证在start和end限制内的表达式来计算mid。
第二个问题（与您的问题无关）是您的代码从不使用root->right。
英文:
When start and end are equal, the expression ((start+end)/2)+1 will return end+1, which is outside of the start..end (inclusive) range.
That is a two-fold problem:
-
when
endis the last valid index of the vector, this access invectleads to undefined behaviour, which can be a segmentation error. This scenario happens when the vector has a size of 1. -
when
endis not the last valid index of the vector this leads to a recursive call that has the same values forstartandend, leading to infinite recursion and eventually a stack limit overrun.
The corrected code uses an expression for mid that is guaranteed to stay within the limits of start and end.
A second issue (unrelated to your question) is that your code never does anything with root->right.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论