0

以下代码是将二叉搜索树转换为双向链表的代码。它在 GDB 中运行良好，但在运行时崩溃。当我只有 2 个输入到二叉搜索树时，当有 2 个以上的输入时它会崩溃，它工作正常。代码可能有什么问题。双向链表不是循环链表。所以第一个节点的前一个是NULL，最后一个节点的下一个是NULL。

#include<stdio.h>
struct node{
int data;
struct node* large;
struct node* small;
};

typedef struct node* Node;

void add_to_tree(Node *root, int num){
Node current = *root;
Node temp_store;
Node new_node = malloc(sizeof(Node));
new_node->data = num;
new_node->large = NULL;
new_node->small = NULL;

if(current == NULL){
    current = new_node;
    *root = current;
}
else
{
    while(current != NULL){
        temp_store = current;
        if(num > current->data)
            current = current->large;
        else
            current = current->small;
    }

    if(num <= temp_store->data)
        temp_store->small = new_node;
    else
        temp_store->large = new_node;
}
}
void display_list(Node head){
Node current = head;
if(head == NULL){
    printf("\nThe list is empty");
}
else{
    printf("\nThe list is:\n");
    while(current !=NULL){
        printf("%d\t", current->data);
        current = current->large;
    }
}
}

void join(Node a, Node b){
a->large = b;
b->small = a;
}

Node append(Node a, Node b){
Node aLast;
Node current;

if(a == NULL) return (b);
if(b == NULL) return (a);

current = a;
while(current->large != NULL)
    current = current->large;
aLast = current;

join(aLast, b);

return (a);
}

Node bst_to_dll(Node root){
Node aList;
Node bList;
if(root == NULL)
    return NULL;

aList = bst_to_dll(root->small);
bList = bst_to_dll(root->large);

root->small = NULL;
root->large = NULL;

aList = append(aList, root);
aList = append(aList, bList);

return aList;
}

int main(){
Node bin_tree = NULL;
Node d_list;


add_to_tree(&bin_tree, 1);
add_to_tree(&bin_tree, 2);
add_to_tree(&bin_tree, 3);

d_list = bst_to_dll(bin_tree);

display_list(d_list);

return 0;

}
4

1 回答 1

1

您的程序在编译时会生成警告：

gcc -g t.c
t.c: In function ‘add_to_tree’:
t.c:13: warning: incompatible implicit declaration of built-in function ‘malloc’

在 Valgrind 下也会产生 32 个错误，其中第一个是：

==29346== Invalid write of size 8
==29346==    at 0x4005E9: add_to_tree (/tmp/t.c:15)
==29346==    by 0x400820: main (/tmp/t.c:97)
==29346==  Address 0x51b6078 is 0 bytes after a block of size 8 alloc'd
==29346==    at 0x4C2A4D6: malloc (coregrind/m_replacemalloc/vg_replace_malloc.c:263)
==29346==    by 0x4005D7: add_to_tree (/tmp/t.c:13)
==29346==    by 0x400820: main (/tmp/t.c:97)

这应该足以让您找出您的错误。

于 2012-09-10T00:27:55.207 回答