Member Avatar for jmoran19

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.

  • 3 Contributors
  • 2 Replies
  • 213 Views
  • 4 Months Discussion Span
  • Latest Post Latest Post by rydhima

Dani AI

Generated

— two different ideas are being mixed: (A) storing a binary tree in a flat array (level-order / heap-style) and (B) building a binary-search tree (BST) whose left values < node < right values. pointed to the array-storage approach (useful for compact, index-based access). For constructing a BST from a sorted sequential array, pick the middle element as root and recurse on the left and right subranges. Note: a strictly full/perfect tree (every internal node has two children) is only possible when n = 2^h − 1; if your array length isn’t that, you can still make a balanced BST but it won’t be perfectly full.

A simple, safe C++ pattern (pointer-based tree) — call with buildBalanced(A, 0, A.size()-1):

struct Node {
  int val;
  Node* left;
  Node* right;
  Node(int x): val(x), left(nullptr), right(nullptr) {}
};

Node* buildBalanced(const std::vector<int>& A, int lo, int hi) {
  if (lo > hi) return nullptr;
  int mid = lo + (hi - lo) / 2;        // integer mid keeps indices correct
  Node* root = new Node(A[mid]);
  root->left  = buildBalanced(A, lo, mid - 1);
  root->right = buildBalanced(A, mid + 1, hi);
  return root;
}

Python equivalent:

class Node:
  def __init__(self,v):
    self.v=v
    self.left=None
    self.right=None

def build_balanced(A, lo, hi):
  if lo>hi: return None
  mid=(lo+hi)//2
  r=Node(A[mid])
  r.left=build_balanced(A, lo, mid-1)
  r.right=build_balanced(A, mid+1, hi)
  return r

Troubleshooting notes: off-by-one errors come from the base case and using mid±1 correctly; for even-sized segments decide consistently whether to take the left or right middle to keep shape predictable. If you actually want array-storage (no pointers), fill an array level-order after building the pointer tree (or place elements directly into level-order positions); as noted, level-order index arithmetic is the right tool for that representation. If a perfect/full tree is required, trim or pad the input so its length equals 2^h−1.

Recommended Answers

All 2 Replies

Member Avatar for zortec

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.

Member Avatar for rydhima

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, networking, learning, and sharing knowledge.