c - 我在函数树中插入节点的算法有哪些缺陷？

Question

我正在研究一种从数学函数构建树的算法。例如:

x^2+5*3

构建为

     /   +    \
    /          \
  / ^ \      / * \
  x   2     5     3

树的节点是对象

typedef struct node
{
    char * fx; // function
    struct node * gx; // left-hand side
    char * op; // operator
    struct node * hx; // right-hand side
} node;

所以上面的树实际上是这样的

                            (root node)
                      { 0, / , '+',  \   }
                          /           \
                         /             \
                        /               \
                       /                 \
                      /                   \
   { 0, / , '^', \ }                        { 0, / , '*', \ }
       /          \                             /          \
      /            \                           /            \
     /              \                         /              \
    /                \                       /                \
{"x", 0, 0, 0}     {"2", 0, 0, 0}         {"5", 0, 0, 0}    {"3", 0, 0, 0} 

我遇到问题的函数是在树中插入新节点的函数。例如，如果到目前为止已经构建的树是

  / ^ \
 /     \
x       2

我刚刚找到运算符 + 和它后面的数字 5，我需要将树重建为

       /   +   \
      /         \
   / ^ \         5
  /     \
 x       2   

我尝试使用的函数看起来像

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;
}

其中 opstack 由

定义

char opstack [] = {'+','-','*','^'}; // operators, with precedence sorted from lowest to highest

但是，出于某种原因，此功能无法正常工作。它根本没有重建树。知道我哪里出错了吗？

Answer 1

你所做的在逻辑上是不正确的。考虑以下代码段:

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;

所以您正在做的是在 X 和 R 之间插入一个节点，同时仍然保持 X 和 R 之间的连接，因此，在您的 printTree 函数中，它遍历 X 和 R 之间的链接并打印相同的内容。这就是为什么您会产生没有重建树的错觉。

解决办法是断开X和R之间的连接，将X和newNode连接起来。在您的 while 循环中，在叶节点之前 停止，然后将该节点的 ->gx 变量更改为 newNode