插入节点（二进制搜索树）C

Question

我试图在二叉搜索树中插入一个节点，并且出现了一些问题。

#include "stdafx.h" 
#include <string.h> 
#include <stdlib.h> 


typedef struct Node{ 
    char name[100]; 
    struct Node *pGauche; 
    struct Node *pDroit; 
}Node; 

void getName(char[]); 
void copy(Node **, Node *,char[]); 
void menu(Node **); 
void add(Node **); 
void search(char[],Node**, Node **,Node **); 
void print(Node **); 
void inOrder(Node *); 

void main(void) 
{ 
    Node *root = NULL; 
    menu(&root); 
    system("pause"); 
} 

void menu(Node **root) 
{ 
    for (int i=0;i<10;i++) 
    { 
     add(root); 
    } 
    print(root); 
} 

void add(Node **root) 
{ 
    char name[100]; 
    getName(name); 
    Node *p = NULL; 
    Node *savep = NULL; 
    search(name,root,&p,&savep); 
    copy(root,savep,name); 
} 

void search(char name[],Node **root, Node **p, Node **savep) 
{ 
    *p = *root; 

    while ((p == NULL) && (strcmp((*p)->name,name) != 0)) 
    { 
     *savep = *p; 

     if (strcmp(name,(*p)->name) < 0) 
      *p = (*p)->pGauche; 
     else 
      *p = (*p)->pDroit; 
    } 

} 

void getName(char name[]) 
{ 
    printf("What name do you want to add\n"); 
    scanf("%s",name); 
    fflush(stdin); 

} 

void copy(Node **root, Node *savep, char name[]) 
{ 
    Node *newp = (Node *) malloc(sizeof(Node*)); 
    newp->pDroit = NULL; 
    newp->pGauche = NULL; 

    strcpy(newp->name,name); 
    printf("%s",newp->name); 


    if (*root == NULL) 
     *root = newp; 
    else 
    { 
     if (strcmp(name,savep->name) < 0) 
      savep->pGauche = newp; 
     else 
      savep->pDroit = newp; 
    } 
    free(newp); 
} 

void print(Node ** root) 
{ 
    Node *p = *root; 
    inOrder(p); 
} 

void inOrder(Node *p) 
{ 
    if (p != NULL) 
    { 
     inOrder(p->pGauche); 
     printf("%s\n",p->name); 
     inOrder(p->pDroit); 
    } 
} 

我知道有一些很奇怪的功能和无用的功能，但是这只是一个“测试”一个稍微大一点的学校项目，所以它会得到及时有用的，现在我只是想获得二进制树工作！

所以基本上问题是，我得到一个“访问冲突读取位置”后，我的第二个名字键入做STRCMP时候......我猜，但我真的不知道：/

我真的很高兴，如果有人可以帮助我得到这个运行:)

Answer 1

一些让你开始的东西。我还没有看进去太深，所以你可能将不得不继续向下钻取更多的问题，而只是解决这些事情，让你开始：

在这段代码中search()：

while ((p == NULL) && (strcmp((*p)->name,name) != 0)) 

p参数永远不会为NULL。所以，while循环从不输入。这意味着savep不会设置为任何值，并且在您的add()函数中调用copy()时为NULL。然后，copy()函数将取消引用无效指针引用，这会导致您观察到的问题。

您实际上想测试以查看*p是否为而不是 NULL。这可以让你合法地解除引用。

while ((*p != NULL) && (strcmp((*p)->name,name) != 0)) 

其次，作为hmjd确定，你不为内部copy()您的节点分配足够的内存。

Node *newp = (Node *) malloc(sizeof(Node*)); 

我们会根据一个指针分配足够的存储空间，而不是整个节点。另外，在C语言编写代码时，您不应该使用malloc()的返回值（它会隐藏可能导致最坏情况下崩溃的错误）。

Node *newp = malloc(sizeof(Node)); 

第三，你需要保留你分配你的结点，而不是立即释放他们存储在copy()末插入之后：如果您调用free()像你这样

// I need this memory for my tree! 
    //free(newp); 

，然后你的tree将指向释放的内存，并访问它们会导致未定义的行为。

一件小事：你不应该做fflush(stdin)，因为fflush()只适用于输出流。

Answer 2

这是不正确的：

while ((p == NULL) && (strcmp((*p)->name,name) != 0)) 

，并会导致NULL指针被dereferenced，这是不确定的行为。更改为：

while (*p && strcmp((*p)->name,name) != 0) 

---

这是不正确的：

Node *newp = (Node *) malloc(sizeof(Node*)); 

，因为它是只为Node*分配不够，它需要被分配Node时。更改为：

Node *newp = malloc(sizeof(*newp)); 

而不是free()它与后面要求的功能相同。 free()荷兰国际集团的Node意味着列表中有dangling pointers和提领一个是不确定的行为，并访问冲突的可能原因。

---

注：

fflush(stdin); 

是不确定的行为。来自fflush()参考页面：

导致输出文件流与文件的实际内容同步。 如果给定的流是输入类型，那么函数的行为是未定义的。