I'm trying to write a program that builds a full binary tree from an array containing an even number of sequential numbers. I know the memory allocation part, I'm just having trouble with how to pass the integers to act as array positions. This is what I've come up with so far:

tree root = maketree(a, 0, i) // a is an array of i elements, containing the
// numbers 1 to some multiple of 1000
tree maketree(int a[], int st, int max)
    tree root = makenode(a, max/2 + (some number));
    root->leftchild = maketree(a, 0, max/2 + (some number));
    root->rightchild = maketree(a, max/2 + (some number), max);

tree makenode(int a[], int i)
    tree t = newnode();
    t->element = a[i];
    t->leftchild = NULL;
    t->rightchild = NULL;

tree newnode()
    return malloc(sizeof(node));

The three places I'm unsure about are the places I've written (some number). Obviously I know they might not need a number added at all, or maybe some need a number subtracted. But at this point, I've tried every combination I could think of and nothing is coming out as a full binary tree. I think the definition I've been given is universal, but just in case, what I mean by full binary tree is a binary tree where all elements to the left of a node have elements that are less than the current node's element, and every node has two children, except for leaves of the "lowest" depth of the tree.

If anyone has a tip for what I can fill in, or a preexisting example, it would be greatly appreciated.

Recommended Answers

All 2 Replies

The root is going to be at index 0, left of element at index i will be 2i + 1 and the right will be at 2i + 2. Give those numbers a try.

binary tree implementation using an array in c language (data structures)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.