c++ - 编写一个程序，使用栈将表达式 a b + c d e + * * 转换为表达式树。

Question

描述我不知道如何完成这项任务....但我刚刚创建了一棵树并输入了值..任何人都可以帮助我完成这项任务......堆栈也是节点类型，我们必须推值像 ab+ 这样的运算符，所以我们将把 a 作为节点，然后将 b 作为节点，当 + 出现时，我们创建一棵树，a 和 b 将成为它的叶子节点。

.代码

#include<iostream>

using namespace std;

class Node{
public:
    int data;
    Node *left;
    Node *right;
    Node()
    {
        data = 0;
        left = NULL;
        right = NULL;
    }
};

class Tree
{
    Node *root;
    void insert(int d, Node *node)
    {
        if (d < node->data)
        {
            if (node->left == NULL)
            {
                Node *leaf = new Node();
                leaf->data = d;
                node->left = leaf;
            }
            else
            {
                insert(d, node->left);
            }
        }
        else
        {
            if (node->right == NULL)
            {
                Node *leaf = new Node();
                leaf->data = d;
                node->right = leaf;
            }
            else
            {
                insert(d, node->right);
            }

        }
    }

    void inOrderDisplay(Node *subRoot)
    {

        if (subRoot != NULL)
        {
            inOrderDisplay(subRoot->left);
            cout << subRoot->data << "  ";
            inOrderDisplay(subRoot->right);
        }
    }

    void postOrderDisplay(Node *subRoot)
    {

        if (subRoot != NULL)
        {
            postOrderDisplay(subRoot->left);
            postOrderDisplay(subRoot->right);
            cout << subRoot->data << "  ";
        }
    }

    void preOrderDisplay(Node *subRoot)
    {

        if (subRoot != NULL)
        {
            cout << subRoot->data << "  ";
            preOrderDisplay(subRoot->left);
            preOrderDisplay(subRoot->right);

        }
    }

    void deleteSubtree(Node *subRoot)
    {
        if (subRoot != NULL)
        {
            deleteSubtree(subRoot->left);
            deleteSubtree(subRoot->right);
            cout << "\ndeleting: " << subRoot->data;
            delete subRoot;
            subRoot = NULL;
        }
    }

public:
    Tree()
    {
        root = NULL;
    }
    ~Tree()
    {
        deleteAll();
    }

    void insert(int d)
    {
        if (root == NULL)
        {
            Node *leaf = new Node();
            leaf->data = d;
            root = leaf;
        }
        else
        {
            insert(d, root);
        }
    }

    void inOrderDisplay()
    {
        inOrderDisplay(root);

    }

    void postOrderDisplay()
    {
        postOrderDisplay(root);

    }

    void preOrderDisplay()
    {
        preOrderDisplay(root);

    }
    void deleteAll()
    {
        deleteSubtree(root);
    }

};

.主类:

#include<iostream>
#include"task1.h"
using namespace std;

void main()
{
    Tree tree;

    tree.insert(10);
    tree.insert(6);
    tree.insert(14);
    tree.insert(5);
    tree.insert(8);
    tree.insert(11);
    tree.insert(18);
    cout << endl;
    system("pause");
    //tree.deleteAll();
}

Answer 1

根据你这里的代码，你只有一个void insert(int d, Node *node)函数，没有void insert(operator o, Node *node)功能。

我认为这表明您错过了重要的一点。树中的每个节点都可以是整数(就像您所做的那样)或运算符。在这两种情况下，我都将其称为字符串。每个不是叶子的节点都必须是运算符，并且所有叶子都必须是整数(或者在我们的例子中代表运算符/整数的字符串)。

然后，遍历您的输入，前三项的结果应该类似于:

    +
   / \
  a   b

下一步将是构建更多的子树(不确定您所拥有的输入的定义)，将它们保存在堆栈中，然后构建树的更多内部节点。

所以如果我上面显示的树被称为Tree(+)(为了便于使用)，并且初始堆栈是[a,b,+,c,d,e ,*,*]，然后在一次迭代后你将得到 [Tree(+),c,d,e,*,*] 并从那里继续。