c - 在一个函数中删除所有二叉搜索树

Question

我有一个用于 AVL Tree 的 C 程序。我已经编写了创建节点、创建树、将元素插入树等的所有必要函数。一切正常，但我无法设法使 tree_free 函数正常工作。我想要这个函数移除所有的树。这是我的结构；

typedef struct NODE_s *NODE;
typedef struct NODE_s
{  
    NODE right;
    NODE left;
    unsigned long long data;
    int height;
} NODE_t[1];

typedef struct TREE_s *TREE;
typedef struct TREE_s
{
    NODE root;
} TREE_t[1];

这是我在树中插入数字的方法；

void avl_insert(TREE tree, unsigned long long data){


    tree->root = avl_insert_recursive(tree->root, data);

}

这里是 avl_insert_recursive 函数；

NODE avl_insert_recursive(NODE node, unsigned long long data){

    int balance = 0;


    if( node == NULL){

        return(node_init(data));
    }

    if( data < node->data ){


        node->left = avl_insert_recursive(node->left, data);



    }else if( data > node->data){


        node->right = avl_insert_recursive(node->right, data);



    }else{

        return node;
    }

    node->height = 1 + max(local_height(node->left), local_height(node->right));

    return node;
}

如您所见，首先将一个数字插入到一个节点中。然后将节点插入到树中。这就是为什么我有 2 个函数来删除这三个函数。第一个功能是简单地删除节点；

void node_free(NODE node){

    if(node != NULL){

    node_free(node->left); 
    node_free(node->right); 
    free(node);

    }
}

我从主 tree_free 函数调用这个函数；

void tree_free(TREE tree){

    node_free(tree->root);

}

这就是您了解树的工作原理所需的所有代码。我在 tree_free' 之后放置了一个 printf 语句，但它从未执行过。因此，程序在使用 tree_free` 函数时崩溃了。感谢您的帮助。

编辑:对于那些想看 node_init 函数的人，给你；

NODE node_init(unsigned long long data)
{

    NODE newNode = (struct NODE_s*)malloc(sizeof(struct NODE_s));
    newNode->data = data;
    newNode->right = NULL;
    newNode->left = NULL;
    newNode->height = 1; 
    return newNode;
}

我有一个测试函数来测试我的 AVL 树；

void test(char *fname, int n)
{

// Create tree and initalized it.
TREE tree;
tree = tree_init();


//NODE node = node_init(NULL);

time_t start, end;
int avl_insertion_time = 0;

FILE *fp;
int i = 0;
unsigned long long number;

unsigned long long *inorder = (unsigned long long *)malloc(sizeof(unsigned long long)*n);
fp = fopen(fname, "r+");
time(&start);
for(i = 0; i<n; i++){
    fscanf(fp, "%llu\n", &number);
    //node = avl_insert_recursive(node,number);
    avl_insert(tree, number);
}
time(&end);
fclose(fp);
avl_insertion_time = end - start

time(&start);
inorder_traversal(tree->root, inorder);
time(&end);
printf("inorder_traversal function's time spent is %ld second for %d number of elements.(AVL insertion was %ld secs)\n", (end - start), n, avl_insertion_time);
tree_free(tree);
free(inorder);
}

这是我的主要功能；

int main()
{


test("10000.txt", 10000);
test("100000.txt", 100000);
test("1000000.txt", 1000000);
test("10000000.txt", 10000000);


return 0;
}

这是遍历我的树的函数；

void inorder_traversal(NODE node, unsigned long long *inorder){


if (node == NULL){
    return; 
}


inorder_traversal(node->left, inorder); 



inorder[index] = node->data;
index++;



inorder_traversal(node->right, inorder); 


}

Answer 1

假设 index 是全局变量。

问题是您没有重置全局 index。

inorder[index] = node->data;
index++;

在第一次调用 test 后，您的索引将为 10000。

因此你访问

inorder[10000+100000] in the second `test` call.

---

因此在每次调用 test 后重置索引。

int main()
{

index = 0;
test("10000.txt", 10000);
index = 0;
test("100000.txt", 100000);
index = 0;
test("1000000.txt", 1000000);
index = 0;
test("10000000.txt", 10000000);


return 0;
}