recriating a bst tree from inorder

This is a discussion on recriating a bst tree from inorder within the C Programming forums, part of the General Programming Boards category; i have an inorder traversal array (in every node we have only two sons or no sons) and i need ...

  1. #1
    Banned
    Join Date
    Jul 2009
    Posts
    46

    recriating a bst tree from inorder

    i have an inorder traversal array (in every node we have only two sons or no sons)
    and i need to construct a BST tree out of it.
    if i had freedom i would do a fuction of node build(arr,start,end)
    ABCREFG
    i would build a recursive function which will get R in the middle
    then for the leftside i would send indexes from A to C
    and for the right side E to G

    but i am asked to write a function which has only node * build(int* arr,lenght);

    how??

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    Quote Originally Posted by cfan View Post
    i have an inorder traversal array (in every node we have only two sons or no sons)
    and i need to construct a BST tree out of it.
    if i had freedom i would do a fuction of node build(arr,start,end)
    ABCREFG
    i would build a recursive function which will get R in the middle
    then for the leftside i would send indexes from A to C
    and for the right side E to G

    but i am asked to write a function which has only node * build(int* arr,lenght);

    how??
    You can convert between the two. When you want to write:

    Code:
    build( arr, start, end );
    Instead you write:

    Code:
    build( arr + start, end - start );
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by cfan View Post
    i have an inorder traversal array
    I know what inorder traversal is but I've never seen it refer to an array: does that mean the numbers are in the order they would be if you traversed a tree with them "inorder"?

    Anyway, not sure why you have a problem with build(arr,start,end) vs build(int* arr,lenght). For the recursion, you can set the "start" value by submitting that as the array like this:
    Code:
    int ray[10];
    build(&ray[3],7);
    array[0] in build() will now be the same as array[3] in the caller.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Banned
    Join Date
    Jul 2009
    Posts
    46
    i tried to understand using this ***R***
    but i cant see to what side left or right
    Code:
    build( arr + start, end - start );
    it refers too?

    because if start if 0 at the begginig then our range doesnt cut down at all

    for the left and right side we need separated ranges?
    Last edited by cfan; 08-04-2009 at 12:48 PM.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by cfan View Post
    i tried to understand using this ***R***
    but i cant see to what side left or right
    Code:
    build( arr + start, end - start );
    it refers too?

    because if start if 0 at the begginig then our range doesnt cut down at all

    for the left and right side we need separated ranges?
    If your root is at 0, then that's (almost?) what you would want to build the right side -- the right side would start at arr[0], and it would have end-start = end elements in it. You need to figure out a way to figure out the root. For instance if you had 1 2 3 4 5 6 7, I would think that you could make 2, 4, or 6 the root.

  6. #6
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    its easy you use len not as the length but as the number of cells in each subset

    i is allways the middle of lenso the left x(arr+1,len-i)
    and for right x(arr+i+1,i)

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, 06:59 PM
  2. BST delete again, but this time I think I'm close
    By tms43 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2006, 06:24 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04: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, 11:45 PM

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