为什么我的打印功能之一会删除节点？

Question

好的，所以我的二叉树程序有一个打印函数，它以广度优先的方式打印所有内容。当我调用它时，它按我期望的顺序打印，但是它也删除了除节点之外的所有节点并给我留下了一棵空树。

void BST::breadth(Node *& cur_root)
{
    if (cur_root != NULL) {
        cout << cur_root->m_value;
        if (cur_root->m_left != NULL) { 
            myqueue.push(cur_root->m_left);
        }
        if (cur_root->m_right != NULL) {
            myqueue.push(cur_root->m_right);
        }
        if (!myqueue.empty()) {
            cout << ", "; 
            cur_root = myqueue.front();
            myqueue.pop();
            breadth(cur_root);
        } else {
            cout << "}" << endl;
        }
    }
}

我假设从 myqueue 中弹出节点可能是问题所在，但是当我使用我的正常打印功能（按顺序遍历）时我没有遇到这个问题。

void BST::print(Node *& cur_root)
{
    if (cur_root != NULL) {
        print(cur_root->m_left);
        myqueue.push(cur_root);
        print(cur_root->m_right);
    }
    int sizecompare = myqueue.size();
    if (size() == sizecompare) {
        while (!myqueue.empty()) {
            cout << myqueue.front()->m_value;
            myqueue.pop();
            if (!myqueue.empty()) {
                cout << ", ";
            }
        }
        cout << "}" << endl;
    }
}

它们都使用相同的节点队列，所以我不明白为什么它们在弹出时会有不同的行为。那么 pop 函数是罪魁祸首吗？如果是这样，为什么它只发生在一个函数上？有什么办法可以解决这个问题，这样我的节点就不会被破坏吗？

Answer 1

void BST::breadth(Node *& cur_root)

接受对指针的引用。

cur_root = myqueue.front();

将其更改为子节点之一。你刚刚覆盖了它。

Answer 2

因为您通过引用而不是值传递 cur_root。当你的 breadth 函数 returns 时，你的 cur_root 指向其他东西（树的末尾）。

你也可以避免递归：

void BST::breadth(Node* root)
{
    std::queue<Node*> myqueue;
    myqueue.push_back(root);
    bool first = true;

    cout << "{";

    while (myqueue.empty() == false) {
        cout << (first ? "" : ",");
        first = false;

        Node* current = myqueue.front();
        myqueue.pop();

        cout << current->m_value;

        if (current->left) {
            myqueue.push(current->left);
        }
        if (current->right) {
            myqueue.push(current->right);
        }
    }

    cout << "}" << endl;
}

为什么我的打印功能之一会删除节点？

Why is one of my print functions deleting nodes?

c++

binary-tree