Обход бинарного дерева в C - PullRequest
Новая
       30

Обход бинарного дерева в C

4 голосов
/ 26 декабря 2009

Я пытаюсь пройти через двоичное дерево в C. Мое дерево содержит узел AST (узел абстрактного синтаксического дерева для компилятора). ASTnode резервирует тип узла, который определяет данный тип узла (т. Е. INT OP или CHAR и TYPE, которые не нужны для других типов), остальные члены - это левый и правый указатели, и, наконец, мы храним.

Вот код для обхода: 

    void traverse(struct ASTNode *root)
    {
        if(root->nodeType == OP){
            printf("OP \n");
            if(root->left != NULL){
              printf("left - ");
              traverse(root->left);
            }
            if(root->right != NULL){
              printf("right - ");
              traverse(root->right);
            }
            return;
        }
        else{
            if(root != NULL && root->nodeType == INT)
            {
              printf("INT - ");
              printf("INT: %d\n",root->value);
            }
            if(root != NULL && root->nodeType == CHAR)
            {
              printf("CHAR - ");
              printf("CHAR: %c\n",root->chValue);
            }
            return;
        }
    }

Также мы не можем назначать левые или правые значения узлам CONSTANT, потому что в AST постоянные значения не содержат никаких дополнительных значений.

Обновлен:

Проблема в моем основном вызове: 

    int main()
    {
        struct ASTNode *node1 = makeCharNode('a');
        struct ASTNode *node2 = makeCharNode('b');
        struct ASTNode *node10 = makeCharNode('c');
        struct ASTNode *node3 = makeINTNode(19);

        struct decl *d = (struct decl*) malloc(sizeof(struct decl*));
        struct decl *d2 = (struct decl*) malloc(sizeof(struct decl*));

        struct ASTNode *node4 = makeNode(3,d,node3,node2);
        struct ASTNode *node5 = makeNode(3,d2,node4,node1); !!
        traverse(node4);
    }

Если мы удаляем node5 (который отмечен символом !!), код работает очень хорошо, иначе он дает ошибку сегментации.

Функции, которые работают с makenode: 

    struct ASTNode *makeNode(int opType,struct decl *resultType,struct ASTNode *left,struct ASTNode *right)
    {
        struct ASTNode *node= (struct ASTNode *) malloc(sizeof(struct ASTNode *));
        node->nodeType = opType;
        node->resultType = resultType;
        node->left = left;
        node->right = right;
        return node;
    }

    struct ASTNode *makeINTNode(int value)
    {
        struct ASTNode *intnode= (struct ASTNode *) malloc(sizeof(struct ASTNode *));
        intnode->nodeType = INT;
        intnode->value = value;
        return intnode;
    }

    struct ASTNode *makeCharNode(char chValue)
    {
        struct ASTNode *charNode = (struct ASTNode *) malloc(sizeof(struct ASTNode *));
        charNode->nodeType = CHAR;
        charNode->chValue = chValue;
        return charNode;
    }

Ответы [ 6 ]

11 голосов
/ 26 декабря 2009

Ваши mallocs неправильны 

 struct decl *d = (struct decl*) malloc(sizeof(struct decl*));
 struct decl *d2 = (struct decl*) malloc(sizeof(struct decl*));

должно быть 

 struct decl *d = (struct decl*) malloc(sizeof(struct decl));
 struct decl *d2 = (struct decl*) malloc(sizeof(struct decl));

(или используйте sizeof * d вместо sizeof (struct decl)). В C вам не нужно приводить возвращаемое значение malloc, кстати.

Кроме того, убедитесь, что вы устанавливаете элементы в NULL или другое значение по умолчанию, прежде чем получить к ним доступ. malloc не установит для них значение 0 / NULL.

1 голос
/ 26 декабря 2009

Вы показываете код, размещающий указатели 'struct decl'; Вы не показываете код, инициализирующий их. Непонятно, почему makeNode () инициализирует свой второй аргумент или как он это сделает. Также не ясно, что означает 3. Также не ясно, как «struct decl» интегрируется в узел AST.

Вы можете упростить traverse (), обратившись к исключительным случаям раньше: 

void traverse(struct ASTNode *root)
{
  if (root == NULL)  // Or: assert(root != NULL);
    return;
  if (root->nodeType == OP)
  {
    printf("OP \n");
    if (root->left != NULL)
    {
      printf("left - ");
      traverse(root->left);
    }
    if (root->right != NULL)
    {
      printf("right - ");
      traverse(root->right);
    }
  }
  else if (root->nodeType == INT)
  {
    printf("INT - ");
    printf("INT: %d\n", root->value);    
  }
  else if (root->nodeType == CHAR)
  {   
    printf("CHAR - ");
    printf("CHAR: %c\n", root->chValue);
  }
  else
    assert("Unrecognized nodeType" == 0);
}

Это также касается невозможного случая - нераспознанного типа узла. Он также не падает и не горит, если передается нулевой указатель.

Однако это еще не объясняет, почему ваш код падает и не падает в зависимости от дополнительного узла AST ... Я не уверен, что у нас достаточно кода, чтобы быть уверенным в том, почему это происходит. Вы пытались обойти все узлы (узел1, узел2, узел3, узел10)? Это должно быть хорошо, если предположить, что функции makeCharNode () и makeINTNode () работают нормально, но такие элементарные проверки могут спасти ваш бекон. Может быть полезно посмотреть, что делает функция makeNode (); обеспечивает ли он правильную инициализацию всех частей узла.

1 голос
/ 26 декабря 2009

Ваш код будет зависать на первом NULL-узле, переданном в traverse ().

Вы проверяете root != NULL в своем блоке else, но к тому времени вы уже разыменовали его. Если вы попытаетесь разыменовать нулевой указатель, вы получите ошибку по умолчанию.

Попробуйте добавить 

if (!root) return;

как ваша первая строка.

1 голос
/ 26 декабря 2009

Функция makeNode должна инициализировать все члены структуры. Возможно, это не установка одного из левого / правого указателей в NULL? Вызов malloc () не обнуляет память.

Ack - я слепой. Ответ nos правильный. Неправильный вызов malloc. Я только добавил к шуму.

1 голос
/ 26 декабря 2009

Вы не проверяете, имеет ли root значение NULL в вашем первом блоке if. Я думаю, что самое простое, что нужно сделать, это завернуть 

if(root != NULL)

вокруг всего этого (кроме окончательного возврата) и избавьтесь от отдельных проверок 'root! = NULL' при печати узлов INT и CHAR.

Делись и наслаждайся.

РЕДАКТИРОВАТЬ: вот что я имею в виду: 

void traverse(struct ASTNode *root) 
  { 
  if(root != NULL)
    {
    switch(root->nodeType)
      {
      case OP:
        printf("OP \n"); 

        if(root->left != NULL)
          { 
          printf("left - "); 
          traverse(root->left); 
          } 

        if(root->right != NULL)
          { 
          printf("right - "); 
          traverse(root->right); 
          } 
        break;

      case INT:
        printf("INT - "); 
        printf("INT: %d\n",root->value);
        break;

      case CHAR:
        printf("CHAR - "); 
        printf("CHAR: %c\n",root->chValue); 
      }
    } 
  }

Также изменено использование переключателя вместо группы if.

Прошу прощения за любые синтаксические ошибки: это не в моей голове, без компилятора.

1 голос
/ 26 декабря 2009

Я вижу только то, что, возможно, вы захотите проверить root->value и др., Прежде чем переходить к printf.

Кроме того, хотя это не должно вызывать ошибку, вы можете изменить

if(root != NULL && root->nodeType == CHAR)

до

else if(root != NULL && root->nodeType == CHAR)

Редактировать: подождите, вот что - когда вы передаете root->left для обхода, это само значение или указатель? Функция ожидает указатель.

...