C++ BST - 调用 display() 函数而不递归

Question

我使用 C++ 创建了一个 BST。 display函数递归调用，程序运行正常

但是我想在没有递归的情况下显示 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;
}

我在想我需要使用 Stack。如果我压入所有节点并且当最左边的节点为 NULL 时，则弹出值。

谢谢

Answer 1

可能有更简单的解决方案，但这可以帮助您入门。无需为整棵树准备堆栈，只需在堆栈上存储一个标志，显示是否已将子元素压入堆栈。如果没有，只需将包括正在处理的节点在内的节点按正确顺序压入堆栈即可。如果是，则输出值：

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

C++ BST - 调用 display() 函数而不递归

C++ BST - Call display() function without recursion

c++

tree

recursion

binary-search-tree