c++ - 如何从后缀表达式制作表达式树？

Question

我想用 C++ 创建树。 我可以在没有错误或警告的情况下编译代码，但我没有得到输出。

我认为错误是 inorder fn，但不知道如何删除它。

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

struct tree
{
    int data;
    struct tree * left;
    struct tree * right;
};
typedef struct tree * TREE;

TREE maketree(int x)
{
    TREE tree = (TREE)malloc(sizeof(tree));
    if(tree == NULL)
    {
        return NULL;
    }
    tree->left = tree->right = NULL;
    tree->data = x;
return tree;
}

void setleft(TREE tree,int x)
{
    if(tree == NULL || tree->left != NULL)
    {
        cout<<"\t Error !! Inserting New Node At Left Side  !\n";
    }
    else
    {
        tree->left = maketree(x);
    }
}

void setright(TREE tree,int x)
{
    if(tree == NULL || tree->right != NULL)
    {
        cout<<"\t Error !! Inserting New Node At Right Side !\n";
    }
    else
    {
        tree->right = maketree(x);
    }
}

void inorder(TREE root)
{
    if(root != NULL)
    {
        TREE left=root->left;
        TREE right=root->right;
        inorder(left);
        cout<<root->data;
        inorder(right);
    }
}

void main()
{
clrscr();
    TREE root = NULL,child,parent;
    int i,j = 1;
    cout<<"Root Of Binary Search Tree :- ";
    cin>>i;
    root = maketree(i);
    cout<<"\n\n";
    while(i)
    {
        cout<<j<<" Node Value:- ";
        cin>>i;
        if(i < 0)
        {
            break;
        }
        parent = child = root;
        while((i != parent->data) && (child != NULL))
        {
            parent = child;
            if(i < parent->data)
            {
                child = parent->left;
            }
            else
            {
                child = parent->right;
            }
        }
        if(i == parent->data)
        {
            cout<<"\t Value "<<i<<" Already Present In BST !!\n";
        }
        else if(i < parent->data)
        {
            setleft(parent,i);
        }
        else
        {
            setright(parent,i);
        }
        j++;
    }
    inorder(root);
getch();
}

Answer 1

如果你想用 C++ 编写，那么就用 C++ 编写。使用构造函数和析构函数以及类方法。可能使您的数据成员私有(private)。并使用 new而不是 malloc并且您的析构函数可能想要删除(树的子节点)。

除了合并了 C++、iostream 及其旧的已弃用的非标准版本中最糟糕的功能之外，您编写的内容都是用 C 语言编写的。

这看起来像是一些学校练习。

我也看不到你在哪里free您使用 malloc 分配的数据.

您的排序逻辑应该在基于树的函数中，而不是在主函数中。

您的“错误”可能是输出中缺少空格，但我不知道。

使用 tree 是合法的，但不是好的做法作为数据类型(它是一个结构，在 C++ 中不需要用结构限定)和变量(它经常被使用)。

好的，现在是一些代码，主要基于您的代码。

class tree
{
    tree * left;
    tree * right;
    int value;

public:
    explicit tree( int v );
    ~tree();

    bool insert( int v );
    void print( std::ostream& ) const;

private:
    tree( const tree& );
    tree& operator=( const tree& );

};

tree::tree( int v ) : 
   left( NULL ), 
   right( NULL ),
   value( v )
{
}

tree::~tree()
{
    delete right;
    delete left;
}

bool tree::insert( int v )
{
   // inserts v in the correct place in the tree, returns true
   // if it inserted or false if it already exists

   // I want you to fill in the detail for this function
}

void tree::print( std::ostream& os ) const
{
   // prints the tree
    if( left )
    {
       left->print( os );
    }
    os << value << '\n';
    if( right )
    {
       right->print( os );
    }
}

在那里，我留下了一个功能供您实现。您不需要实现私有(private)复制构造函数或赋值运算符。

同时执行 main() .请注意，无需在堆上(使用 new)实现 main 中的树。在堆栈上实现它。

main()将读入数字，将它们插入调用其 insert() 的树中方法然后在最后打印树，传递 std::cout作为参数。

您需要 #include <iostream> (不是 iostream.h)它会起作用。