从二叉树中看似无处设置的根节点

Question

当出于某种原因将一个节点插入此二叉树（不接受重复项）时，未设置根节点，甚至更奇怪的是根节点似乎被设置为正在输入的任何节点.这是我正在使用的两个文件。我在 tree.c 中用大写字母写了一条评论，以说明异常发生的地方。另一件要提到的事情是，具有包含 "integ" 变量的节点的树在循环中按预期工作。

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXRELATIONS 10
#define MAXTUPLES 100
#define MAXCOLUMNS 15
#define MAXLEN 15
struct tree_node
{
    //string or integer
    char *sOrI;
    char *string;
    int integ;
    char *column;
    struct tree_node *left_child;
    struct tree_node *right_child;
};
struct column
{
    char name[MAXLEN+1];
    char SI[1];
    int bytez;
};
struct db
{
    int columnNo;
    struct column columns[MAXCOLUMNS];
    struct tree_node dataNodes[MAXCOLUMNS];
};
int main(int argc, char *argv[])
{
    FILE *config;
    FILE *query;
    FILE *schema;
    FILE *dataFile;
    struct tree_node *current = NULL;
    int noOfRelations;
    int x,y;
    char relation[MAXLEN+1];
    struct db dbz[MAXLEN+1];
    int numOfColumns;
    if(argc==3){
        config = fopen(argv[1], "r+");
        query = fopen(argv[2], "r+");
        if(config==NULL){
            printf("Input file does not exist");
            return(1);
        }
        fscanf(config, "%d", &noOfRelations);
        for(x=0;fscanf(config, "%s", relation)!=EOF;x++){
            char dat[MAXLEN+1];
            char sch[MAXLEN+1];
            strcpy(dat, relation);
            strcpy(sch, relation);
            strcat(dat, ".dat");
            strcat(sch, ".sch");
            schema = fopen(sch, "r+");
            dataFile = fopen(dat, "rb");
            if(schema==NULL){
                printf("Couldn't find %s", sch);
                return(1);
            }
            if(dataFile==NULL){
                printf("Couldn't find %s", dat);
                return(1);
            }
            fscanf(schema, "%d", &numOfColumns);
            for(y=0;fscanf(schema, "%s%s%d", &(dbz[x].columns[y].name),&(dbz[x].columns[y].SI),&(dbz[x].columns[y].bytez))!=EOF;y++);
            if(strcmp(dbz[x].columns[0].SI,"S")==0){
                int t=0;
                while(1){
                    //printf("Hit!n");
                    char strHold[dbz[x].columns[0].bytez];
                    struct tree_node *start = NULL;
                    if(fread(&strHold, dbz[x].columns[0].bytez , 1, dataFile)==NULL){
                        break;
                    }
                    //printf("bytes %dn", dbz[x].columns[0].bytez);
                    printf("%sn", strHold);
                    current=NULL;
                    current = (struct tree_node *)malloc(sizeof(struct tree_node));
                    current->left_child = NULL;
                    current->right_child = NULL;
                    current->sOrI = dbz[x].columns[0].SI;
                    current->string = strHold;
                    current->column = dbz[x].columns[0].name;
                    start = &(dbz[x].dataNodes[0]);
                    insert(current, &(dbz[x].dataNodes[0]));
                    for(y=1;y<numOfColumns;y++){
                        if(strcmp(dbz[x].columns[y].SI,"S")==0){
                            current=NULL;
                            char strHold[dbz[x].columns[y].bytez];
                            //printf("bytes:%d y:%dn", dbz[x].columns[y].bytez,y);
                            fread(&strHold,dbz[x].columns[y].bytez , 1, dataFile);
                            printf("%sn", strHold);
                            current = (struct tree_node *)malloc(sizeof(struct tree_node));
                            current->left_child = NULL;
                            current->right_child = NULL;
                            current->sOrI = dbz[x].columns[y].SI;
                            current->string = strHold;
                            current->column = dbz[x].columns[y].name;
                            insert(current, &(dbz[x].dataNodes[y]));
                        }
                        else{
                            current=NULL;
                            int intHold;
                            //printf("bytes:%d y:%dn", dbz[x].columns[y].bytez,y);
                            fread(&intHold,dbz[x].columns[y].bytez , 1, dataFile);
                            printf("%dn", intHold);
                            current = (struct tree_node *)malloc(sizeof(struct tree_node));
                            current->left_child = NULL;
                            current->right_child = NULL;
                            current->sOrI = dbz[x].columns[y].SI;
                            current->integ = intHold;
                            current->column = dbz[x].columns[y].name;
                            insert(current, &(dbz[x].dataNodes[y]));
                        }
                    }
                }
            }
            else{
                int intHold;
                while(fread(&intHold,dbz[x].columns[0].bytez , 1, dataFile)!=NULL){
                    printf("%dn", intHold);
                    current = (struct tree_node *)malloc(sizeof(struct tree_node));
                    current->left_child = NULL;
                    current->right_child = NULL;
                    current->sOrI = dbz[x].columns[0].SI;
                    current->integ = intHold;
                    current->column = dbz[x].columns[0].name;
                    insert(current, &(dbz[x].dataNodes[0]));
                    for(y=1;y<numOfColumns;y++){
                        if(strcmp(dbz[x].columns[y].SI,"S")==0){
                            current=NULL;
                            char strHold[dbz[x].columns[y].bytez];
                            fread(&strHold,dbz[x].columns[y].bytez , 1, dataFile);
                            printf("%sn", strHold);
                            current = (struct tree_node *)malloc(sizeof(struct tree_node));
                            current->left_child = NULL;
                            current->right_child = NULL;
                            current->sOrI = dbz[x].columns[y].SI;
                            current->string = strHold;
                            current->column = dbz[x].columns[y].name;
                            insert(current, &(dbz[x].dataNodes[y]));
                        }
                        else{
                            int intHold;
                            fread(&intHold,dbz[x].columns[y].bytez , 1, dataFile);
                            printf("%dn", intHold);
                            current = (struct tree_node *)malloc(sizeof(struct tree_node));
                            current->left_child = NULL;
                            current->right_child = NULL;
                            current->sOrI = dbz[x].columns[y].SI;
                            current->integ = intHold;
                            current->column = dbz[x].columns[y].name;
                            insert(current, &(dbz[x].dataNodes[y]));
                        }
                    }
                    printf("nn");
                }
            }
            fclose(dataFile);
            fclose(schema);
            break;
        }
        fclose(config);
        return(0);
    }
    printf("Incorrect number of argumentsn");
    return(1);
}

tree.c

#include <stdio.h>
#include <string.h>
#define MAXLEN 15
struct tree_node
{
    //string or integer
    char *sOrI;
    char *string;
    int integ;
    char *column;
    struct tree_node *left_child;
    struct tree_node *right_child;
};
void insert(struct tree_node * node, struct tree_node ** start)
{
    printf("node type: %s node column: %sn", node->sOrI, node->column);
    if((*start)==NULL)
    {
        if(node->string){
            printf("node %s is setn",node->string);
        }
        *start = node;
        return;
    }
    if(strcmp(node->sOrI, "S")==0){
        printf("node string: %s, start string: %sn", node->string, (*start)->string);//WITHIN THE BIG LOOP THESE ARE IDENTICAL
        if(strcmp(node->string,(*start)->string)<0)
        {
            printf("Leftsn");
            insert(node, &(*start)->left_child);
        }
        else if(strcmp(node->string,(*start)->string)>0)
        {
            printf("Rightsn");
            insert(node, &(*start)->right_child);
        }
    }
    else{
        printf("node string: %d, start string: %dn", node->integ, (*start)->integ);
        if(node->integ<(*start)->integ)
        {
            printf("Leftin");
            insert(node, &(*start)->left_child);
        }
        else if(node->integ>(*start)->integ)
        {
            printf("Rightin");
            insert(node, &(*start)->right_child);
        }
    }
}

现在如果我尝试做类似

的事情

current=NULL;                                       
current = (struct tree_node *)malloc(sizeof(struct tree_node));                 
current->left_child = NULL;
current->right_child = NULL; 
current->sOrI = "S";
current->string = "a";
current->column = "column"; 
insert(current, &(dbz[0].dataNodes[0]));

current=NULL;                                       
current = (struct tree_node *)malloc(sizeof(struct tree_node));                 
current->left_child = NULL;
current->right_child = NULL; 
current->sOrI = "S";
current->string = "b";
current->column = "column"; 
insert(current, &(dbz[0].dataNodes[0]));

current=NULL;                                       
current = (struct tree_node *)malloc(sizeof(struct tree_node));                 
current->left_child = NULL;
current->right_child = NULL; 
current->sOrI = "S";
current->string = "c";
current->column = "column"; 
insert(current, &(dbz[0].dataNodes[0]));

我得到了预期的输出，所以我知道二叉树和一切都按预期工作，问题一定出在疯狂的大循环中。我已经隔离了我的代码中可能被破坏的每一部分，并且一切似乎都按预期工作。我不需要关于最佳实践的建议，除非它会影响该程序的结果，只是寻找一双新鲜的眼睛来指出导致手头问题的原因。感谢您的宝贵时间！

输出一个运行和一个数据file/schema文件

Smith,Robert node type: S node column: Name node Smith,Robert is set PSY node type: S node column: Major node PSY is set CSI node type: S node column: Minor node CSI is set 57 node type: I node column: Totcr 39 node type: I node column: Majcr Woods,Jane node type: S node column: Name node string: Woods,Jane, start string: Woods,Jane CSI node type: S node column: Major node string: CSI, start string: CSI BUS node type: S node column: Minor node string: BUS, start string: BUS 97 node type: I node column: Totcr node string: 97, start string: 57 Righti node type: I node column: Totcr 68 node type: I node column: Majcr node string: 68, start string: 39 Righti node type: I node column: Majcr Ramsey,Elaine node type: S node column: Name node string: Ramsey,Elaine, start string: Ramsey,Elaine BUS node type: S node column: Major node string: BUS, start string: BUS PSY node type: S node column: Minor node string: PSY, start string: PSY 107 node type: I node column: Totcr node string: 107, start string: 57 Righti node type: I node column: Totcr node string: 107, start string: 97 Righti node type: I node column: Totcr 88 node type: I node column: Majcr node string: 88, start string: 39 Righti node type: I node column: Majcr node string: 88, start string: 68 Righti node type: I node column: Majcr Wharton,Tom node type: S node column: Name node string: Wharton,Tom, start string: Wharton,Tom BUS node type: S node column: Major node string: BUS, start string: BUS PSY node type: S node column: Minor node string: PSY, start string: PSY 117 node type: I node column: Totcr node string: 117, start string: 57 Righti node type: I node column: Totcr node string: 117, start string: 97 Righti node type: I node column: Totcr node string: 117, start string: 107 Righti node type: I node column: Totcr 98 node type: I node column: Majcr node string: 98, start string: 39 Righti node type: I node column: Majcr node string: 98, start string: 68 Righti node type: I node column: Majcr node string: 98, start string: 88 Righti node type: I node column: Majcr Baker,Norma node type: S node column: Name node string: Baker,Norma, start string: Baker,Norma BIO node type: S node column: Major node string: BIO, start string: BIO CSI node type: S node column: Minor node string: CSI, start string: CSI 39 node type: I node column: Totcr node string: 39, start string: 57 Lefti node type: I node column: Totcr 25 node type: I node column: Majcr node string: 25, start string: 39 Lefti node type: I node column: Majcr

Answer 1

您的节点的密钥似乎正在本地声明。

char strHold[dbz[x].columns[y].bytez];

以上似乎是您的密钥。您可以在要插入的节点中存储指向该键的指针，但是当您离开声明 strHold 的框架时，您将丢失对它的引用。您的另一个示例有效，因为密钥字符串存储在静态内存中。我猜想最近的密钥似乎在根目录中，因为根密钥指针仍指向该帧中的 strHold，并且您不断地用新密钥覆盖它。声明动态内存来存储您的密钥，以便它们持久存在。

编辑：查看您的节点结构，字符串只是指向字符的指针。只要您希望节点存在，您就需要实际分配存储空间。

struct tree_node
{
    //string or integer
    char *sOrI;
    char *string;
    int integ;
    char *column;
    struct tree_node *left_child;
    struct tree_node *right_child;
};

...

node->string 指向 strHold，*start->string 也可能指向 strHold。

if(strcmp(node->string,(*start)->string)<0)

main.c:

这里是声明string hold的方法，它是一个局部变量，这意味着它的内存存在于栈中。框架退出后，您不再拥有该内存（但是，内存仍然可能设置为退出框架之前存储在那里的内容 - 但这并不意味着用着没问题。)

char strHold[dbz[x].columns[y].bytez];

然后您使用对 strHold 的引用加载新创建的节点的字符串字段，如上所述，它位于当前帧的本地内存中。

current->string = strHold;

这意味着当您退出框架时，您很可能不会长时间指向存储您刚刚尝试输入的字符串的内存位置。此外，由于您在此循环中输入的所有节点都有指向该变量的指针，因此它们似乎都具有您在 node->string 指针中复制到 strHold 中的最后一个值。

您提供的示例之所以有效，是因为您分配给 node->string 的字符串具有唯一的内存位置，并且在程序的整个生命周期中都保留在只读内存中。

这就是你需要做的，只是你需要动态地做。与使用 malloc 分配节点的方式相同，您需要使用 malloc 为字符串分配 space。

所以代替：

node->string = strHold;

您可能想要更多类似的东西：

node->string = malloc( sizeof(char) * strlen(strHold) )
//if malloc didn't fail...
strcpy(node->string, strHold)

现在的不同之处在于，您的节点的字符串字段指向专属于该节点的内存区域，并存储 strHold 内容中的内容。清理时不要忘记释放它！

从二叉树中看似无处设置的根节点

Root node being set from seemingly nowhere in binary tree

c

binary-tree

binary-search-tree