plain tree traversal

[kmel]

Hallo everyone . I am trying to write code for a tree traversal of plain trees (although all trees can be viewed as binary trees). So far i have written the code below. I would like to ask if you think my approach is correct. Furthermore, in the main procedure i want to parse a tree from a file and then call the post_traverse function. My problem is not the parsing of the file, instead i am having difficulties to understand how to assign each value i am going to read from the file to a node. For example, lets say i have a file like this: (1(2 (3 9)5(3))). A left parenthesis '(' signals a new child, while a right parenthesis ')' signals a new sibling. In this example how can i pass each value to the n -> firstchild or n -> nextsibling?

Thank you.

#include <iostream>
using namespace std;

struct treenode {
  string value;
  int numofchildren;
  struct treenode *firstchild;
  struct treenode *nextsibling;

};


int leaf (treenode *n, int depth) {
  if (n -> numofchildren == 0)
    return 1;
  else
    return 0;
}


int visit (treenode *n, int depth) {
  std::cout << depth << ":" << n -> value;
  return 0;
}


int post_traverse (treenode *n, int depth) {
  if (leaf(n, depth))
    visit(n, depth);
  else {
    // visit(n, depth);  //PRE
    post_traverse(n -> firstchild, depth + 1);
    while (n -> numofchildren - 1 > 0) {
      //        visit(n, depth);   //IN
      n -> numofchildren --;
      post_traverse (n -> nextsibling, depth + 1);
      visit(n, depth);
    }
    depth ++;
    return 0;
  }
}


int main() {

  return 0;
}

[kmel]

Hallo everyone, i ll be more specific about my problem. I do not understand how to hardcode a tree using my struct. Can anyone please help me, give an example so i can move on.

Thank you.

[mczapar]

In this example how can i pass each value to the n -> firstchild or n -> nextsibling?

assuming that n is a pointer to a treenode, and you have already done something like

n->firstchild = new treenode;

for all of the nodes that you want to create,

you should be able to just do something like

n->value = 1;
n->firstchild->value = 2;
...

[treuss]

For example, lets say i have a file like this: (1(2 (3 9)5(3))). A left parenthesis '(' signals a new child, while a right parenthesis ')' signals a new sibling.

I'm sorry to say, but to me this does not make sense. Can you post a picture (I love ASCII art) what you expect the tree, that results from (1(2 (3 9)5(3))) to look like?

While you draw the picture think about how you draw it, i.e. how you interpret the parenthesis. That will make it easier to code it.

[kmel]

Below is the tree that corresponds to (1(2 (3 9)5(3)))

          1
   2           5
3   9      3

Thank you

[treuss]

Below is the tree that corresponds to (1(2 (3 9)5(3)))

          1
   2           5
3   9      3

Thank you

That's missing the arrows (pointers) for firstchild and nextsibling. I see any node having a left and a right child, but the parenthesis syntax clearly allows more than two children, so I'm still confused. How would ((1 2)(3 4)(5 6)) look like?

[kmel]

Well ((1 2)(3 4)(5 6)) is not a valid tree. You must have a '(' then a node and then a new '(' with the children of that node and then ')' . So for example (2(3 4)) its a tree with 2 as a root and 3 , 4 as children.

     2
   /   \
 3      4

Another example will be (1(2(3 4) 5)) where 1 is the root, 2 and 5 are the children of 1, the 3, 4 (leafs) are children of 2 and 5 (leaf) has no children.

        1
      /    \  
    2       5
  /   \
3     4

Thank you for your help

[treuss]

So in short, the pointer called firstchild should point to the left child ( / in your drawings) and the pointer called nextsibling should point to the right child (\). Why not call the left and right in the first place?

Now as you have been able to do that on paper, just remember what you did and put it in the program. It comes down to having a pointer point to the "current" element of the tree and act as follows:

• If reading a number, add an additional child to the current element
• If reading an opening paretheses, make the element that was last added (the rightmost) the current element
• If reading a closing parentheses, make the parent the "current" element.

The last one will give you most trouble as your struct does not contain a parent pointer. You can either add it or keep track of your current elements, e.g. by using recursion.