BST array

This is a discussion on BST array within the C Programming forums, part of the General Programming Boards category; I need some help brainstorming an algorithm for implementing a given array into a BST array. This is what I ...

  1. #1
    Registered User Iron_Shortage's Avatar
    Join Date
    Apr 2009
    Location
    Denver, CO
    Posts
    3

    BST array

    I need some help brainstorming an algorithm for implementing a given array into a BST array.

    This is what I am stuck with using:

    My example array is "val[-1,4,2,1,3,6,5,7]" and I need to omit -1 and put the rest of the values correctly in a BST array "bst[4 2 6 1 3 5 7]". However, the bst array is first initialized to "bst[-1 -1 -1 -1 -1 -1 -1]". For some reason these arrays are global, too.

    My function call can only have two parameters in the main function: addBST(1, val[i]);

    This is what I'm thinking..

    addBST(int root, int newNode)
    function call one:
    if val[root] == -1
    bst[root-1] = val[root+1];

    function call two:
    if newNode < bst[root-1]
    if (bst[(root-1)*2+1] == -1)
    { bst[(root-1)*2+1] = newNode }
    else
    addBST(bst[(root-1)*2+1], newNode)

    This is what I have brainstormed so far. I would like some advice from experienced C programmers. Thanks in advance, friends.
    Last edited by Iron_Shortage; 04-17-2009 at 08:41 PM.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Why don't you throw together a sample program and see how it works?


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    Those child position calculations appear to be a bit off.
    You can notice from your sample array that children should be at parent*2+1 and parent*2+2.
    Also, the parent is at (child-1)/2.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User Iron_Shortage's Avatar
    Join Date
    Apr 2009
    Location
    Denver, CO
    Posts
    3
    It looks kind of weird because root == 1. One of the requirements is that the root parameter is always passing "1". So it is actually bst[(1-1)*2+1] == bst[1]. I haven't compiled anything yet, but I think that is the best way to move to the next node still; albeit, I could still be quite wrong.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    Well what you're got should work fine for getting to the left chld then.
    I wonder if they're insisting on skipping index zero to make it "easier" or whether they just don't realise that it isn't actually any harder or less efficient not to skip the first element.
    They'll probably just confuse some people into thining that arrays start at one.
    Not sure how we can be of much more assistance without seeing how you're going with the code.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User Iron_Shortage's Avatar
    Join Date
    Apr 2009
    Location
    Denver, CO
    Posts
    3
    Touching back with the main rules:

    The array val[8] = {-1,4,2,1,3,6,5,7} is initialized.
    The array bst[] is initialized to -1.

    Writing two functions for a BST and preOrder traversal with arrays, the rules of the game are the parameters for the call functions must be: (val[i] is using a loop)

    Code:
     
    addBST(0,val[i]);
    
    preOrder(0);
    I came up with some solutions, but they're the most intellectually devoid solutions I have ever come up with. I seem to have a mental road block before me. Does anyone have any problem solving solutions to make this code more efficient?

    Also, any suggestions on how to alter the program if the call parameters for root had to be "1" instead of "0"? Thanks in advance, friends.

    Code:
    void addBST(int root,int newNode)
    {
    	
    	if (newNode < 0)
    	  {bst[root] = val[root+1]; return; }
    
    	if (newNode == val[root+1])
    	  {return;}
    	
    	if (newNode < bst[root])
    	  {
    	  if (bst[(root)*2+1] == -1)
    	    { bst[(root)*2+1] = newNode; return;}
    	  else
    	    addBST(((root)*2+1), newNode);
    	  }
    
    	if (newNode > bst[root])
    	  {
    	  if (bst[(root)*2+2] == -1)
    	    { bst[(root)*2+2] = newNode; return;}
    	  else
    	    addBST(((root)*2+2), newNode);
    	  }
    
    	  return;
    
    }
    
    void preOrder(int root)
    {
    
    if (bst[root])
    	{
    	if (bst[root] != -1)
    		{
    		printf(" %d ", bst[root]);	
    		preOrder((root*2+1));
    		preOrder((root*2+2));
    		}
    	 }
    
    
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. Replies: 6
    Last Post: 11-09-2006, 02:28 AM
  3. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  4. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM
  5. Array Program
    By emmx in forum C Programming
    Replies: 3
    Last Post: 08-31-2003, 12:44 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21