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 に答える