如何從後綴表達式中創建表達式樹？

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++編寫。使用構造函數和析構函數以及類方法。可能使您的數據成員保密。並且使用new而不是malloc，並且您的析構函數可能想要刪除（樹的子節點）。

你寫什麼是用C以外的其他你已經納入C++的iostream，並在它的老過時的非標準版本的最壞的特徵。

這看起來像一些學校鍛鍊。

我也不能看到你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); 
    } 
} 

在那裏，我留下了一個函數供您實現。您不需要實現私有拷貝構造函數或賦值操作符。

還執行main()。請注意，沒有必要在堆上實現樹（使用new）。在堆棧上實現它。

main()將讀入數字，將它們插入到調用其insert()方法的樹中，然後在最後打印樹，並將std::cout作爲參數傳遞。

你需要#include <iostream>（不iostream.h），它會工作。