-
plain tree traversal
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.
Code:
#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;
}
-
What question are you asking, exactly? My Hat thinks you want to know about the shift trick, that is, upon seeing '1' and then '2' and then '3' you want to have the value 123. In that case, every time you see a new digit, you have to "shift" the current number over one spot (in other words, add a zero to the end -- and you know how to turn 1 into 10 and 12 into 120 right?), and then add the new digit in.
-
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.