c - C 中的二叉树 - 多个数据

Question

我需要创建一个二叉搜索树来存储许多竞赛成员。

typedef struct Member{
char name[30];
char surname[30];
int id;
char email[30];
}member;

用于添加节点的键是名称(按字母顺序排列)。我知道我需要使用 strcmp 来定义放置新成员的位置，但我不知道如何实现树。我的结构应该是这样的吗:

typedef struct Member{
char name[30];
char surname[30];
int id;
char email[30];
struct mnode *left; 
struct mnode *right;
}member;

或者我应该保留旧的结构并为节点创建一个结构，然后将一个指针传递给成员作为数据类型，如下所示:

typedef struct mnode { 
    struct member *aMember; 
    struct tnode *left; 
    struct tnode *right;
} MTree;

如果是这样，正确吗？ :

MTree* addMember(MTree* nodeP, char name, char surname, int id, char email){
    if( nodeP == NULL )
    {
        nodeP = (struct tnode*) malloc( sizeof( struct mnode ) );
        (nodeP->mBook)->name = name;
        (nodeP->mBook)->surname = surname;
        (nodeP->mBook)->id = id;
        (nodeP->mBook)->email = email;

        /* initialize the children to null */
        (nodeP)->left = NULL;    
        (nodeP)->right = NULL;  
    }
    else if(name > (nodeP->aBook)->name)
    {
        addMember(&(nodeP)->left,name,surname,id,email);
    }
    else if(year < (nodeP->aBook)->year)
    {
        addMember(&(nodeP)->right,name,surname,id,email);
    }
    return nodeP;
}

Answer 1

如果编码正确，则可以使用增强结构或附加结构技术——两者都有效，并且有时都是必要的。

但是，限定符“如果编码正确”至关重要。您的第一个增强结构如下所示:

typedef struct Member
{
    char name[30];
    char surname[30];
    int id;
    char email[30];
    struct mnode *left; 
    struct mnode *right;
} member;

此时，还没有已知的struct mnode，因此您有指向与成员结构无关的两个结构的指针。您需要:

typedef struct Member
{
    char name[30];
    char surname[30];
    int id;
    char email[30];
    struct Member *left; 
    struct Member *right;
} member;

或者:

typedef struct Member member;

struct Member
{
    char name[30];
    char surname[30];
    int id;
    char email[30];
    member *left; 
    member *right;
};

两者都有效；没有强有力的理由证明其中一种优于另一种 - 但当您需要时，第二种适合“不透明数据类型”。

同样，您有:

typedef struct mnode { 
    struct member *aMember; 
    struct tnode *left; 
    struct tnode *right;
} MTree;

尚未显示类型struct member(有一个struct Member - 请记住，C 区分大小写)，也没有struct tnode 。这个结构就目前而言是无用的，但如果更正为:

typedef struct mnode
{ 
    struct Member *aMember; 
    struct mnode  *left; 
    struct mnode  *right;
} MTree;

然后它可以用于原始struct Member结构的树(其中没有指针的结构)。您也可以不使用指向成员的指针:

typedef struct mnode
{ 
    struct Member aMember; 
    struct mnode *left; 
    struct mnode *right;
} MTree;

这样做的好处是可以少分配和释放一 block 内存；它简化了簿记。

您必须正确控制结构标记和 typedef 名称。没有理由一直发明新名字。您可以使用:

typedef struct Tag Tag;

或者:

typedef struct Tag { …structure definition… } Tag;

然后struct Tag和Tag都引用相同的类型。结构(以及 union 和枚举)标记的命名空间与普通标识符命名空间(即 typedef 名称的命名空间)是分开的。 C++ 自动提供此功能；您必须在 C 中手动执行此操作，如图所示。 Linux 内核编码指南不允许使用 typedef 作为结构类型 - 您必须始终编写 struct WhatEver，而不是创建类似 typedef struct WhatEver WhatEver; 或 typedef struct WhatEver 的名称这是什么；。您不必在自己的代码中遵循 Linux 指南——我不需要——但它们并非完全没有优点。