Thread: Listing binary tree numbers by level

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    158

    Listing binary tree numbers by level

    I know there is an algorithm called Breadth-first traversal but I think it's a bit complicated and I didn't want to mix it with queues.

    I basically want to print the numbers in a binary tree level by level and I don't want to use a queue to store the values, just print them.

    This is a problem that will be (for sure) on my girlfriend's exam but she doesn't understand much of programming in general and I'm trying to help her doing it, though I'm having difficulties making this work because it's been a while since I coded in C and I always had problems regarding pointers.

    Could anyone help me with the code to the a function that lists the binary tree values level by level, without queues, just print them directly to the screen in the most easy way to understand?

    I would really appreciate it...

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I'm pretty sure you're going to have to deal with queues in the end. (You can pretend you're not using a queue by simulating it with an array or something, but it's still going to act like a queue.)

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    Why? I think that using queues would complicate a lot the exercise for the final exam where this question only weights 2 points in 20... There must be a simpler way to do it if it's all it's worth is 2 points... Otherwise, I don't think this question would be in the exam considering this is the first year and the class does not usually gets too complicated...

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I would guess that it's worth 2 points out of 20 (which is still 10%, which at least in the US is a letter grade) is that if you're allowed to say "suppose I have a queue implementation" the algorithm takes less than a minute to write down. If you have to build the queue as well and don't have it around somewhere, it may take longer. (And for that matter, it's not that hard to simulate a queue with an array, if you're willing to have a fixed limit -- you update the index of the head and the tail as you insert and remove.)

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    Well, I don't know if I can suppose I have a queue implementation but I'm think there won't be one so I can't really use a queue because I would have to code it also and I'm almost sure that's not what the teacher wants and/or is asking for this exercise.

    I could simulate it with an array as you say, but it would need to have a fixed limit and that will actually depend on the problem. I'm not sure if the question will display an input for the binary tree or if we should make a function that works for any tree...

    Yes, I know, it's hard to help me when I don't even know exactly what do I have at my disposal for this problem...

  6. #6
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    I ended up with this:
    Code:
    void printLevelOrderAux(Tree t, int level) {
    	if(t) {
    		if(level == 1) {
    			printf(" %d ", t->val);
    		} else if (level > 1) {
    			printLevelOrderAux(t->left, level-1);
    			printLevelOrderAux(t->right, level-1);
    		}
    	}
    }
    
    void printLevelOrder(Tree t) {
    	int i;
    
    	for(i = 1; i <= countSize(t); i++) {
    		printLevelOrderAux(t, i);
    	}
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree
    By Ideswa in forum C Programming
    Replies: 12
    Last Post: 10-25-2007, 12:24 PM
  2. Binary Search Tree - one last question
    By tms43 in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2006, 03:58 AM
  3. best STL method to implement a binary tree
    By MatthewDoucette in forum C++ Programming
    Replies: 8
    Last Post: 06-16-2006, 07:08 AM
  4. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 02:24 AM
  5. inserting characters into a binary tree
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-06-2001, 04:08 PM

Tags for this Thread