如何使用二叉搜索树实现优先级队列 [英] How to implement priority queue using binary search tree
问题描述
我正在尝试使用二进制搜索树为优先级队列实现优先级队列函数PQ_DeleteMin（），PQ_GetMinKey（）。二叉搜索树包含获取k个最近节点的附加信息。任何人都可以帮助我如何在C中实现这一目标吗？谢谢。
我尝试过：
插入代码节点写为：
节点*插入（节点*树， void * 对象， float （*距离）（ void *， void *））
{
if （ Tree == NULL）{
if （（Tree =（Node *）malloc（ sizeof （节点）））== NULL）{
printf（ 内存不足）;
退出（ 1 ）;
}
Tree-> p1 = 对象;
Tree-> p2 = NULL;
Tree-> left = Tree-> right = NULL;
}
else if （Tree-> p2 = = NULL）
Tree-> p2 = 对象;
else if （（* Distance）（Tree-> p1， 对象）<（*距离）（树 - > p2，对象））
insert（Tree-> left， Object ，Distance）;
else insert（Tree-> right， Object ，Distance）;
return （树）;
}
我们不做你的功课：这是有原因的。它就是为了让你思考你被告知的事情，并试着理解它。它也在那里，以便您的导师可以识别您身体虚弱的区域，并将更多的注意力集中在补救措施上。
亲自尝试，你可能会发现它不是和你想的一样困难！
如果遇到具体问题，请询问相关问题，我们会尽力提供帮助。但是我们不会为你做这一切！
我们不做你的HomeWork。
HomeWork不会测试你的技能在乞求其他人们做你的工作，它会让你思考并帮助你的老师检查你对你所学课程的理解，以及你应用它们时遇到的问题。
你的任何失败都会帮助你的老师发现你的弱点并设定补救措施。
你的任何失败都会帮助你了解什么有效，什么无效，被称为'试错'学习。
所以，试一试，重读课程并开始工作。如果您遇到特定问题，请显示您的代码并解释这个问题，我们可能会提供帮助。
作为程序员，您的工作是创建算法解决特定问题，你不能依赖别人永远为你做，所以有一段时间你必须学会如何。而且越快越好。
当你要求解决方案时，就像试图通过培训其他人来学习开车一样。
创建算法基本上是找到数学并做出必要的调整以适应你的实际问题。
[更新]
建议：正确缩进你的代码，缩进显示代码的结构并使其更易于阅读。
节点*插入（节点*树， void * 对象， float （*距离）（ void *， void *））
{
if （树== NULL）{
if （（Tree =（Node *）malloc（ sizeof （ Node）））== NULL）{
printf（ 内存不足）;
退出（ 1 ）;
}
Tree-> p1 = 对象;
Tree-> p2 = NULL;
Tree-> left = Tree-> right = NULL;
}
else if （Tree-> p2 = = NULL）
Tree-> p2 = 对象;
else if （（* Distance）（Tree-> p1， 对象）<（*距离）（树 - > p2，对象））
insert（Tree-> left， Object ，Distance）;
else insert（Tree-> right， Object ，Distance）;
return （树）;
}
专业程序员的编辑有此功能。
Notepad ++ Home [ ^ ]
UltraEdit |原始文本编辑器 [ ^ ]
建议：不要在1行中打包超过需要的代码，它不会保存任何内容，也不会更快，只是更难阅读。
节点*插入（节点*树，无效 * 对象， float （* Distance）（ void *， void *））
{
if （Tree == NULL）{
Tree =（Node *）malloc（ sizeof （Node））;
if （（Tree == NULL）{
printf（ 内存不足）;
退出（< span class =code-digit> 1 ）;
}
Tree-> p1 = 对象;
Tree-> p2 = NULL;
Tree-> left = Tree-> right = NULL;
}
else if （Tree-> p2 == NULL）
Tree-> p2 = 对象;
else if （（* Distance）（树 - > p1， Object ）<（* Distance）（Tree-> p2， Object ））
insert（Tree- >左，对象，距离）;
其他
insert（树 - >右，对象，距离）;
返回（树）;
}
建议：不要学习用C语言编程。使用C语言，您负责内存管理，数组边界，内存泄漏等所有细节。处理这些细节会使学习变得更加困难。
使用真正的高级语言，如BASIC，Java或C＃，它们被编组并告诉你什么时候出现问题，比如在数组结束后读取。
I am trying to implement Priority queue functions PQ_DeleteMin(), PQ_GetMinKey() for Priority Queue with Binary Search Tree. The binary search tree contains additional information to get the k nearest nodes. Can any one help me how to achieve that in C? Thanks.
What I have tried:
The code for inserting a node is written as:
Node *insert(Node *Tree, void *Object, float (*Distance)(void *, void *))
{
if(Tree == NULL){
if((Tree=(Node *)malloc(sizeof(Node)))==NULL){
printf("Insufficient memory");
exit(1);
}
Tree->p1 = Object;
Tree->p2 = NULL;
Tree->left = Tree->right =NULL;
}
else if (Tree->p2 == NULL)
Tree->p2 = Object;
else if ((*Distance)(Tree->p1, Object) < (*Distance)(Tree->p2, Object))
insert(Tree->left, Object, Distance);
else insert(Tree->right, Object, Distance);
return(Tree);
}We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.
Try it yourself, you may find it is not as difficult as you think!
If you meet a specific problem, then please ask about that and we will do our best to help. But we aren't going to do it all for you!
We do not do your HomeWork.
HomeWork is not set to test your skills at begging other people to do your work, it is set to make you think and to help your teacher to check your understanding of the courses you have taken and also the problems you have at applying them.
Any failure of you will help your teacher spot your weaknesses and set remedial actions.
Any failure of you will help you to learn what works and what don't, it is called 'trial and error' learning.
So, give it a try, reread your lessons and start working. If you are stuck on a specific problem, show your code and explain this exact problem, we might help.
As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better.
When you just ask for the solution, it is like trying to learn to drive a car by having someone else training.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.
[Update]
Advice: Indent your code properly, indentation shows the structure of your code and makes it easier to read.
Node *insert(Node *Tree, void *Object, float (*Distance)(void *, void *)) { if(Tree == NULL){ if((Tree=(Node *)malloc(sizeof(Node)))==NULL){ printf("Insufficient memory"); exit(1); } Tree->p1 = Object; Tree->p2 = NULL; Tree->left = Tree->right =NULL; } else if (Tree->p2 == NULL) Tree->p2 = Object; else if ((*Distance)(Tree->p1, Object) < (*Distance)(Tree->p2, Object)) insert(Tree->left, Object, Distance); else insert(Tree->right, Object, Distance); return(Tree); }
Professional programmer's editors have this feature.
Notepad++ Home[^]
UltraEdit | The Original Text Editor[^]
Advice: do not pack more code than needed in 1 line, it saves nothing and is not faster, it is just more difficult to read.
Node *insert(Node *Tree, void *Object, float (*Distance)(void *, void *)) { if(Tree == NULL){ Tree=(Node *)malloc(sizeof(Node)); if((Tree == NULL){ printf("Insufficient memory"); exit(1); } Tree->p1 = Object; Tree->p2 = NULL; Tree->left = Tree->right =NULL; } else if (Tree->p2 == NULL) Tree->p2 = Object; else if ((*Distance)(Tree->p1, Object) < (*Distance)(Tree->p2, Object)) insert(Tree->left, Object, Distance); else insert(Tree->right, Object, Distance); return(Tree); }
Advice: do not learn programming with C language. With C language, you are responsible of every details like memory management, array boundaries, memory leak and so on. Handling those details makes learning more difficult.
Use instead real high level language like BASIC, Java or C#, they are marshaled and tell you when something go wrong like reading after the end of an array.
这篇关于如何使用二叉搜索树实现优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
