c - 使用堆栈和入栈和出栈函数将 BST 转换为数组

Question

这个问题已经存在:

Converting a BST into an array using a stack

已关闭 8 年前。

我的程序的最后一部分有问题。我应该使用堆栈将 BST 更改为数组。当我尝试执行程序的这一部分时，出现段错误。我将发布一些我的代码，让大家了解我想要做什么，然后发布我应该使用此函数得到的输出。感谢您提前提供的帮助。

typedef struct TreeNode_ {
    char name[MAX_NAME_LEN];
    struct TreeNode_ *left;
    struct TreeNode_ *right;
}TreeNode;


typedef struct StackNode_ {
    TreeNode *t;
    struct StackNode_ *next;
}StackNode;

char** flatten_tree(TreeNode* node, int *len_strings);
void push_node(StackNode** top, TreeNode* t);
TreeNode* pop_node(StackNode** top);
int size(TreeNode *node);

int main (int argc, char *argv[]) {
    /*
     * Check command line parameters
     * */
    if (argc < 2) {
            printf("%s is missing parameters to run properly\n", argv[0]);
            return 1;
    }
    TreeNode* root = NULL;
    root = read_from_file(argv[1]);
    char buffer[MAX_NAME_LEN];
    char buffer2[MAX_NAME_LEN];
    display_tree(root,START_DEPTH);

    printf("Trimming the database from %s to %s\n\n", buffer, buffer2);
    root = trim_tree(root,buffer,buffer2);

    display_tree(root,START_DEPTH);

    int size = 0;
    char** strings = flatten_tree(root,&size);
    int i = 0;
    printf("\nFlattened databse is:\n");


    for (i = 0; i < size; ++i) {
            printf("%s\n", strings[i]);
            free(strings[i]);
    }
    free(strings);
}
}

int size(TreeNode* node) {

    if(node==NULL){
    return 0;
    }
    else{
            return(size(node->left) + 1 + size(node->right));
}}


char** flatten_tree(TreeNode* node, int *len_strings) {

    *len_strings = size(node);
    char *strings = malloc(sizeof(len_strings));
    TreeNode* current = node;
    StackNode* s = NULL;
    int done = 0;
    int i = 0;

    *strings = strings[i];


    while(!done){

            if(current != NULL){
                    push_node(&s, current);
                    current = current->left;
            }
            else{
                    if(s){
                            current = pop_node(&s);
                            current = current->right;
                            strings[i++];
                    }
                    else
                            done = 1;
}
}
}

void push_node(StackNode** top, TreeNode* t) {

    StackNode *newPtr = NULL;

    if(newPtr != NULL)
    {
            newPtr->t = t;
            newPtr->next = *top;
            *top = newPtr;
    }

}

TreeNode* pop_node(StackNode** top_ref) {

    StackNode *top = *top_ref;

    if(top){
            StackNode *temp = top->next;
            free(top_ref);
            *top_ref = top;
    }
}

该程序的输出应该如下所示:

 -
        bob
            -
    erik
            -
        james
            -
matt
            -
        nick
                -
            sachin
                -
sue
    -


Flattened database is:
bob
erik
james
matt
nick
sachin
sue

我的输出是这样的:

-
        bob
            -
    erik
            -
        james
            -
matt
            -
        nick
                -
            sachin
                -
sue
    -


Flattened database is:
segmentation fault

Answer 1

push_node 正在使用未初始化的局部变量 (newPtr)；如果它不是NULL，使用它可能会导致段错误。

更新:为什么不尝试将strings声明为char strings[max-#-of-nodes][MAX_NAME_LEN] 全局，并让代码填充和打印它工作吗？完成后，您可以返回并处理动态分配。