Binary Trees with arrays

I have recently written a program that works with binary trees with linked lists. I now need to take the same program and write it for using arrays. I have my LNR, LRN and NLR scans written for linked list as well and using them for linked list seemed trivial but for arrays I'm a bit lost on how to do those searches in an array. I'm sure if I can get the array made right then I could probably figure out the scans.

ascii (1062)

what are you searching for? generally to search an array just use a loop to go through every element until you find what you want

sorthon123 (131)

well a binary search tree isnt a search its self its a way of storing information say for example you have the numbers 4,5,8,20,30,39,25,1 and you picked 30 as your root. Your search tree would look something like...

 
                          30
                    20       39
                8     25   
             5
          4
        1

The rule being everything less then the root of a tree must go to the left of the root and everything larger goes to the right. So where at 20 and 25 25 is less then 30 so its on the left but larger then 20 so it then gets put to the right side of the subtree were 20 is the "root" of that subtree

Last edited on

sorthon123 (131)

Pretty much im trying to write preorder and post order functions to work for an array i already did it for linked list but for some reason the array part isnt coming to me as easily as the linked list part.

this is my code for the linked list scans, can anyone help me mod them so it works for an array rather then link list

void LNRscan(node* current)
        {
                if(current->lptr != NULL)
                LNRscan(current->lptr);

                cout<<current->data<<" ";

                if(current->rptr != NULL)
                LNRscan(current->rptr);
        }
void NLRscan(node* current)
        {
                cout<<current->data<<" ";
                if(current->lptr != NULL)
                NLRscan(current->lptr);

                if(current->rptr != NULL)
                NLRscan(current->rptr);
        }
void LRNscan(node* current)
        {

                if(current->lptr != NULL)
                LRNscan(current->lptr);
                if(current->rptr != NULL)
                LRNscan(current->rptr);
                cout<<current->data<<" ";
        }

if i could get someone to do or help me with the first one i could more then likely figure the rest out from that. at the moment for the first search i just used a quick sort and sorted the array but thats kind of cheating.

Last edited on

webJose (2948)

If I understood correctly, you want to store a binary tree in an array. If I understood correctly, then (without even attempting to do it) I would imagine that the simplest conversion would be to change the pointers of the nodes to indexes:

template<class T>
struct BTNode
{
    T Data;
    int leftIndex;
    int rightIndex;
};

Now, every time you need to add an element, you add it at the end of the array:

1
2
3

//"Black box" function that stores a new item:
template<class T>
int StoreItem(T arr[], const T &newVal); //The return value is the index where the item was stored.

At this point you should be able to treat the index as a pointer and therefore everything else should work with minimal modification.

sorthon123 (131)

webJose, this being a creative fix for my problem its pretty much cheating. I had already planned to make my array into linked list in a sense but my professor did not approve.

Last edited on

Topic archived. No new replies allowed.

C++

Forum

Binary Trees with arrays