trouble while constructing a tree....

[ARWA]

hi every one,im having some difficulties in constructing a tree linked list
i didnt yet study data structer.now if i want to construct a tree
and i dont care about the order of the data inside a node i only care
that the tree should as balanced as possible....

this is how i thought about it please if some one can explain it to me
ill be very thankfull..

if(root == NULL)
{
root = new TreeNode<type>
root->leftptr=NULL;
root->rightptr=NULL;
count++;}
else if(root->leftptr==null)
{
TreeNode<type> *newRoot;
newRoot=new TreeNode<type>;
newRoot->leftptr=NULL;
newRoot->rightptr=NULL;
count++;
}
else if(root->rightptr==NULL)
{
TreeNode<type> *newRoot;
newRoot=new treeNode<type>
newRoot->leftptr=NULL;
newRoot->rightptr=NULL;
count++;
}

now how do i put it in aloop or what so that
ill have tree....
thank you in advance...^____~

[hamsterman]

Well, if you only care that your tree is balanced, then why have a tree at all?

Anyway, if your node looks like this

struct Node{
   Node* left, right;
   //some data
   int count;

   //and a constructor which sets left, right and count to 0
};

your insert could look like this

void insert(Node*& root){
   if(root == 0) root = new Node();
   else{
      root->count++;
      if(root->left == 0) insert(root->left);
      else if(root->right == 0) insert(root->right);
      else if(root->left->count <= root->right->count) insert(root->left);
      else insert(root->right);
   }
}

[ARWA]

this is my treeNode

struct treeNode{
treeNode* leftptr;
treeNode* rightptr;
int data;
};

actually im going to read some numbers and just construct the tree...
its simple ...put our doc want to challange us ..he sayed that we should
not use recursion and here i became in trouble..
i realy did a good effort by my self to do it ...but i was stuck in
how to jumb from level 2 to 3 and so on how should my function handle it.?

by the way doing void insert(Node*& root)
dose it mean that the root in my class is passed by referance or its just
avariable.....what dose it mean..

thanks very much ^__^

[hamsterman]

ok. no recursion then. I should probably not do your homework, so I'll try to explain it.

Have a Node**N. This is a pointer to Node pointer. Make it point to the root of the tree. Then while(the pointer to which N points is not null ( *N != 0 ), advance to either branch (N = &(*N)->left, for example). Once the loop ends ( *N == 0 ), *N = new Node().

About the balance, you'll have a harder time doing it if your node does not count its children. Though you shouldn't be doing that at all..

Node*&, similarly to Node**, is a reference to Node pointer.

[ne555]

If you just want balance, what about using an array. New nodes will be added to the end
left_child = 2*i + 1
right_child = 2*i + 2
(where i is the index of the parent)

[ARWA]

after some search i found that using stack will help me ...thanks gays very much ill worke it ..