What are the disadvantages in my algorithm for inserting a node into a function tree?
I am working on an algorithm that builds a tree from a math function. For example:
x^2+5*3
is created
/ + \
/ \
/ ^ \ / * \
x 2 5 3
Tree nodes are objects
typedef struct node
{
char * fx; // function
struct node * gx; // left-hand side
char * op; // operator
struct node * hx; // right-hand side
} node;
so that the above tree is really like
(root node)
{ 0, / , '+', \ }
/ \
/ \
/ \
/ \
/ \
{ 0, / , '^', \ } { 0, / , '*', \ }
/ \ / \
/ \ / \
/ \ / \
/ \ / \
{"x", 0, 0, 0} {"2", 0, 0, 0} {"5", 0, 0, 0} {"3", 0, 0, 0}
The function I came across is the one that inserts a new node into the tree. For example, if a tree that has been built so far is
/ ^ \
/ \
x 2
and I just found an operator +
and the number 5
following it, I need to rebuild the tree to
/ + \
/ \
/ ^ \ 5
/ \
x 2
The function I'm trying to do looks like
void insertInTree ( node * * curRootPtr, char * newOp, node * newNode )
{
// crpp: Pointer to a pointer to the node element that is the current root
// newOp: New operator found
// newNode: New node corresponding to the expression following the operator
node * rightTraveler = *curRootPtr;
while (!0)
{
if (rightTraveler->op)
{
long thisOpIdx = strchr(opstack, *rightTraveler->op) - opstack;
long newOpIdx = strchr(opstack, *newOp) - opstack;
if (thisOpIdx > newOpIdx) break; // if new operator has a lower precendence than the
// operator on the current node,
rightTraveler = rightTraveler->hx;
}
else // reached a node that has no children
{
break;
}
}
node * temp = rightTraveler;
rightTraveler = malloc(sizeof(node));
rightTraveler->gx = temp; rightTraveler->op = newOp; rightTraveler->hx = newNode;
}
where opstack
is defined
char opstack [] = {'+','-','*','^'}; // operators, with precedence sorted from lowest to highest
For some reason this feature doesn't work. This is not tree restoration at all. Any idea where I am going wrong?
source to share
The wbhat you are doing is logically wrong. Consider the following snippet:
node * temp = rightTraveler;//currently rightTraveler is the rightmost leaf node, say R, accessible from some node, say X(may be null)
rightTraveler = malloc(sizeof(node)); //rightTraveler is newly assigned
rightTraveler->gx = temp; //temp is R, now accessible from new rightTraveller and from X
rightTraveler->op = newOp; //assignes values to new node
rightTraveler->hx = newNode;
so you do a node insertion between X and R while keeping the link between X and R, so in your printTree function, it goes through the link between X and R, and it prints the same one.That’s why you get the illusion that the tree is not being rebuilt ...
The solution is to break the link between X and R and reference X with the newNode. In the while loop, stop just before the leaf node and then change this variable node -> gx to newNode
source to share