**** c++ binary parse trees help PLEASE URGENT??

[existence19]

**********PLEASE HELP**********

SORRY I TRIED TO INDENT THE CODE BUT IT DIDNT WORK OUT
I am trying to make a binary tree for conversion of postfix to infix. the binary trees class is as follows


template<class type>
class binaryTree
{
struct treeNode
{

type data;
binaryTree<type> *left;
binaryTree<type> *right;

};

treeNode * root;

void inOrder(treeNode *tnode);

void preOrder(treeNode *tnode);

void postOrder(treeNode *tnode);


public:

binaryTree();

binaryTree(treeNode *tnode);

binaryTree(treeNode *tnode, binaryTree<type> leftSub, binaryTree<type> rightSub);

bool isEmpty() const;

void inOrder();

void postOrder();

void preOrder();

void destroy(treeNode * &tnode);

~binaryTree();

};

the structure of the class has been given by the teacher so i can't make any change.
Here is the implementation of the class WHICH I HAVE WRITTEN:

template<class type>
binaryTree<type>::binaryTree()
{
root = NULL;
}

template<class type>
binaryTree<type>::binaryTree(treeNode *tnode)
{
root = tnode;
root->left = NULL;
root->right = NULL;
}

template<class type>
binaryTree<type>::binaryTree(treeNode *tnode, binaryTree<type> leftSub, binaryTree<type> rightSub)
{
root = tnode;
root->left=leftSub->root;
root->right=rightSub->root;
}

template<class type>
bool binaryTree<type>::isEmpty() const
{
return (root==NULL);
}

template<class type>
void binaryTree<type>::inOrder()
{
inOrder(root);

}

template<class type>
void binaryTree<type>:reOrder()
{
preOrder(root);

}

template<class type>
void binaryTree<type>:ostOrder()
{
postOrder(root);

}

template<class type>
void binaryTree<type>::inOrder(treeNode* tnode)
{

cout<<"here";
if(this->isEmpty())
return;

if(tnode!=NULL)
{
inOrder(tnode->left->root);
cout << tnode->data << " ";
inOrder(tnode->right->root);
}
}

template<class type>
void binaryTree<type>:reOrder(treeNode* tnode)
{
if(this->isEmpty())
return;

if(tnode!=NULL)
{
cout << tnode->data << " ";
preOrder(tnode->left->root);
preOrder(tnode->right->root);
}
}

template<class type>
void binaryTree<type>:ostOrder(treeNode* tnode)
{
if(this->isEmpty())
return;

if(tnode!=NULL)
{
cout << tnode->data << " ";
postOrder(tnode->left->root);
postOrder(tnode->right->root);
}
}


template<class type>
void binaryTree<type>::destroy(treeNode *&tnode)
{
if (tnode != NULL)
{
destroy(tnode->left->root);
destroy(tnode->right->root);
delete tnode;
}

tnode = NULL;
}

template<class type>
binaryTree<type>::~binaryTree()
{
destroy(root);
}



WHAT I HAVE TO DO AND WHAT I AN HAVING TROUBLE WITH
1) READ A POSTFIX EXPRESSION FROM A FILE AND MAKE A TREE. I HAVE TO DO THAT BY THE STACK METHOD.
**** I KNOW HOW TO WRITE THE CODE AND THE ALGORITHM BUT I AM CONFUSED.. I KNOW THAT I MAKE A STACK OF TYPE binaryTree and then write the algorithm. I don't know WHERE DO I READ FROM THE FILE, INSIDE OR OUTSIDE THE CLASS? WHENEVER I TRY TO MAKE A STACK<binaryTree> in the main file i get an error

2) i think i have a problem with the CONSTRUCTORS. THIS IS WHERE I GET A RUN TIME ERROR AND THE PROGRAM FAILS TO RUN. SUPPOSE I MAKE A function read file() in the class binaryTree

stack<binaryTree> treeStack;
treeNode * n;
n=new treeNode;
n->data='a';
binaryTree<char> b;
binaryTree<char> c(n); // this line gives an error on run and the program fails

I don't know why this constructor is not working. PLEASEEEEEEE HELPPPPPPPPPP.
ALSO TELL ME IF THE OTHER CONSTRUCTOR IS FINE. ANY OTHER SUGGESTIONS/ADVICE ARE WELCOME

[coder777]

I'd say that the constructor is ok. But later you have problems because you never pay attention whether 'left' or 'right' is NULL or not.

The destructor is supposed to look like this:

template<class type>
binaryTree<type>::~binaryTree()
{
  if(root != NULL)
  {
    if(root->left != NULL)
      delete root->left;
    if(root->right != NULL)
      delete root->right;
    delete root;
  }
}

Since 'delete root->left/right;' already involves the binaryTree destructor no recursion is necessary / i.e. is wrong.

I don't see the point of the 'destroy()' function, but you can implement it according to the destructor.

[existence19]

Hey.. thanks for t he help but i don't think that the destructor would work. i would recursively have to delete every node.
I am still stuck please help. i finally had my logic going and have made changes to my code. here is the new code.

#ifndef TREENODE_H
#define TREENODE_H

#include"stack.h"
#include<iostream>
#include<fstream>

using namespace std;




template<class type>
class binaryTree
{
struct treeNode
{

type data;
binaryTree<type> *left;
binaryTree<type> *right;

};

treeNode * root;

void inOrder(treeNode *tnode);

void preOrder(treeNode *tnode);

void postOrder(treeNode *tnode);

void destroy(treeNode *&tnode);


public:

binaryTree();

binaryTree(type data);

binaryTree(type data, binaryTree<type> , binaryTree<type>);

bool isEmpty() const;

void inOrder();

void postOrder();

void preOrder();

void destroy();

~binaryTree();

};

template<class type>
binaryTree<type>::binaryTree()
{
root = NULL;
}

template<class type>
binaryTree<type>::binaryTree(type data)
{
root = new treeNode;
root->data = data;
root->left = NULL;
root->right = NULL;
}

template<class type>
binaryTree<type>::binaryTree(type data, binaryTree<type> leftSub, binaryTree<type> rightSub)
{
root = new treeNode;
root->data=data;

root->left=&leftSub;

root->right=&rightSub;
}

template<class type>
bool binaryTree<type>::isEmpty() const
{
return (root==NULL);
}

template<class type>
void binaryTree<type>::inOrder()
{
inOrder(root);

}

template<class type>
void binaryTree<type>::preOrder()
{
preOrder(root);

}

template<class type>
void binaryTree<type>::postOrder()
{
postOrder(root);

}

template<class type>
void binaryTree<type>::inOrder(treeNode *tnode)
{

if(tnode==NULL)
return;

if(tnode->left!=NULL)
inOrder(tnode->left->root);
cout << tnode->data << " ";

if(tnode->right!=NULL)
inOrder(tnode->right->root);

}

template<class type>
void binaryTree<type>::preOrder(treeNode* tnode)
{
if(tnode == NULL)
return;

cout << tnode->data << " ";

if(tnode->left!=NULL)
preOrder(tnode->left->root);

if(tnode->right!=NULL)
preOrder(tnode->right->root);

}

template<class type>
void binaryTree<type>::postOrder(treeNode* tnode)
{
if(tnode == NULL)
return;

if(tnode->left!=NULL)
postOrder(tnode->left->root);

if(tnode->right!=NULL)
postOrder(tnode->right->root);

cout << tnode->data << " ";
}

template<class type>
void binaryTree<type>::destroy()
{
destroy(root);
}

template<class type>
void binaryTree<type>::destroy(treeNode*& tnode)
{
if(tnode == NULL)
return;



if(tnode->left!=NULL)
destroy(tnode->left->root);

if(tnode->right!=NULL)
destroy(tnode->right->root);
delete tnode;
tnode = NULL;
}

template<class type>
binaryTree<type>::~binaryTree()
{
destroy(root);
}

what my problems are now:

1) my destructor and destroy() are still giving problems..
2)inorder and everything else works but for some cases they do not. i think they are the destructor dependent though. they seem to be working when i don't use the destructor and the destroy function. example: something like this always works when i comment out the destructor and destroy..

binaryTree<char> a('a');

binaryTree<char> b('b');

binaryTree<char> c('+',a,b);

binaryTree<char> d('+',b,c);

binaryTree<char> e('*',a,d);

binaryTree<char> f('z',final,d);
f.inOrder();

but when i destroy a tree object and use it later in order seems to give problems.

3)my final question and most important.. how do i store the popped tree in another tree object. for example :
stack<binaryTree> s; // consider the stack has some objects
binaryTree tree;

tree=s.pop() gives a malloc error and run time error.

Please someone i really need help...

[coder777]

I see your problem: You're trying to build a tree with local variables, which does not make sense. The pointer to such an object is invalid as soon as the local goes out of scope (the function they're in ends).

template<class type>
binaryTree<type>::binaryTree(type data, binaryTree<type> leftSub, binaryTree<type> rightSub) // leftSub and rightSub are local variables to 'binaryTree()' and it is passed as a copy i.e. it copies the pointer of 'root'
{
root = new treeNode;
root->data=data;

root->left=&leftSub; // this is a pointer to a local variable

root->right=&rightSub;  // this too
} // at this point leftSub and rightSub don't exist anymore (and 'root' of the original passed variables is destroyed) but root->left and root->right are still hold the pointer to those now invalid local variables
...

binaryTree<char> c('+',a,b); // This passes 'a' and 'b' as copies. After the constructor of 'c' is done. 'root' of 'a' and 'b' is not valid anymore because 'leftSub' and 'rightSub' destroyed 'root'

...

There're 2 ways to solve your problem: Either work only with pointers (binaryTree<char> *a = new binaryTree<char>('a');) or copy the content and not the pointer of 'root' when you pass the variables.

I recommend using just pointer and then my suggestion of the destructor/destroy will work.