Thread: Tree Traversal

Hi Everyone! I'm have a General tree here and I have a problem on traversing it. Here's my code:

Code:

#include <stdio.h>
#include <stdlib.h>


typedef struct Tree {
    char* token;
    int level;
    struct Tree* left; 
    struct Tree* right;
} Tree;


Tree* newNode(char* token, int level) {
    Tree* node = (Tree*)malloc(sizeof(Tree));
    node -> token = token;
    node -> level = level;
    node -> left = NULL;
    node -> right = NULL;


    return node;
}


void insertTree(Tree** rootRef, char* token, int level, int currentLevel) {
    Tree *root = *rootRef;


    if(NULL == root)
        *rootRef = newNode(token, level);
  
    else {
        if(level == currentLevel)
            insertTree(&(root -> right), token, level, currentLevel);
        
        else
            insertTree(&(root -> left), token, level, currentLevel + 1);
    }
}


void displayTree(Tree* root) {
    if(NULL == root)
        return;


    putchar('\n');


    for(int i = 0; i < root -> level; i++)
        printf("----");


    printf("%s", root -> token);
    displayTree(root -> left);
    displayTree(root -> right);
}


int main(int argc, char *argv[]) {
    Tree* root = NULL;
    
    insertTree(&root, "ISPROPYL", 0, 0);
    insertTree(&root, "START", 1, 0);
    insertTree(&root, "OUT_STMT", 1, 0);


    insertTree(&root, "getout", 2, 0);
    insertTree(&root, "lss_thn_op", 2, 0);
    insertTree(&root, "OUTPUT_STMT", 2, 0);


    insertTree(&root, "identifier", 3, 0);


    insertTree(&root, "grt_thn_op", 2, 0);
    insertTree(&root, "trmntr_stmnt", 2, 0);


    insertTree(&root, "END", 1, 0);


    displayTree(root);
    putchar('\n');
    return 0;
}

And the output of the traversal is:

Code:

ISPROPYL
----START
--------getout
------------identifier
--------lss_thn_op
--------OUTPUT_STMT
--------grt_thn_op
--------trmntr_stmnt
----OUT_STMT
----END

What I'm expecting is:

Code:

ISPROPYL
----START
----OUT_STMT
--------getout
--------lss_thn_op
--------OUTPUT_STMT
------------identifier
--------grt_thn_op
--------trmntr_stmnt
----END

I'm going to use this to generate a AST for our parser.

For starters, I'm not sure your tree is getting built the way you think it is. I added a few printf statements to your insert function and got this:

Code:

Inserting ISPROPYL
Found ISPROPYL, level=1, currentLevel=0 going left
Inserting START
Found ISPROPYL, level=1, currentLevel=0 going left
Found START, level=1, currentLevel=1 going right
Inserting OUT_STMT
Found ISPROPYL, level=2, currentLevel=0 going left
Found START, level=2, currentLevel=1 going left
Inserting getout
Found ISPROPYL, level=2, currentLevel=0 going left
Found START, level=2, currentLevel=1 going left
Found getout, level=2, currentLevel=2 going right
Inserting lss_thn_op
Found ISPROPYL, level=2, currentLevel=0 going left
Found START, level=2, currentLevel=1 going left
Found getout, level=2, currentLevel=2 going right
Found lss_thn_op, level=2, currentLevel=2 going right
Inserting OUTPUT_STMT
Found ISPROPYL, level=3, currentLevel=0 going left
Found START, level=3, currentLevel=1 going left
Found getout, level=3, currentLevel=2 going left
Inserting identifier
Found ISPROPYL, level=2, currentLevel=0 going left
Found START, level=2, currentLevel=1 going left
Found getout, level=2, currentLevel=2 going right
Found lss_thn_op, level=2, currentLevel=2 going right
Found OUTPUT_STMT, level=2, currentLevel=2 going right
Inserting grt_thn_op
Found ISPROPYL, level=2, currentLevel=0 going left
Found START, level=2, currentLevel=1 going left
Found getout, level=2, currentLevel=2 going right
Found lss_thn_op, level=2, currentLevel=2 going right
Found OUTPUT_STMT, level=2, currentLevel=2 going right
Found grt_thn_op, level=2, currentLevel=2 going right
Inserting trmntr_stmnt
Found ISPROPYL, level=1, currentLevel=0 going left
Found START, level=1, currentLevel=1 going right
Found OUT_STMT, level=1, currentLevel=1 going right
Inserting END

It's not clear what level and currentLevel are really for. Also, I'm not sure I quite grasp your desired traversal method. What you implemented is a basic pre-order traversal. What type of traversal do you actually want? Simply the insert order?

Be careful how you specify the parent node, as you probably want support duplicates, since you likely will have more than one identifier, for example, in whatever you're parsing.

Also, you might not want to restrict yourself to a binary tree, since some operators/language elements may have more than two operands/components. For example, a switch statement can have any number of cases, not just 2; a program or function usually supports any number of statements, not just 2. This may actually facilitate your insertion.

Originally Posted by anduril462

Also, you might not want to restrict yourself to a binary tree, since some operators/language elements may have more than two operands/components. For example, a switch statement can have any number of cases, not just 2; a program or function usually supports any number of statements, not just 2. This may actually facilitate your insertion.

This is a General tree, here's my reference http://www.rsbauer.com/class/dsa2/sl...al%20Trees.pdf

Ahh, I see. You're using the left pointer as a child pointer and the right as siblings. Those words then (child and sibling) would make better names for the pointers. This would also make your insert make more sense, level corresponding to child/parent generations. You would simply find the right level, then traverse the sibling pointers until you're at the end, and append a node there (you could also insert in the middle of a sibling list if you needed to).

I come up with this code:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct Tree {
    char* token;
    int level;
    struct Tree* child; 
    struct Tree* sibling;
} Tree;


Tree* newNode(char* token, int level) {
    Tree* node = (Tree*)malloc(sizeof(Tree));
    node -> token = token;
    node -> level = level;
    node -> child = NULL;
    node -> sibling = NULL;


    return node;
}


void insertTree(Tree** rootRef, char* token, char* parent, int level, int currentLevel) {
    Tree *root = *rootRef;


    if(NULL == root) {
        *rootRef = newNode(token, level);
        printf("Successfully Inserted: %s at level = %d\n", token, level);
    }
    else {
        if(currentLevel == level) {
            printf("Found %s, level = %d, currentLevel = %d, parent = %s going to sibling\n", root -> token, root -> level, currentLevel, parent);
            insertTree(&(root -> sibling), token, parent, level, currentLevel);
        }
        else if(currentLevel == level - 1) {
            if(!strcmp(parent, root -> token)) {
                printf("Found %s, level = %d, currentLevel = %d, parent = %s going to child\n", root -> token, root -> level, currentLevel, parent);
                insertTree(&(root -> child), token, parent, level, currentLevel + 1);    
            }


            else if(NULL != root -> sibling) {
                printf("Found %s, level = %d, currentLevel = %d, parent = %s going to sibling\n", root -> token, root -> level, currentLevel, parent);
                insertTree(&(root -> sibling), token, parent, level, currentLevel);
            }
            else {
                printf("Found %s, level = %d, currentLevel = %d, parent = %s going to child\n", root -> token, root -> level, currentLevel, parent);
                insertTree(&(root -> child), token, parent, level, currentLevel + 1);    
            }
        }
        else {
            printf("Found %s, level = %d, currentLevel = %d, parent = %s going to child\n", root -> token, root -> level, currentLevel, parent);
            insertTree(&(root -> child), token, parent, level, currentLevel + 1);
        }
    }
}


void displayTree(Tree* root) {
    if(NULL == root)
        return;


    putchar('\n');


    for(int i = 0; i < root -> level; i++)
        printf("----");


    printf("%s", root -> token);
    displayTree(root -> child);
    displayTree(root -> sibling);
}


int main(int argc, char *argv[]) {
    Tree* root = NULL;
    
    puts("Inserting ISPROPYL");
    insertTree(&root, "ISPROPYL", NULL, 0, 0);
    puts("\nInserting START");
    insertTree(&root, "START", "ISPROPYL", 1, 0);
    puts("\nInserting OUT_STMT");
    insertTree(&root, "OUT_STMT", "ISPROPYL", 1, 0);


    puts("\nInserting getout");
    insertTree(&root, "getout", "OUT_STMT", 2, 0);
    puts("\nInserting lss_thn_op");
    insertTree(&root, "lss_thn_op", "OUT_STMT", 2, 0);
    puts("\nInserting OUTPUT_STMT");
    insertTree(&root, "OUTPUT_STMT", "OUT_STMT", 2, 0);


    puts("\nInserting identifier");
    insertTree(&root, "identifier", "OUTPUT_STMT", 3, 0);


    puts("\nInserting grt_thn_op");
    insertTree(&root, "grt_thn_op", "OUT_STMT", 2, 0);
    puts("\nInserting trmntr_stmnt");
    insertTree(&root, "trmntr_stmnt", "OUT_STMT", 2, 0);


    puts("\nInserting END");
    insertTree(&root, "END", "ISPROPYL", 1, 0);


    displayTree(root);
    putchar('\n');
    return 0;
}

I have a problem on the

Code:

insertTree(&root, "identifier", "OUTPUT_STMT", 3, 0);

It's inserting on the child of START

Code:

Inserting identifier
Found ISPROPYL, level = 0, currentLevel = 0, parent = OUTPUT_STMT going to child
Found START, level = 1, currentLevel = 1, parent = OUTPUT_STMT going to child
Successfully Inserted: identifier at level = 3

How can I solve it??

I think you need to take a step back, put the keyboard away for a bit and get out the paper and pencil. I even do this for simpler problems, but it's crucial for more complex stuff like this. If you can't solve the problem yourself, with paper and pencil, then you have no hope of programming a computer to solve it. You need to sit down with several samples of your language and insert them by hand -- pay attention to every little decision and step you take, as these will form the basis of your algorithm.

The problem you're having has to do with how you insert. Note that you start with a tree like

Code:

0   ISPROPYL
       |
1      +----START----OUT_STMT
                        |
2                       +----getout----lss_thn_op----OUTPUT_STMT

Now, you try to insert identifier at level 3, as a child of OUTPUT_STMT. You start at ISPROPYL with currentLevel == 0, which is neither == level or == level-1, so you go down a level. Now you're at START, with currentLevel == 1, which is neither == level or == level-1. So you go again to the child of your current node, which is the child of start. That node has no children, so root is NULL and you insert there. What you need is something more like a full DFS or BFS. However, neither of those are really ideal -- your algorithm just doesn't really support multiple tokens at the same level. Imagine the following tree -- it's theoretically possible unless your language somehow forbids it, though I can't imagine why (e.g. a compound statement with two OUTPUT_STMTs in it, each with their own identifier):

Code:

0    A
     |
     +----B----C----D--------B
                    |
                    +----F

If I try to go insert ident at level 2 under token B, which B do I insert under?

However, it seems to me that when you actually implement this tree in the real world, you may be building from the bottom up. Take a look at the shunting-yard algorithm for how to implement this with a stack.

You may want to try a simple math parser first, maybe with just + - * / operators, or maybe also parentheses () and ^ (exponent) for a bit more challenge.