0

我需要弄清楚如何创建算术表达式树。

我可以只使用一组数字来创建简单的二叉树。下面有一个代码示例：

这是我的树的简单节点。

typedef struct _node {
    int key;
    struct _node *left, *right;
} node;

这就是我向二叉树添加新节点的方式：

node* add_tree(node *root, int val) {    
    if(NULL == root) {
        root = crnode(val);
    }    
    if (val < root->key) {
        if (NULL == root->left) {
            root->left = crnode(val);
        }
        else {
            add_tree(root->left, val);
        }
    }

    if (val > root->key) {
        if (NULL == root->right) {
            root->right = crnode(val);
        }
        else {
            add_tree(root->right, val);
        }
    }    
    return root;
}

这是我向树中添加新数字的主要功能和步骤：

int main(int argc, const char * argv[])
    {    
        node *tree = add_tree(NULL, 5);
        tree = add_tree(tree, 6);
        tree = add_tree(tree, 7);
        tree = add_tree(tree, 3);
        return 0;
    }

我的问题是：如何转换这段代码，我不仅可以使用数字，还可以使用运算符（例如 + - / *）。

例如，我需要将表达式 5 * (10 - 5) + 6 * 4 转换为树。我怎样才能做到？

4

1 回答 1

4

表达式中的节点是以下两种情况之一：运算符或值。所以你需要划定。有几种方法可以做到这一点，但由于这是家庭作业，我倾向于有点谨慎，让你使用迄今为止学到的编程概念来解决一些问题。

所以我决定通过展示如果你的节点工作时你的树可能会是什么样子来帮助你：

      +
     / \
    /   \
   /     \
  *       *
 / \     / \
5   -   6   4
   / \
  10  5

您可能想放弃“构建树”的概念，而将其视为“构建表达式”。这可能是阻碍你前进的原因。您最终可能会得到一些像这样使用的函数：

node *expr = subtract(value(10), value(5));

这构建了树的一部分。看看发生了什么？=)

于 2012-09-24T13:52:56.033 回答