gpt4 book ai didi

c++ - 二叉搜索树C++实现(动态内存问题)

转载 作者:太空宇宙 更新时间:2023-11-04 13:36:29 25 4
gpt4 key购买 nike

我目前正在学习如何实现二叉搜索树,但使用的是更基本的 C 方法(请不要“现在使用类”)。但是,动态内存自身删除存在一个大问题。 head 值得到正确更新,但是,每个其他点都会被删除。谁能帮我?此外,如果您能提供一些如何加强我对树的实现的提示,那就太好了。该程序的基本概要:您输入一个字符,然后运行树的功能之一。不过请注意,此实现是纯 BST,因此没有平衡。谢谢。

#include <iostream>

struct point{
point* parent, *left, *right;

int val = -1;
};

point* biggest;
point empty;

point search(int pos, bool near, point* loc = biggest){
if(loc->val == pos){
return *loc;
} else if(loc->left->val != -1 and loc->val > pos){
return search(pos, near, loc->left);
} else if(loc->right->val != -1){
return search(pos, near, loc->right);
}

if(near){
return *loc;
} else{
point fail;
return fail;
}
}

void insert(int pos, point* res){
point loc = search(pos, true);
res->val = pos, res->left = &empty, res->right = &empty, res->parent = &loc;
if(loc.val < res->val){
loc.left = res;
} else{
loc.right = res;
}

}

void remove(int pos){

}

int pred(int pos){
point res = search(pos, false);
if(res.val == -1){
return -1;
}

}

int succ(int pos){
point res = search(pos, false);
if(res.val == -1){
return -1;
}

}

void inorder(point* pos = biggest){
if(pos->left->val != -1){
inorder(pos->left);
}
std::cout << pos->val << " ";
if(pos->right->val != -1){
inorder(pos->right);
}
}

int main() {
point start;
start.parent = &empty, start.left = &empty, start.right = &empty;
biggest = &start;
char c;
int pos;
do{
std::cin >> c >> pos;

switch (c){
case 'S':
std::cout << search(pos, false).val << std::endl;
break;
case 'I':
if(biggest->val == -1){
start.val = pos;
} else{
point* res = new point;
insert(pos, res);
}
break;
case 'R':
remove(pos);
break;
case 'P':
std::cout << pred(pos) << std::endl;
break;
case 'N':
std::cout << succ(pos) << std::endl;
break;
case 'O':
inorder();
std::cout << std::endl;
break;
}
} while(c != '0');
return 0;
}

最佳答案

除了你的代码中有很多奇怪之处,我会在这里说:

void insert(int pos, point* res){
point loc = search(pos, true);
res->val = pos, res->left = &empty, res->right = &empty;
res->parent = &loc; // <=== here

您修改 res->parent 以指向局部变量 loc。在 insert() 函数返回后,point loc 不再存在。

此外,您已经在使用类; C++ 结构和类几乎相同......除了默认成员可见性。

关于c++ - 二叉搜索树C++实现(动态内存问题),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29378649/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com