0

二分木を使用して式を評価しようとしています。ツリーには次の特徴があります。

  • 各ノードには、0 個、1 個、または 2 個の子があります。
  • 演算子を含むノードのみが子を持つことができます。
  • すべてのリーフ ノードは数値でなければなりません。
  • 簡単にするために、使用できる演算子は*およびのみです。+

それらのようなもの：
式ツリー

これは私のツリークラスです:

class ExpressionTree {
    struct Node {
        std::string data;

        Node *leftChild, *rightChild;

        Node(std::string d): data(d), leftChild(NULL), rightChild(NULL) {}
    } *root;
    uint tsize;
public:
    ExpressionTree(): root(NULL), tsize(0) {}
    Node* treeRoot() { return root; }
    void insert(std::string s);
};

そして、これは私の挿入機能です:

void insert(std::string s) {
    if (root == NULL) {
        root = new Node(s);
        ++tsize;
    } else {
        Node* current = root;
        while (true) {
            if (is_operator(current->data)) {
                if (current->leftChild == NULL) {
                    current->leftChild = new Node(s);
                    ++tsize;
                    return;
                } else if (current->rightChild == NULL) {
                    current->rightChild = new Node(s);
                    ++tsize;
                    return;
                } else {
                    if (is_operator(current->leftChild->data)) {
                        current = current->leftChild;
                        continue;
                    } else if (is_operator(current->rightChild->data)) {
                        current = current->rightChild;
                        continue;
                    } else {
                        std::cout << "Error: only nodes who hold operators"
                                  << " can have children." << std::endl;
                        return;
                    }
                }
            }
        }
    }
}

問題はこの関数にあります。二分探索木にノードを挿入する機能から書き始めたのですが、うまくいきません。単純なメイン (を使用しinsert()て 2 番目のツリーのノードを 1 つずつ追加する) を実行すると、エラーを返さずにクラッシュし、オンライン ソリューションの確認を要求する Windows 7 ダイアログのみが表示されます。

主な問題は、ツリーのすべての要素を検査するのではなく、ブランチのみを検査することであると思います。このため、新しいノードを不正な方法で追加します。残念ながら、これを解決する方法がわかりません。

この質問が具体的すぎないことを願っています。

注:is_operator()文字列を取り、trueそれが+またはの場合は戻り、*そうでない場合は false を返します。

4

2 に答える 2

1

この問題は、各ノードの親ノードのトレースを保持する可能性をクラスに追加することで解決できます。新しいクラスは次のとおりです。

class ExpressionTree {
    struct Node {
    std::string data;

        Node *leftChild, *rightChild;
        Node* parent; // +

        Node(std::string d, Node* p):
        data(d), leftChild(NULL), rightChild(NULL), parent(p) {}
    } *root;
uint tsize;
public:
    ExpressionTree(): root(NULL), tsize(0) {}
    Node* treeRoot() { return root; }
    void insert(std::string s);
};

前のものとの唯一の違いは、別のNode*データ メンバーの追加です。これにより、親ノードへのポインターが格納され、この方法でツリーを逆方向にたどることができます。

また、insert()関数にはいくつかの変更が必要です。ここにあります：

void insert(std::string s) {
    if (root == NULL) {
        root = new Node(s, NULL);
        ++tsize;
    } else {
        Node* current = root;
        while (true) {
            if (is_operator(current->data)) {
                if (current->leftChild == NULL) {
                    current->leftChild = new Node(s, current);
                    ++tsize;
                    return;
                } else if (current->rightChild == NULL) {
                    current->rightChild = new Node(s, current);
                    ++tsize;
                    return;
                } else {
                    if (is_operator(current->leftChild->data)) {
                        current = current->leftChild;
                        continue;
                    } else if (is_operator(current->rightChild->data)) {
                        current = current->rightChild;
                        continue;
                    } else {
                        current = current->parent->rightChild; // +
                        continue;
                    }
                }
            } else {
                std::cout << "Error: only nodes who hold operators "
                          << "can have children." << std::endl;
                return;
            }
        }
    }
}

以前のバージョンとの違いは次のとおりです:すべてのリーフ ノードが数値である場合 (つまり、子を持つことができないことを意味します) [1]、および ( で指定されているelseようifに)カーソルを現在のノードの親ノードに逆向きに移動させる割り当てを伴う前のelse 。while// +

さらに、コンストラクターもNode()変更されます。新しいノードが作成されるたびに、親のポインターと 2 番目の引数を渡して親とリンクされます。

最後に一言。要素を挿入する順序は、上から下、左から右です。たとえば、質問の最初のツリーに続いて、要素を次の順序で挿入する必要があります: *, +, *, 7, 121, 12, +, 9, 3.


[1] Dr_Sam によって提案されました。

于 2013-06-24T17:30:24.980 に答える
1

私は2つの問題を発見したと思います。

(ア)

写真の右側にある木に入ろうとするとします。上と下の はすでに入力*されて*い+ます。と も入力しまし7た121。

ここで を入力する12と、コードが失敗します。

ルートは演算子であり、両方の子は null ではないため、「else」句に入り、左側の子を現在の場所と見なします。しかし、この部分はすでに満たされています！したがって、そこには何も挿入できません。

ただし、エラーメッセージが表示されるはずなので、それが唯一のエラーかどうかはわかりません.

(ロ)

ツリーを数字で (演算子ではなく) 開始すると、葉を挿入しようとすると無限ループに入り、メッセージが表示されない (常に失敗する場合は最初のメッセージ) と思います。

于 2013-06-20T14:33:49.117 に答える