Thread: Binary search tree implemented by use of an array

  1. #1
    Registered User
    Join Date
    Feb 2006
    Posts
    2

    Binary search tree implemented by use of an array

    so...this is the problem...
    i need to make a BST tnat has random integers in all nodes and then do a inorder print,and i have to construct a function tha would return how many nodes have only one child, and how many of them have both children.

    does anybody have any kind of written source code that could help me?!
    i know how to do this by use of pointers but this array sh** is to idiotic and i really dont know how to do this.help...

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > i know how to do this by use of pointers
    So instead of storing a pointer in a node of your tree, store array indices.

    The only slightly tricky bit is allocating 'nodes' from your array, which is basically down to marking each element of the array as 'free' or 'allocated'

  3. #3
    Registered User
    Join Date
    Feb 2006
    Posts
    2
    hum...
    but i need the code for the structure,and everything else...
    just to see wha to do...

    may-day

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    The root of the tree is index 0.
    The left child of any node is at "current index" * 2 + 1.
    The right child of any node is at "current index" * 2 + 2.

    Just remember those rules and you should be able to duplicate the necessary components of your pointer based tree. Like Salem said, you need to figure a way to mark/differentiate the indicies as being in use or available.

    So, for example to insert the value 18 into an empty tree you check the root (index 0) to see if it is available. Since the tree is initially empty, the root is available and you can place 18 in that index and then mark it as unavailable/in use.

    Next say we try to insert the value 46. Well, the root (index 0) has been marked as unavailable and its value is 18 which is less than 46 and so we need to move on to the right node which is at index 2 (0*2+2). Since index 2 is available, we put 46 into that index and mark it as unavailable... and so on and so on.

    The marking of the indicies as available or unavailable can be done in a couple of ways. The first would be to have a second array of essentially boolean values to keep track of what's going on in the array you are using to store the actual data in. The other way would be to store not just simply integers in the tree, but perhaps a struct consisting of an int and a bool "available/unavailable" value. ...if you know your values to be stored are going to look a certain way (all positive integers for example) then you can also say that a special value(s) will be used (any negative value in this example) to indicate that the node is empty and available for use
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > but i need the code for the structure,and everything else...
    But you first said

    "i know how to do this by use of pointers "

    So either you know how to implement a binary tree using the traditional approach or you don't.

    Algorithms and data structures are independent of implementation, so once you actually understand the principle, implementing them in a variety of styles shouldn't be that much of an issue.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 02:02 PM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM