在树中插入(键,值)时,节点不形成树结构
While inserting (key, value) in a tree, the node doesnt form a tree structure
我正在尝试创建 avl 树,它从文件中一对一地读取(键,值)并根据键的数据形成树。
首先,将元组读入键和值并将它们传递给创建函数,我在其中初始化了具有结构的树
typedef struct AVLTree{
int size; // count of items in avl tree
AVLTreeNode *root; // root
} AVLTree;
AVLTree *newAVLTree()
{
AVLTree *T;
T = malloc(sizeof (AVLTree));
assert (T != NULL);
T->size = 0;
T->root = NULL;
return T;
}
然后我将最初为 NULL 的树的根的值分配给结构如下所示的 AVLTreeNode:
typedef struct AVLTreeNode {
int key; //key of this item
int value; //value (int) of this item
int height; //height of the subtree rooted at this node
struct AVLTreeNode *parent; //pointer to parent
struct AVLTreeNode *left; //pointer to left child
struct AVLTreeNode *right; //pointer to right child
} AVLTreeNode;
//data type for AVL trees
typedef struct AVLTree{
int size; // count of items in avl tree
AVLTreeNode *root; // root
} AVLTree;
// create a new AVLTreeNode
AVLTreeNode *newAVLTreeNode(int k, int v )
{
AVLTreeNode *new;
new = malloc(sizeof(AVLTreeNode));
assert(new != NULL);
new->key = k;
new->value = v;
new->height = 0; // height of this new node is set to 0
new->left = NULL; // this node has no child
new->right = NULL;
new->parent = NULL; // no parent
return new;
}
现在,对于我从文件中读取的每个键值对,我将其传递给创建函数并检查以下 3 个条件:
void insert_in_tree(int key, int value, struct AVLTreeNode **node){
// if the tree is empty
if(*node == NULL){
node = newNode;
}
// insert on left if the data in the key is less than the data in the node.
else if (key<(*node)->key){
insert_in_tree(key,value,&(*node)->left);
}
// insert on right if the data in the key is greater than the data in the node.
else if(key>(*node)->key)
{
insert_in_tree(key,value,&(*node)->right);
}
}
PS:不要担心 newAVLTreeNode 中的 'value' 部分,因为我稍后会使用它处理重复项。
通过上面的代码,我预计树会形成,但那没有发生。经过进一步调查和调试,我发现
虽然 insert_in_tree 传递了新的键和值,但节点也是新的,而不是已经创建的节点。
AVLTree *CreateAVLTree(const char *filename)
{
//Inititalising a new tree
AVLTree *tree = newAVLTree();
// initialising the head to root of tree i.e. null
AVLTreeNode *head = tree->root;
int key, value;
FILE* file = fopen(filename, "r"); // open a file
if(file == NULL) {
return 1; // error checking
}
while (fscanf (file, " (%d,%d)", &key, &value) == 2) // check for number of conversions
// space added here ^
{
insert_in_tree(key, value, &head);
//printf("%d,%d\n", key, value);
}
fclose(file);
return tree;
}
int main() //sample main for testing
{
AVLTree *tree1;
tree1=CreateAVLTree("File1.txt");
//PrintAVLTree(tree1);
return 0;
}
我尽量讲得详细些,但如果您不明白,请随时问我问题。乐于回答。
请帮忙。
在函数 insert_in_tree
中,您正试图修改按值传递的参数。您需要像这样通过引用传递:
void insert_in_tree(int key, int value, struct AVLTreeNode **node){
// if the tree is empty
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
// insert on left if the data in the key is less than the data in the node.
else if (key<(*node)->key){
insert_in_tree(key,value,&(*node)->left);
}
// insert on right if the data in the key is greater than the data in the node.
else if(key>(*node)->key)
{
insert_in_tree(key,value,&(*node)->right);
}
}
此外,如果 node != NULL
此函数会导致内存泄漏,因为它分配新节点但不会在任何地方保存指向它的指针。
顺便说一句,您要创建的不是 AVL 树,而是 binary search tree。
Mikhail 快到了,但没有发现内存泄漏。我在下面更正:
void insert_in_tree(int key, int value, struct AVLTreeNode **node){
// if the tree is empty
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
// insert on left if the data in the key is less than the data in the node.
else if (key<(*node)->key){
insert_in_tree(key,value,&(*node)->left);
}
// insert on right if the data in the key is greater than the data in the node.
else if(key>(*node)->key)
{
insert_in_tree(key,value,&(*node)->right);
}
}
修复总结:
你需要传递一个指向放置新分配节点的地方的指针,因为C是按值传递的。那叫一个"double pointer".
您在每次递归调用时都分配了内存,但只有在知道插入位置后才需要这样做。
更多已在答案中描述的更正:
void insert_in_tree(int key, int value, struct AVLTreeNode **node){
// if the tree is empty
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
// insert on left if the data in the key is less than the data in the node.
else if (key<(*node)->key){
insert_in_tree(key,value,&(*node)->left);
}
// insert on right if the data in the key is greater than the data in the node.
else if(key>(*node)->key)
{
insert_in_tree(key,value,&(*node)->right);
}
}
在 CreateAVLTree 中,您(现在)将 node 的树设置为 head 但是您错过更新 tree->root
,一个简单的方法是不使用临时变量 head 而是直接使用 tree->root
:
AVLTree *CreateAVLTree(const char *filename)
{
//Inititalising a new tree
AVLTree *tree = newAVLTree();
// initialising the head to root of tree i.e. null
int key, value;
FILE* file = fopen(filename, "r"); // open a file
if(file == NULL) {
return NULL; // error checking
}
while (fscanf (file, " (%d,%d)", &key, &value) == 2) // check for number of conversions
// space added here ^
{
insert_in_tree(key, value, &tree->root);
//printf("%d,%d\n", key, value);
}
fclose(file);
return tree;
}
我也把无效的return 1;
换成了return NULL;
,文件打不开
注意字段 size 没有设置,也许它必须包含节点列表的大小,在这种情况下只需在 [= 的调用附近添加 tree->size += 1;
19=]
如果我添加定义来打印结果:
void PrintNodes(struct AVLTreeNode * l)
{
if (l == NULL)
printf("()");
else {
putchar('(');
PrintNodes(l->left);
printf(" %d %d %d ", l->key, l->value, l->height);
PrintNodes(l->right);
putchar(')');
}
}
void PrintAVLTree(AVLTree * tree)
{
printf("%d elements : ", tree->size);
PrintNodes(tree->root);
putchar('\n');
}
并在main中将PrintAVLTree(tree1);
注释掉,编译执行:
pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra -Wall t.c
pi@raspberrypi:/tmp $ cat File1.txt
(2, 50) (4, 30) (9, 30) (10, 400) (-5, -40)
(7, 20) (19, 200) (20, 50) (-18, -200) (-2, 29)
(2, 67) (4, 35) (9, 45) (-18, 100)
pi@raspberrypi:/tmp $ ./a.out
14 elements : (((() -18 -200 0 ()) -5 -40 0 (() -2 29 0 ())) 2 50 0 (() 4 30 0 ((() 7 20 0 ()) 9 30 0 (() 10 400 0 (() 19 200 0 (() 20 50 0 ()))))))
我正在尝试创建 avl 树,它从文件中一对一地读取(键,值)并根据键的数据形成树。
首先,将元组读入键和值并将它们传递给创建函数,我在其中初始化了具有结构的树
typedef struct AVLTree{
int size; // count of items in avl tree
AVLTreeNode *root; // root
} AVLTree;
AVLTree *newAVLTree()
{
AVLTree *T;
T = malloc(sizeof (AVLTree));
assert (T != NULL);
T->size = 0;
T->root = NULL;
return T;
}
然后我将最初为 NULL 的树的根的值分配给结构如下所示的 AVLTreeNode:
typedef struct AVLTreeNode {
int key; //key of this item
int value; //value (int) of this item
int height; //height of the subtree rooted at this node
struct AVLTreeNode *parent; //pointer to parent
struct AVLTreeNode *left; //pointer to left child
struct AVLTreeNode *right; //pointer to right child
} AVLTreeNode;
//data type for AVL trees
typedef struct AVLTree{
int size; // count of items in avl tree
AVLTreeNode *root; // root
} AVLTree;
// create a new AVLTreeNode
AVLTreeNode *newAVLTreeNode(int k, int v )
{
AVLTreeNode *new;
new = malloc(sizeof(AVLTreeNode));
assert(new != NULL);
new->key = k;
new->value = v;
new->height = 0; // height of this new node is set to 0
new->left = NULL; // this node has no child
new->right = NULL;
new->parent = NULL; // no parent
return new;
}
现在,对于我从文件中读取的每个键值对,我将其传递给创建函数并检查以下 3 个条件:
void insert_in_tree(int key, int value, struct AVLTreeNode **node){
// if the tree is empty
if(*node == NULL){
node = newNode;
}
// insert on left if the data in the key is less than the data in the node.
else if (key<(*node)->key){
insert_in_tree(key,value,&(*node)->left);
}
// insert on right if the data in the key is greater than the data in the node.
else if(key>(*node)->key)
{
insert_in_tree(key,value,&(*node)->right);
}
}
PS:不要担心 newAVLTreeNode 中的 'value' 部分,因为我稍后会使用它处理重复项。
通过上面的代码,我预计树会形成,但那没有发生。经过进一步调查和调试,我发现 虽然 insert_in_tree 传递了新的键和值,但节点也是新的,而不是已经创建的节点。
AVLTree *CreateAVLTree(const char *filename)
{
//Inititalising a new tree
AVLTree *tree = newAVLTree();
// initialising the head to root of tree i.e. null
AVLTreeNode *head = tree->root;
int key, value;
FILE* file = fopen(filename, "r"); // open a file
if(file == NULL) {
return 1; // error checking
}
while (fscanf (file, " (%d,%d)", &key, &value) == 2) // check for number of conversions
// space added here ^
{
insert_in_tree(key, value, &head);
//printf("%d,%d\n", key, value);
}
fclose(file);
return tree;
}
int main() //sample main for testing
{
AVLTree *tree1;
tree1=CreateAVLTree("File1.txt");
//PrintAVLTree(tree1);
return 0;
}
我尽量讲得详细些,但如果您不明白,请随时问我问题。乐于回答。
请帮忙。
在函数 insert_in_tree
中,您正试图修改按值传递的参数。您需要像这样通过引用传递:
void insert_in_tree(int key, int value, struct AVLTreeNode **node){
// if the tree is empty
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
// insert on left if the data in the key is less than the data in the node.
else if (key<(*node)->key){
insert_in_tree(key,value,&(*node)->left);
}
// insert on right if the data in the key is greater than the data in the node.
else if(key>(*node)->key)
{
insert_in_tree(key,value,&(*node)->right);
}
}
此外,如果 node != NULL
此函数会导致内存泄漏,因为它分配新节点但不会在任何地方保存指向它的指针。
顺便说一句,您要创建的不是 AVL 树,而是 binary search tree。
Mikhail 快到了,但没有发现内存泄漏。我在下面更正:
void insert_in_tree(int key, int value, struct AVLTreeNode **node){
// if the tree is empty
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
// insert on left if the data in the key is less than the data in the node.
else if (key<(*node)->key){
insert_in_tree(key,value,&(*node)->left);
}
// insert on right if the data in the key is greater than the data in the node.
else if(key>(*node)->key)
{
insert_in_tree(key,value,&(*node)->right);
}
}
修复总结:
你需要传递一个指向放置新分配节点的地方的指针,因为C是按值传递的。那叫一个"double pointer".
您在每次递归调用时都分配了内存,但只有在知道插入位置后才需要这样做。
更多已在答案中描述的更正:
void insert_in_tree(int key, int value, struct AVLTreeNode **node){
// if the tree is empty
if(*node == NULL){
*node = newAVLTreeNode(key, value);
}
// insert on left if the data in the key is less than the data in the node.
else if (key<(*node)->key){
insert_in_tree(key,value,&(*node)->left);
}
// insert on right if the data in the key is greater than the data in the node.
else if(key>(*node)->key)
{
insert_in_tree(key,value,&(*node)->right);
}
}
在 CreateAVLTree 中,您(现在)将 node 的树设置为 head 但是您错过更新 tree->root
,一个简单的方法是不使用临时变量 head 而是直接使用 tree->root
:
AVLTree *CreateAVLTree(const char *filename)
{
//Inititalising a new tree
AVLTree *tree = newAVLTree();
// initialising the head to root of tree i.e. null
int key, value;
FILE* file = fopen(filename, "r"); // open a file
if(file == NULL) {
return NULL; // error checking
}
while (fscanf (file, " (%d,%d)", &key, &value) == 2) // check for number of conversions
// space added here ^
{
insert_in_tree(key, value, &tree->root);
//printf("%d,%d\n", key, value);
}
fclose(file);
return tree;
}
我也把无效的return 1;
换成了return NULL;
,文件打不开
注意字段 size 没有设置,也许它必须包含节点列表的大小,在这种情况下只需在 [= 的调用附近添加 tree->size += 1;
19=]
如果我添加定义来打印结果:
void PrintNodes(struct AVLTreeNode * l)
{
if (l == NULL)
printf("()");
else {
putchar('(');
PrintNodes(l->left);
printf(" %d %d %d ", l->key, l->value, l->height);
PrintNodes(l->right);
putchar(')');
}
}
void PrintAVLTree(AVLTree * tree)
{
printf("%d elements : ", tree->size);
PrintNodes(tree->root);
putchar('\n');
}
并在main中将PrintAVLTree(tree1);
注释掉,编译执行:
pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra -Wall t.c
pi@raspberrypi:/tmp $ cat File1.txt
(2, 50) (4, 30) (9, 30) (10, 400) (-5, -40)
(7, 20) (19, 200) (20, 50) (-18, -200) (-2, 29)
(2, 67) (4, 35) (9, 45) (-18, 100)
pi@raspberrypi:/tmp $ ./a.out
14 elements : (((() -18 -200 0 ()) -5 -40 0 (() -2 29 0 ())) 2 50 0 (() 4 30 0 ((() 7 20 0 ()) 9 30 0 (() 10 400 0 (() 19 200 0 (() 20 50 0 ()))))))