Subscript/index a linked binary tree

[duragezic]

Hmph, so I got this assignment to do, and one of the major hurdles I have is to implement operator overloading on some data structures we made. Basically a lot of my other operators depend on being able to subscript with brackets on these data structures, so that they can be accessed like an array[indx].

But the tree was built as a linked tree, so it seems kinda tricky to access it with subscripts/indices.

Element [0] would access the smallest value in the binary tree. So, given the basic in-order recursive traversal of

if(hasLeft()) then visitLeft()
access node's value
if(hasRight()) then visitRight()

Is this what I would use? But I guess the access part is the problem. I thought I would increment a counter at that point, and check if that counter is equal to the subscript, but it doesn't work like I need it to. Basically, going all the way left would be element zero, but after that I don't know how to find element 1, and so on.

Anyone got any ideas or hints for me?

 

[duragezic]

Bump.. I haven't been able to figure this out. A big part of this assignment rides on getting this subscript to work for the tree. I've tried ALL different kinds of things, but it seems like an inorder traversal should do it still. I even tried using an inorder traversal to make an array and access it that way (prolly wouldn't sit well with the instructor, but hell I need something working), but kept getting seg faults anyway! :disgust:

I attached some code below, but it finds element [0] as the root always, when in fact element [0] needs to be the smallest number, element [1] next smallest, etc.. with element[size-1] being the largest.

Can anyone give me an idea on if this inorder traversal would even work?

 

[Madwand1]

If your data is already sorted inorder in the tree, then you have to use an inorder traversal to access it in order. To go about implementing the inorder traversal, you first need to understand the recursion properly.

Recursion is always about the termination and the reduction. Recursive traversals are always about the "visit" and the reduction just follows the tree. You should be able to write a generic traversal that just does a generic "visit", and then plug in your "visit" for a specific problem.

Here the problem amounts to numbering the nodes in order. What would the "visit" be here? It would be the part that numbers the node.

E.g. tree of

5
/
4 6

Traverse left of 5
Traverse left of 4 -> null -> nothing
Visit 4 => count node. counter = 1
Traverse right of 4 -> null -> nothing
Visit 5 => count node. counter = 2
Traverse right of 5
Traverse left of 6 -> null -> nothing
Visit 6 => count node. counter = 3
Traverse right of 6 -> null -> nothing

The above is an example of the basic logic. You have to understand that fully and come up with some plan for executing an idea. The rest is just implementation detail which can take various forms. If you jump into the implementation details without a clear understanding of the basic logic, you're going to thrash around until you do understand it.

There are a few significant implementation details left here: (1) How and when to stop counting. (2) How to pass in and return the counter to higher levels (3) How to pass out the target node as the result. Hint: (3) and (1) can be related.

I think this is about as much as I'm willing to do for you here. Good luck with your homework.

 

[duragezic]

Ok, well I guess I am on the right path, and the implementation details you left me with are seemingly easy, but damn, I can't get this thing work. The rest of my program is riding on this subscript for a tree, so I had to write everything else assuming that this subscript thing will work, so if I ever get the subscript working, the rest of my program will hopefully work, but hah, that doesn't happen very often.

I attached code to a little bit different way of doing it. Using the example tree you posted, it finds [0] as value 4, but [1] as 6, and [2] as seg fault.

Can you give me any other hints or point out something I did obviously wrong?

 

[Madwand1]

You're still not counting properly. (1) You should count the current node, i.e. increment i, before the test "if ( i == n )". (2) i is only increasing down the tree because of the method of parameter passing. When you're back at node (5) in my example, i is back to 0 -- it should be 2, because node (5) is the 2nd node inorder.

A simple trace -- say printing i at the point of the visit, will show you what's going on. A test call with n = size of tree should produce a trace sequence of 1 through n. If you print the values in addition, you should see that they're increasing according to how the tree's data is sorted.

I guess the seg fault is due to not testing for null properly in the calling code. You'd encounter unexpected nulls due to the counting not working properly and so not finding the desired value.

 

[duragezic]

Alright, thank you. I think I got it working!