如何仅使用 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)，它再次打印 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);
}

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

How to print all nodes in Binary Search Tree only use iostream library?

c++

tree

binary-tree

tree-traversal