empty tree ::= ()
tree ::= empty tree | (w tree tree)
ex:
()
empty tree
(99(5()())(35(-5()())()))
99
/ \
5 35
/
-5
class Node
{
public:
int weight; // weight can be negative!
Node *left, *right;
Node():weight(0),left(NULL),right(NULL){}
Node(int d):weight(d),left(NULL),right(NULL){}
};
Construct a binary tree by given condition
I get problem with construct it, my program will crush and I have no idea about why it happened, the following is my code and I print out some information for debug, take (99(5()())(35(-5()())())) as a test case, it will print out 99(5( and crush, I think maybe problem is at which I deal with ) where I return node which is NULL, but I can’t find problem with it. By the way, this tree is expected to handle HUNDREDS of nodes in each tree, and Each of the test cases contains up to TEN-THOUSAND trees, will I run out of time with this program or what should I need to do?Thank for your time
Node* MyBinaryTreeOps::constructTree(Node *root, std::string treeStr)const
{
int idex = 1;//always look at the treeStr[1]
Node *cur=NULL;//use to pass in recursive call
if(treeStr[idex]!='('&&treeStr[idex]!=')'){//meet number create new node
stringstream ss;
while(treeStr[idex]!='('){
ss<<treeStr[idex];
if(treeStr.size()>1){//if size > 1 then remove the treeStr[1],to let treeStr[1] become next char in treeStr
treeStr.erase(1,1);
}
}
int num=0;
ss>>num;
std::cout<<num<<std::endl;//print out just for debug
std::cout<<treeStr[idex]<<std::endl;//print out just for debug
root = new Node(num);
}
if(treeStr[idex]==')'){//meet ')' return subtree constructed
if(treeStr.size()>1){
treeStr.erase(1,1);
}
return root;
}
if(treeStr[idex]=='('){//meet first '(' then construct left subtree
if(treeStr.size()>1){
treeStr.erase(1,1);
}
root->left = constructTree(cur,treeStr);
}
if(treeStr[idex]=='('){ //meet second '(' then construct right subtree
if(treeStr.size()>1){
treeStr.erase(1,1);
}
root->right = constructTree(cur,treeStr);
}
if(treeStr[idex]==')'){ //meet ')' return subtree constructed
if(treeStr.size()>1){
treeStr.erase(1,1);
}
return root;
}
}