C二进制搜索树实现-插入 [英] C binary search tree implementation - insert

问题描述

我正在尝试创建一个程序，该程序将单词列表作为输入，并将它们分类到二叉树中，以便能够找到它们，例如像字典一样到目前为止，这是我所做的，但是由于newEl -> el = input;出现分段错误，我知道这是因为在首次创建树时，它试图指向NULL el，但是我不确定最好的是什么改进我的代码的方法将是.有人有想法么?谢谢.

I am trying to create a program which which takes a list of words as an input, and sorts them into a binary tree, in order to allow them to be found, e.g. like a dictionary. This is what I have done so far, but am getting a segmentation error with newEl -> el = input; I know this is because it is trying to point to a NULL el, when the tree is first created, but i'm not sure what the best way to improve my code would be. Anyone have any ideas? Thanks.

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) < 0)
        return tra(thisNode -> 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;
    }

推荐答案

这是指向等效指针的指针:

This is a pointer to pointer equivalent:

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;
}

---

一些注意事项:

---

a few notes:

• 将节点插入树中意味着:分配给以前为NULL的指针
• 空树也是一棵树:只是一个指针(指向树的根)恰巧为空
• 在树中找到一个节点意味着:找到应该存在的位置(:= pointer)(如果存在的话)
• 如果它不存在，则该指针正是应该插入该指针以使其存在的地方
• 用纸和铅笔绘制图表会有所帮助.

这篇关于C二进制搜索树实现-插入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！