如何仅使用 iostream 库打印二叉搜索树中的所有节点？

Question

我想打印树中的所有节点（首先打印低级别的节点，对于具有相同输出级别的节点，首先打印具有较小值的节点）例如：输入

预期输出：10 6 20 1 8 18 21 7 25。 我试着这样编码

void print_Nodes(Node *root)
{
    if(root == nullptr) return;
        cout << root->value << " ";
    if(root->left!=nullptr){
        cout << root->left->value << " ";
        if(root->right!=nullptr){
            cout << root->right->value << " ";
        }
    }
    print_Nodes(root->right);
    print_Nodes(root->left);
}

但输出是：10 6 20 6 1 8 1 8 7 7 20 18 21 18 21 25。 你能指导我如何解决这个问题吗？

Answer 1

您正在打印root->left->value，然后调用print_Nodes(root->left)which 再次打印root->value（root前一个在哪里root->left）。这就是为什么它们都出现两次的原因。

此外，您正在执行深度优先遍历，而您实际上想要进行广度优先遍历。要在继续下一个级别之前遍历一个级别上的所有节点，您需要一个额外的数据结构来记住节点，以便您以后可以回到它们并继续向下。

#include <iostream>
#include <queue>
struct Node {
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int value) : value(value) {}
    int value;
};

void bft(Node* root) {
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* current = q.front();
        q.pop();
        std::cout << current->value << " ";
        if (current->left) q.push(current->left);
        if (current->right) q.push(current->right);    
    }
}

int main() {
    Node root(10);
    Node n6(6);
    Node n20(20);
    Node n1(1);
    Node n8(8);
    Node n18(18);
    Node n21(21);
    Node n7(7);
    Node n25(25);

    root.left = &n6;
    root.right = &n20;
    n6.left = &n1;
    n6.right = &n8;
    n20.left = &n18;
    n20.right = &n21;
    n8.left = &n7;
    n21.right = &n25;

    bft(&root);
}