c++ - 使用双指针创建树

Question

我正在尝试创建一棵树。基本思想是每当我看到“+”、“-”、“/”或“*”时，该变量就会成为主树的父级。例如，如果用户输入 1 + 1 ，树应该看起来

  +
1   1

请看一下我的插入函数。我已经编写了 sudo 代码，但我不知道如何编码。我对双指针感到不舒服。如果可以的话，请逐行解释它们，以便我能够理解。谢谢

这是我的代码

%{
#include <stdio.h>
#define true 1
#define false 0
int lookahead;
int lookahead1;
int error;
int count;
%}

// LEX codes
%%
[(] {return(111);}
[)] {return(222);}
[0-9] {return(333);}
[a-zA-Z] {return(444);}
[\+] {return(33);}
[\*] {return(44);}
[\/] {return(55);}
[\-] {return(66);}
[ \n\t] {return(0);}

%%    

// C code

struct node
{
    char  a;
    struct node * left;
    struct node * right;
};


struct node *root, * current;
// inserting into tree
void insert( struct node ** tree, struct node *item)
{

    printf("%c", item -> a);

    if (!(*tree))
    {
        *tree = item;
        return;
    }

     // this is where I need help

    if ( item-> a == '+' || item-> a == '-' || item->a == '*' || item->a == '/' )
    {
        item -> left = tree;
        break;  

    /*  struct node ** temp;
        temp= tree;
        *tree = item;
        (*tree) -> left = *temp;
    */      
        //insert (&(*tree) -> left, item);
    }
    else if ( (*tree) -> left == NULL )
    {
        insert (&(*tree) -> left, item);
    }
    else
    {
        insert (&(*tree) -> right, item);
    }

}

// c code ends here

// lex code
Goal ()
{
    return Expr(); 
}

Expr()
{
    if ( Term() )
        return ExprP();
    else
        return false;
}

ExprP()
{
    if ( lookahead == 33 || lookahead == 66 )
    {   
        current = malloc(sizeof(struct node));
        current -> a = yytext[0];
        current -> left = NULL;
        current -> right = NULL;
        insert(&root, current);     
        lookahead = yylex();
        if ( Term() )
            return ExprP();
        else 
            return false;
    }
    else if ( lookahead == 222 ||  lookahead == 0  )
        return true;
    else
        return false;
}

Term()
{
    if (Factor())
    {
        return TermP();
    }
    else
        return false;
}

TermP()
{
    if ( lookahead == 44 || lookahead == 55 )
    {
        current = malloc(sizeof(struct node));
        current -> a = yytext[0];
        current -> left = NULL;
        current -> right = NULL;
        insert(&root, current);     
        lookahead = yylex();
        if ( Factor() )
        {
            return TermP();
        }
        else
            return false;   
    }
    else if ( lookahead == 33 || lookahead == 222 || lookahead == 0 || lookahead == 66 )
        return true;
    else
        return false;   
}

Factor()
{
    if (lookahead == 111 )
    {   
        lookahead = yylex();
        if ( !Expr() )
            return false;
        if ( lookahead != 222 )
            return false;
        lookahead = yylex();

            return true;        
    }
    else if ( lookahead == 333 )
        {
        current = malloc(sizeof(struct node));
        current -> a = yytext[0];
        current -> left = NULL;
        current -> right = NULL;
        insert(&root, current);
            lookahead = yylex();
            return true;
        }
    else
        return false;
}

int yywrap(void)
{
return 1;
}


void printout(struct node * tree, int h) {
   if(tree->right) printout(tree->right, h+1);
    int i ;
    for ( i = 0; i < h ; i++)
        printf("   ");
   printf("%c\n",tree->a);
   if(tree->left) printout(tree->left, h+1);
}

// maing in c code

int main()
{
    root = NULL; 
    lookahead = yylex();
    if ( Goal() )
        printf ("\n\nThe string you entered successfully accepted\n\n");
    else
    {
        printf("\n\nThe string you entered failed to accept\n\n");
        printf("%s\n", yytext);
    }

    printout(root, 0);

return 0;
}

Answer 1

以下代码不正确:

item -> left = tree

即为结构节点*分配一个作为结构节点**的值。应该是:

item -> left = *tree

您正在传递**tree，以便您可以修改树参数的值，但它的所有使用都需要取消引用，以便您只有一个指针。