C++ BST - 再帰なしでdisplay（）関数を呼び出す

Question

C++を使用してBSTを作成しました。表示関数は再帰的に呼び出し、プログラムは正常に動作します。

しかし、私は再帰なしでBSTを表示したいと思います。これをどのように達成するのですか？私はスタックを使用する必要があることを考えています

#include<iostream> 
#include<fstream> 
#include<time.h> 
using namespace std; 

struct Node { 
    int value; 
    Node * left; 
    Node * right; 
}; 

Node * root; 

class Tree{ 
public: 
    Tree() { 
     root = nullptr; 
    } 

    void _INSERT(Node * current, int data) { 
     if (current == nullptr) { 
      Node * temp = new Node; 
      temp->value = data; 
      temp->left = nullptr; 
      temp->right = nullptr; 
      root = temp; 
     } 

     else if (current->value == data) 
      return; 

     else if (current->value < data && current->right != nullptr) 
      _INSERT(current->right, data); 

     else if (current->value > data && current->left != nullptr) 
      _INSERT(current->left, data); 

     else if (current->value < data && current->right == nullptr) { 
      Node * temp = new Node; 
      temp->value = data; 
      temp->left = nullptr; 
      temp->right = nullptr; 
      current->right = temp; 
     } 

     else if (current->value > data && current->left == nullptr) { 
      Node * temp = new Node; 
      temp->value = data; 
      temp->left = nullptr; 
      temp->right = nullptr; 
      current->left = temp; 
     } 
    } 

    void _DISPLAY(Node * temp) { 
     if (temp != nullptr){ 
      _DISPLAY(temp->left); 
      cout << temp->value << endl; 
      _DISPLAY(temp->right); 
     } 
    } 

    ~Tree(){ 
     root = nullptr; 
    } 
}; 

int main() { 
    int value; 
    Tree obj; 

    ifstream inFile; 
    inFile.open("input.txt"); 

    ofstream outFile; 
    outFile.open("input.txt"); 

    srand(time(NULL)); 

    for (int i = 0; i < 100; i++) { 
     value = (rand() % 500) + 1; 
     outFile << value << endl; 
    } 

    for (int i = 0; i < 100; i++){ 
     inFile >> value; 
     obj._INSERT(root, value); 
    } 

    obj._DISPLAY(root); 


    system("pause"); 
    return 0; 
} 

：

は、ここに私のコードです。すべてのノードをプッシュし、一番左のノードがNULLの場合は、値をポップします。

おかげ

Answer 1

は、おそらく簡単に解決策があるかもしれませんが、これは、あなたが始めることができます。ツリー全体のスタックを準備するのではなく、子がすでにスタックにプッシュされているかどうかを示すフラグをスタックに格納するだけです。そうでなければ、スタック上で処理されているノードを含むノードを正しい順序で押してください。 yesの場合、出力値：

void _DISPLAY(Node * temp) { 
    std::stack<std::pair<Node*, bool>> stack; 

    stack.push(std::make_pair(temp, false)); 

    while (!stack.empty()) { 
     auto p = stack.top(); 
     stack.pop(); 
     if (p.first == nullptr) { 
      continue; 
     } 

     if (p.second) { 
      std::cout << p.first->value << "\n"; 
     } else { 
      stack.push(std::make_pair(p.first->right, false)); 
      stack.push(std::make_pair(p.first, true)); 
      stack.push(std::make_pair(p.first->left, false)); 
     } 
    } 
} 

LIVE