Printable View
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...
> 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'
hum...
but i need the code for the structure,and everything else...
just to see wha to do...
may-day:)
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
> 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.