二叉搜索树，编码问题
Binary search tree, coding issue
由于某些奇怪的原因，我的 BST 树并没有真正按预期运行，这是我编写的代码：
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <limits.h>
//Creating the main structure of the main BST Tree
struct treeNode{
int key; //The key of the node
struct treeNode *leftChild; //The left child of the node
struct treeNode *rightChild; //The right child of the node
struct treeNode *parent; //The parent of the node
};
//Function for implementing and creating a new node in the BST
struct treeNode* newNode(int x){
struct treeNode *n;
n = malloc(sizeof(struct treeNode));
n->key = x;
n->leftChild = NULL;
n->rightChild = NULL;
n->parent = NULL;
return n;
}
//Function for finding the minimun value in a treeNode
struct treeNode* BSTTreeMin(struct treeNode *root){
if(root->leftChild == NULL){
return root; //if the left child is nil, return the root
}
else{
return BSTTreeMin(root->leftChild); //otherwise we repeform the same operation on the left child
}
}
//Function for searching a specific node in the BST
struct treeNode* BSTTreeSearch(struct treeNode *root,int x){
if(root == NULL || root->key == x){
return root; //if root corresponds to key then the element x is found
}
if(x < root->key){
return BSTTreeSearch(root->leftChild, x); // in the case where the element x is smaller than root-->key then it searches the left child
}
else{
return BSTTreeSearch(root->rightChild, x);// in the opposite case, it searches the right child
}
}
//function for inserting a new key in the BST
struct treeNode* BSTTreeInsert(struct treeNode *root, struct treeNode *z){
struct treeNode *y = NULL;
struct treeNode *x = root;
while(x != NULL){
y = x;
if(z->key <= x->key){
x = x->leftChild;
}
else{
x = x->rightChild;
}
}
z->parent = y;
if(y == NULL){
root = z;
}
else if(root != NULL && z->key <= y->key){
y->leftChild = z;
}
else{
y->rightChild = z;
}
}
struct treeNode* BSTTreeTransplant(struct treeNode *root, struct treeNode *u, struct treeNode *v){
if(u->parent == NULL){
root = v;
}
else if(u == u->parent->leftChild){
u->parent->leftChild = v;
}
else{
u->parent->rightChild = v;
}
if(v != NULL){
v->parent = u->parent;
}
}
//function for delete a node in a BST
struct treeNode* BSTTreeDelete(struct treeNode *root, struct treeNode *z){
if(z->leftChild == NULL){
BSTTreeTransplant(root, z, z->rightChild);
}
else if(z->rightChild == NULL){
BSTTreeTransplant(root, z, z->leftChild);
}
else{
struct treeNode *y = BSTTreeMin(z->rightChild);
if(y->parent != z){
BSTTreeTransplant(root, y, y->rightChild);
y->rightChild = z->rightChild;
y->rightChild->parent = y;
}
BSTTreeTransplant(root, z, y);
y->leftChild = z->leftChild;
y->leftChild->parent = y;
}
}
//Function for emptying a BST
void BSTTreeDeallocate(struct treeNode *root){
if(root == NULL){
return;
}
BSTTreeDeallocate(root->leftChild);
BSTTreeDeallocate(root->rightChild);
free(root);
}
//function that checks if the Bst is valid (antagonistic function)
int isValidBstHelper(struct treeNode *root, int low, int high) {
return root == NULL ||
(root->key >= low && root->key <= high &&
isValidBstHelper(root->leftChild, low, root->key) &&
isValidBstHelper(root->rightChild, root->key, high));
}
//function that initiate the validity check of the Bst
int isValidBst(struct treeNode *root) {
return isValidBstHelper(root, INT_MIN, INT_MAX);
}
//Main experiment function for this program, calculating the time for inserting, deleting and searching nodes in our BST
double SingleExperiment(int max_keys,double max_search,double max_delete,int max_instances){
double t_tot = 0;
int i;
int key;
double search;
double delete;
for(i = 1; i <= max_instances; i++){
clock_t start_t, end_t;
srand(0);
struct treeNode *root;
root = newNode(rand()); // Initializing the root of the tree
struct treeNode *i = newNode(rand());
struct treeNode *d = newNode(rand());
start_t = clock();
for(key = 1; key <= max_keys; key++){
BSTTreeInsert(root,i); //Starting with the insertion of the nodes
}
for(search = 1; search <= max_search; search++){
BSTTreeSearch(root, rand()); //Following by the searching of the nodes
}
for(delete = 1; delete <= max_delete; delete++){
BSTTreeDelete(root, d); //Finally, the deletion of the nodes
}
end_t = clock();
double t_elapsed = (double)(end_t - start_t); //Calculation of the time elapased
t_tot += t_elapsed; //Adding the time to the total time
//inorder(root); //checks if the BST is in order --> prints an ordered array
//Checking if the Bst is valid
if (isValidBst(root)) {
printf("The tree is a valid BST \n");
} else {
printf("The tree is NOT a valid BST \n");
}
BSTTreeDeallocate(root); //Emptying the tree
}
return t_tot/max_keys; //Returning the average time
}
//main function (represents the experiment function)
int main(void){
int min_keys = 5;
int max_keys = 10;
int max_instances = 5;
int percentage_search = 60;
int keys;
int seed = 0;
//setting up the main parameters for the experiment
printf("Binary Search Tree \n");
for(keys = min_keys; keys <= max_keys; keys = keys +1){
srand(seed);
double max_search = keys * percentage_search / 100;
double max_delete = keys - max_search;
double time = SingleExperiment(keys,max_search,max_delete,max_instances);
printf("%d %f\n",keys,time);//printing the time associate to each key value
seed = seed +1;
}
return 0;
}
每次迭代的结果应该是“树是有效的”，以及每个键数的总时间。每当我启动该程序时，它只打印出“二进制搜索树”而没有其他内容。
你能帮帮我吗？
在此先感谢大家！
主要问题出现在这个循环中：
for(key = 1; key <= max_keys; key++){
BSTTreeInsert(root,i);
}
忽略 i 作为节点变量名的错误选择（它已经用作循环变量），这将插入 same 节点反复。这意味着此循环的第二次迭代将插入一个已经在树中的节点。这将使节点成为自己的子节点（自引用）。因此，此循环的第三次迭代将永远不会到达树中的叶子，因为它一直遵循该自我引用，运行 转圈。
快速修复是在每次迭代中插入 new 个节点：
for(key = 1; key <= max_keys; key++){
BSTTreeInsert(root, newNode(rand());
}
现在，这解决了您的问题，但我仍然想指出，实验代码的其余部分并没有多大用处：
BSTTreeSearch 非常非常有可能用树中没有出现的值调用，并且没有测试函数 returns 是否确实是预期结果.但是也应该有 positive 测试——看看树中 are 的值是否真的被找到了。
BSTTreeDelete 与 same 节点重复调用。此外，此节点从未插入树中，因此这些调用永远不会从树中删除任何节点。
您可能想对此进行改进 -- 但它超出了您的问题范围。
由于某些奇怪的原因，我的 BST 树并没有真正按预期运行，这是我编写的代码：
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <limits.h>
//Creating the main structure of the main BST Tree
struct treeNode{
int key; //The key of the node
struct treeNode *leftChild; //The left child of the node
struct treeNode *rightChild; //The right child of the node
struct treeNode *parent; //The parent of the node
};
//Function for implementing and creating a new node in the BST
struct treeNode* newNode(int x){
struct treeNode *n;
n = malloc(sizeof(struct treeNode));
n->key = x;
n->leftChild = NULL;
n->rightChild = NULL;
n->parent = NULL;
return n;
}
//Function for finding the minimun value in a treeNode
struct treeNode* BSTTreeMin(struct treeNode *root){
if(root->leftChild == NULL){
return root; //if the left child is nil, return the root
}
else{
return BSTTreeMin(root->leftChild); //otherwise we repeform the same operation on the left child
}
}
//Function for searching a specific node in the BST
struct treeNode* BSTTreeSearch(struct treeNode *root,int x){
if(root == NULL || root->key == x){
return root; //if root corresponds to key then the element x is found
}
if(x < root->key){
return BSTTreeSearch(root->leftChild, x); // in the case where the element x is smaller than root-->key then it searches the left child
}
else{
return BSTTreeSearch(root->rightChild, x);// in the opposite case, it searches the right child
}
}
//function for inserting a new key in the BST
struct treeNode* BSTTreeInsert(struct treeNode *root, struct treeNode *z){
struct treeNode *y = NULL;
struct treeNode *x = root;
while(x != NULL){
y = x;
if(z->key <= x->key){
x = x->leftChild;
}
else{
x = x->rightChild;
}
}
z->parent = y;
if(y == NULL){
root = z;
}
else if(root != NULL && z->key <= y->key){
y->leftChild = z;
}
else{
y->rightChild = z;
}
}
struct treeNode* BSTTreeTransplant(struct treeNode *root, struct treeNode *u, struct treeNode *v){
if(u->parent == NULL){
root = v;
}
else if(u == u->parent->leftChild){
u->parent->leftChild = v;
}
else{
u->parent->rightChild = v;
}
if(v != NULL){
v->parent = u->parent;
}
}
//function for delete a node in a BST
struct treeNode* BSTTreeDelete(struct treeNode *root, struct treeNode *z){
if(z->leftChild == NULL){
BSTTreeTransplant(root, z, z->rightChild);
}
else if(z->rightChild == NULL){
BSTTreeTransplant(root, z, z->leftChild);
}
else{
struct treeNode *y = BSTTreeMin(z->rightChild);
if(y->parent != z){
BSTTreeTransplant(root, y, y->rightChild);
y->rightChild = z->rightChild;
y->rightChild->parent = y;
}
BSTTreeTransplant(root, z, y);
y->leftChild = z->leftChild;
y->leftChild->parent = y;
}
}
//Function for emptying a BST
void BSTTreeDeallocate(struct treeNode *root){
if(root == NULL){
return;
}
BSTTreeDeallocate(root->leftChild);
BSTTreeDeallocate(root->rightChild);
free(root);
}
//function that checks if the Bst is valid (antagonistic function)
int isValidBstHelper(struct treeNode *root, int low, int high) {
return root == NULL ||
(root->key >= low && root->key <= high &&
isValidBstHelper(root->leftChild, low, root->key) &&
isValidBstHelper(root->rightChild, root->key, high));
}
//function that initiate the validity check of the Bst
int isValidBst(struct treeNode *root) {
return isValidBstHelper(root, INT_MIN, INT_MAX);
}
//Main experiment function for this program, calculating the time for inserting, deleting and searching nodes in our BST
double SingleExperiment(int max_keys,double max_search,double max_delete,int max_instances){
double t_tot = 0;
int i;
int key;
double search;
double delete;
for(i = 1; i <= max_instances; i++){
clock_t start_t, end_t;
srand(0);
struct treeNode *root;
root = newNode(rand()); // Initializing the root of the tree
struct treeNode *i = newNode(rand());
struct treeNode *d = newNode(rand());
start_t = clock();
for(key = 1; key <= max_keys; key++){
BSTTreeInsert(root,i); //Starting with the insertion of the nodes
}
for(search = 1; search <= max_search; search++){
BSTTreeSearch(root, rand()); //Following by the searching of the nodes
}
for(delete = 1; delete <= max_delete; delete++){
BSTTreeDelete(root, d); //Finally, the deletion of the nodes
}
end_t = clock();
double t_elapsed = (double)(end_t - start_t); //Calculation of the time elapased
t_tot += t_elapsed; //Adding the time to the total time
//inorder(root); //checks if the BST is in order --> prints an ordered array
//Checking if the Bst is valid
if (isValidBst(root)) {
printf("The tree is a valid BST \n");
} else {
printf("The tree is NOT a valid BST \n");
}
BSTTreeDeallocate(root); //Emptying the tree
}
return t_tot/max_keys; //Returning the average time
}
//main function (represents the experiment function)
int main(void){
int min_keys = 5;
int max_keys = 10;
int max_instances = 5;
int percentage_search = 60;
int keys;
int seed = 0;
//setting up the main parameters for the experiment
printf("Binary Search Tree \n");
for(keys = min_keys; keys <= max_keys; keys = keys +1){
srand(seed);
double max_search = keys * percentage_search / 100;
double max_delete = keys - max_search;
double time = SingleExperiment(keys,max_search,max_delete,max_instances);
printf("%d %f\n",keys,time);//printing the time associate to each key value
seed = seed +1;
}
return 0;
}
每次迭代的结果应该是“树是有效的”，以及每个键数的总时间。每当我启动该程序时，它只打印出“二进制搜索树”而没有其他内容。 你能帮帮我吗？
在此先感谢大家！
主要问题出现在这个循环中：
for(key = 1; key <= max_keys; key++){
BSTTreeInsert(root,i);
}
忽略 i 作为节点变量名的错误选择（它已经用作循环变量），这将插入 same 节点反复。这意味着此循环的第二次迭代将插入一个已经在树中的节点。这将使节点成为自己的子节点（自引用）。因此，此循环的第三次迭代将永远不会到达树中的叶子，因为它一直遵循该自我引用，运行 转圈。
快速修复是在每次迭代中插入 new 个节点：
for(key = 1; key <= max_keys; key++){
BSTTreeInsert(root, newNode(rand());
}
现在，这解决了您的问题，但我仍然想指出，实验代码的其余部分并没有多大用处：
BSTTreeSearch非常非常有可能用树中没有出现的值调用，并且没有测试函数 returns 是否确实是预期结果.但是也应该有 positive 测试——看看树中 are 的值是否真的被找到了。BSTTreeDelete与 same 节点重复调用。此外，此节点从未插入树中，因此这些调用永远不会从树中删除任何节点。
您可能想对此进行改进 -- 但它超出了您的问题范围。