Growing a Binary Tree

This is a discussion on Growing a Binary Tree within the C++ Programming forums, part of the General Programming Boards category; so i want to scan a string of an expression (ex: "1+2*3"), then put each of the element into a ...

  1. #1
    Computer guy
    Join Date
    Sep 2005
    Location
    I'm lost!!!
    Posts
    200

    Growing a Binary Tree

    so i want to scan a string of an expression (ex: "1+2*3"), then put each of the element into a binary tree. So the operator will be the node, and the numbers will be the leaf. And below is my code:

    Code:
    double GrowTree(const string& expression)
    {
    	char number[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    	char operation[] = {'+', '-', '*', '/'};
    	string tempEx = expression;
    	TreeNode<char>* treeRoot = new TreeNode<char>;
    	TreeNode<char>* treeCurrent = new TreeNode<char>;
    	treeRoot = NULL;
    	treeCurrent = treeRoot;
    
    	while(!tempEx.empty())
    	{
    		for(int i=0; i<sizeof(number)/sizeof(char); i++)
    		{
    			if(tempEx[0] == number[i])
    			{
    				TreeNode<char>* newLeaf = new TreeNode<char>;
    				newLeaf->Value = tempEx[0];
    
    				if ( treeCurrent == NULL )
    				{
    					treeRoot = treeCurrent = newLeaf;
    				}else
    				{
    					treeCurrent->Right = newLeaf;
    				}
    			}
    		}
    
    
    			//if find any operator sign
    			if( (tempEx[0] == '+' || tempEx[0]=='-'))
    			{
    				if(treeCurrent->Right == NULL)
    				{
    					TreeNode<char>* newRoot = new TreeNode<char>;
    					newRoot->Value = tempEx[0];
    				
    					//the operator will become the root
    					newRoot->Left = treeRoot;
    					treeCurrent = newRoot;
    
    					//treeRoot->Right = treeCurrent;
    				}else
    				{
    					TreeNode<char>* newRoot = new TreeNode<char>;
    					newRoot->Value = tempEx[0];
    					newRoot->Left = treeCurrent->Right;
    					treeCurrent->Right = newRoot;
    					treeCurrent = newRoot;
    					//treeRoot->Right = treeCurrent;
    				}
    			}else
    			{
    				if ( (tempEx[0] == '*' || tempEx[0] == '/' ))
    				{
    					if(treeCurrent->Right == NULL)
    					{
    						TreeNode<char>* newChild = new TreeNode<char>;
    						newChild->Value = tempEx[0];					
    						//the operator will become the root
    						newChild->Left = treeRoot;
    						treeCurrent = newChild;
    						//treeRoot->Right = treeCurrent;
    					}else
    					{
    						TreeNode<char>* newChild = new TreeNode<char>;
    						newChild->Value = tempEx[0];
    						newChild->Left = treeCurrent->Right;
    						treeCurrent->Right = newChild;
    						treeCurrent = newChild;
    						//treeRoot->Right = treeCurrent;
    					}
    				}
    			}
    		
    		tempEx.erase(tempEx.begin());
    	
    	}
    
    
    	return ValueOf(treeRoot);        //This is where the function calculate the expression, which is another function
    }
    At the end, i had no idea how to reverse and attach everything back to the 'treeRoot'. Can someone help me? Thank you very much

    I could have reduce the code a little bit at checking the operators, but you know . I'll reduce it later when i the whole thing works
    Hello, testing testing. Everthing is running perfectly...for now

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    You need to extract the bulk of that into a seperate resursive function that returns the operator node each time, and the previous call of the function on the call stack takes the return value and attaches that as it's own left or right sub-tree as appropriate. The last recursive call left on the stack then returns the head of the tree.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21