Прохождение двоичного дерева в C

Question

Я пытаюсь пересечь двоичное дерево в C. Мое дерево содержит узел AST (абстрактный узел синтаксического дерева для компилятора). ASTnode резервирует nodetype, который задает тип данного узла (например, 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; 
     } 
    } 

Кроме того, мы не можем назначить левое или правое значение ПОСТОЯННЫХ узлов, так как в 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; 
    } 

Answer 1

Ваши 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 (структура Децл)). В C вам не нужно указывать возвращаемое значение malloc, кстати.

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

Answer 2

Все, что я вижу в том, что, может быть, вы хотите, чтобы проверить root->value и др перед переходом к Printf.

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

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

к

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

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

Answer 3

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

if(root != NULL) 

вокруг всего (за исключением окончательного возвращения), и избавиться от отдельного «корня! = NULL» проверяет при печати INT и CHAR узлов.

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

EDIT: вот что я имею в виду:

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

изменилось также использовать переключатель вместо кучки если х.

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

Answer 4

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

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

Answer 5

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

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

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

if (!root) return; 

в качестве первой линии.

Answer 6

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

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

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

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

Однако это еще не объясняет, почему ваш код аварийно завершает работу и не падает в зависимости от дополнительного ASTnode ... Я не уверен, что у нас есть достаточно кода, чтобы быть уверенным, почему это происходит. Пробовали ли вы перемещение всех узлов (node1, node2, node3, node10)? Это должно быть хорошо, если функции makeCharNode() и makeINTNode() работают нормально, но такие рудиментарные проверки могут спасти ваш бекон. Может быть полезно посмотреть, что делает функция makeNode(); гарантирует ли это, что все части узла правильно инициализированы.