Thread: plain tree traversal

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    10

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

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  3. #3
    Registered User
    Join Date
    Feb 2008
    Posts
    10
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Tree traversal
    By recluse in forum C Programming
    Replies: 4
    Last Post: 12-05-2004, 04:00 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM