CODEWITHSUNDEEP
c++tree
Heifetz_Fan
Heifetz_Fan

Reputation: 463

How to initiate a binary tree with values read from a vector in C++?

I'm trying to run some tests on the binary tree implemented in C++. I used a struct to create tree nodes:

    struct TreeNode
    {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

I want to test if it's a balanced binary tree, invert a binary tree, etc. So I have to initiate a tree like this:

   4
    \
     2
    /
   6

...for vector input = {4, NULL, 2, 6}, or {4, -9999, 2, 6} if C++ cannot take different types in one vector (can it?).

But all the c++ implementation I could find for binary tree node insertion are about inserting the node according to the node's value, which, essentially creates a in-order binary search tree.

I'm wondering if and how can I create a binary tree just based on the input vector, with the 1st (input[0]) value as the root value?

Upvotes: 0

Views: 1733

Answers (2)

Kevin Aud
Kevin Aud

Reputation: 398

Seems like a good job for a recursive algorithm. Binary trees can be equivalently represented with arrays using the following rules. There are good visual representations of what I'm talking about online.

  • left child of array[k] = 2*k+1
  • right child of array[k] = 2*k+2

I had to use these rules in my data structures course (shudder) to implement binary heaps. My memory on exact C++ syntax and methods is a tiny bit rusty and I'm too lazy to test my code, so forgive me for any mistakes in that department. The logic should be good though.

arrayToTree(TreeNode* node, vector<int>& v, int vIndex, int vLength){
   //I'll put these in separate variables for readability
   int left = (vIndex * 2) + 1;
   int right = (vIndex * 2) + 2;

   // make sure that left isn't greater than the length of the
   // index because you might get a memory access error or something
   // if you check the value of an index that doesn't have memory
   // allocated for it yet. You could combine these two if
   // statements,just separated them for readability.
   if(!(left >= vLength - 1)){

      // check if left child has corresponding vector value
      if(v[left] != null)){
         node->left = new TreeNode(v[left]);
         arrayToTree(node->left,v,vIndex,vLength);
      }

      // this is nested because if the left index was greater
      // the size of the index then the right must be as well.
      // no reason to run this statement if the left check failed.
      if(!(right >= vLength -1)){

         //check if right child has corresponding vector value
         if(v[right] != null)){
            node->right = new TreeNode(v[right]);
            arrayToTree(node->right, v, vIndex, vLength);
         }
   }

}

/* assuming vector is called "v" */
TreeNode* root;
root = new TreeNode(v[0]);

arrayToTree(root, v, 0, v.size());

Full disclaimer. Again, I didn't run any of this code so I'm not guaranteeing you can drag and drop it into your IDE and it'll run the first time, but hopefully this will at least give you an idea of how it could be done!

EDIT I just realized that the way you want to store them in a vector would not work with the way my function is set up, because you aren't placing 'null' values in the vector for children of 'null' elements. In order to use my function you'd have to think of your example tree like:

        4
     /     \
   NULL       2
  /   \     /   \ 
NULL NULL  6    NULL

and represent it with {4,NULL,2,NULL,NULL,6,NULL}

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490808

No, a C++ vector can't hold different types in the same vector (though, if you want to badly enough, you can create something like a vector<boost::variant> or something similar). It will work for the specific case of {4, NULL, 2, 6}, but probably won't give the effect you want (NULL is a macro that expands to an integer constant with the value 0, so it'll be essentially the same as {4, 0, 2, 6}, and the code wouldn't have any way of knowing this zero was intended to be unusual, and would just insert a node with the value 0 into the tree.

Yes, it's entirely possible to create a tree that just creates and inserts the nodes in the order they're given rather than attempted to create a sorted binary search tree. Once you've decided on a way to specify the end of a particular branch, you just create nodes and splice them onto the tree. Keeping track of the right place to start adding the next node when you reach the end of a particular branch can be a little bit finicky, but other than that it's all pretty straightforward.

Upvotes: 1

Related Questions