Thread: Print Tree Preorder

  1. #1
    Registered User
    Join Date
    Jan 2007
    Posts
    6

    Question Print Tree Preorder

    I am trying to write a function to print a binary tree as graph. Preorder print is chosen and the code I come out is:

    Code:
    void preorder_print(root*tree){
    	if (tree!=NULL){
    		printf("    %d\n",tree->key);
    		printf("\t");
    		preorder_print(tree->left);
    		printf("\n");
    		preorder_print(tree->right);
    	}
    }
    I want the tree to look something like that.
    5
    ├3
    │├2
    │└5
    └7

    └8

    I know that I can use ASCII characters but
    my problem is how to find the right tab to print each line (vertical tree graph would be fine).
    1.any proposals on that.
    2.any opinions about using the goto??
    Last edited by enisxisi; 01-07-2007 at 04:17 PM.

  2. #2
    Matt Conway bobthebullet990's Avatar
    Join Date
    Nov 2005
    Location
    Cambridge
    Posts
    122
    wow... this will get complicated if you have a lot of data in your tree! ...would it not be easier to code and to read using something like a table output? ...graphical outputs with ASCII chars all over the place look really messy and are really hard to follow! tabular outputs are simple and easy to map the exact whereabouts of any data! ...well... thats my opionion! ...I remember at uni one coursework was to write a digital circuit simulator in C, and it ended up easier to do printouts of the circuits in tabular format and say what type of gate each gate was and give the ID numbers of the parents for each gate!

    well.. good luck!
    Many junglists take pride in their belongin to what may be referred to as a globalised drum & bass subculture, as a subculture though, it is not nearly as distinct at gothic or punk!

  3. #3
    Registered User
    Join Date
    Jan 2007
    Posts
    6
    I though about tabular outputs and if I had a choice I will do it. The problem is that I have to do with ASCII chars or similar chars. It is just an exercise. My problem is that I can not find how to count the tabs I must go right with each recursion and then back left in meet a node.
    I do not want the code just an idea on how to implement it. I guess that the solution would be the same regardless the implementation table or ASCII.

  4. #4
    Registered User
    Join Date
    Jan 2007
    Posts
    6

    Solution????????

    OK I have thought of a solution. I post it here for evaluation and opinions. The idea is:
    Convert the binary tree to an 2 dimmesnion array and each line will have the following info:

    data arrayposition of the left child arrayposition of the right child

    We will built the tree graph verticaly.
    1 the root next line (with the goto)
    ├left child
    |
    | (how many depends of the position of the right child)
    |(must be enough to fit all the node between left and right
    |
    L right child

    Then move one space right and start the process again from rhe fisrt left child.

    I will try to right a draft code for that later but any opinions on that????

  5. #5
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    I'd love to comment, but I have no clue what you're trying to say. Maybe the code will make it clearer.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    The board has wiped out my answer and logged me out while I was answering - can this security measure be relaxed a bit?

    Adak

  7. #7
    Registered User
    Join Date
    Jan 2007
    Posts
    6

    Print tree as array

    OK here is one solution that I come up with.

    Code:
    void printArrayAsTree(ArrayNode a[], int n)
    {
    	printf("%d(", a[n].data);
    	if (a[n].left > 0)
    		printArrayAsTree(a, a[n].left);
    	printf("|");
    	if (a[n].right > 0)
    		printArrayAsTree(a, a[n].right);
    	printf(")");
    }
    Will this function print a tree as a tree in the screen like the tree in the beginning of the post??

  8. #8
    Registered User
    Join Date
    Jan 2007
    Posts
    6
    New idea why to convert the tree to table an then print the table? Can you do it like this?
    Code:
    void printTree (tree t)
    {
    	if (t != NULL) {
    		printf("%d(", t->data);
    		printTree(t->left);
    		printf("|");
    		printTree(t->right);
    		printf(")");
    	}
    }
    please comment on that.

  9. #9
    Registered User
    Join Date
    Jan 2007
    Posts
    6
    How to change the above function so that they will print the tree vertically and not in one line. The only think I can think is goto but any other suggestions.

  10. #10
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Umm . . . use a loop?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by enisxisi
    New idea why to convert the tree to table an then print the table? Can you do it like this?
    Code:
    void printTree (tree t)
    {
    	if (t != NULL) {
    		printf("%d(", t->data);
    		printTree(t->left);
    		printf("|");
    		printTree(t->right);
    		printf(")");
    	}
    }
    please comment on that.
    That won't do what you want. That's printing it out breadth first. You'll need depth first OR you can use a struct to keep track of the depth (ply) that is currently being printed out.

    You can't move the cp (cursor position or printhead), down to another row, before you complete ALL the possible printouts needed on it's right hand side (deeper in the tree), unless you want to keep track of each of the tree's depth's and make adjustments based on that, and that's possible only on the screen, not on a piece of paper.

    Adak
    Last edited by Adak; 01-10-2007 at 05:06 PM.

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. Personal Program that is making me go wtf?
    By Submeg in forum C Programming
    Replies: 20
    Last Post: 06-27-2006, 12:13 AM
  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