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

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 之间的 link 和它打印相同。这就是为什么你会产生树没有被重建的错觉。

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

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

What are the flaws in my algorithm to insert a node in a function tree?

c

algorithm

tree

parsing

data-structures