C二叉搜索树实现 – 插入
我正在尝试创建一个程序，该程序将单词列表作为输入，并将它们分类到二叉树中，以便允许它们被找到，例如像字典。 这是我到目前为止所做的，但是使用newEl -> el = input;得到了分段错误newEl -> el = input; 我知道这是因为当第一次创建树时，它试图指向一个NULL el，但我不确定改进我的代码的最佳方法是什么。 有人有主意吗？ 谢谢。
struct node *tra(struct node * start, Type input) { struct node * thisNode = start; if (thisNode == NULL) Type current = thisNode -> el; if (strcmp(input, current) > 0) return tra(thisNode -> right, input); else if (strcmp(input, current) left, input); else return thisNode; } } Ta insert(Type input, Ta ta) { if ((find(input, ta)) == FALSE) { newEl -> el = input; } return ta; } Boolean find(Type input, Ta ta) { if (tra(ta -> head, input) == NULL) return FALSE; }
这是指向等效指针的指针：
typedef char *Type; struct node { struct node *left , *right; Type payload; }; struct node **find_pp(struct node **pp, Type input) { struct node *thisNode ; while ( thisNode = *pp ) { int diff; diff = strcmp(input, thisNode->payload); if (!diff) break; pp = (diff <0) ? &thisNode->left : &thisNode->right; } return pp; } Boolean find(struct node *root, Type thing) { struct node **pp; pp = find_pp( &root, thing); return (*pp) ? True : False; } void insert (struct node **pp, Type thing) { struct node *newNode; pp = find_pp (pp, thing); if (*pp) return; /* already exists */ *pp = newNode = malloc (sizeof *newnode); newNode->payload = strdup(thing); newNode->left = NULL; newNode->right = NULL; return; }
几点说明：
- 将节点插入树中意味着：分配给之前为NULL的指针
- 空树也是一棵树：只是一个指针（到树的根），恰好是空的
- 在树中查找节点意味着：找到应该在哪里的地方（：=指针）（如果存在的话）
- 如果它不存在，则此指针正好是应该插入它以使其存在的位置
- 绘制图表（用纸和笔）将有所帮助。
既然您已经知道问题所在，那么您应该解决它。 分配节点并插入它。
Ta insert(Type input, Ta ta) { if ((find(input, ta)) == FALSE) { // call to tra will fail. this is the place to create a new node struct node *newEl = (struct node*) malloc(sizeof(struct node)); newEl -> el = input; newEl -> left = 0; newEl -> right = 0; // do the insertion .... } }
好像你想要创建一个新节点，但我没有看到你为新节点分配空间的任何地方，例如：
newEl = (struct node*)malloc(sizeof(struct node));
祝好运！