Я пытаюсь создать дерево 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: Не беспокойтесь о части 'value' в новом AVLTreeNode, так как позже я буду обрабатывать дубликаты, используя это.
С помощью приведенного выше кода я ожидал, что дерево будет сформировано, но этого не произошло.После дальнейшего изучения и отладки я обнаружил, что хотя 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;
}
Я пытался быть настолько сложным, каквозможно, но не стесняйтесь задавать мне вопросы, если вы не понимаете.Рад ответить.Пожалуйста, помогите.