在输出中显示二叉树的空子节点

Question

我有一个打印二叉树层次的方法：

template<class BTNode>
void breadthfirstByLevel(BTNode* node_ptr) {
 if (node_ptr == NULL)
 {
     return;
 }
    queue<BTNode *> q1;
    queue<BTNode *> q2;

    q1.push(node_ptr);

    while (!q1.empty() || !q2.empty()) {
        while (!q1.empty())
        {
            node_ptr = q1.front();
            q1.pop();
            cout << node_ptr->data() << " ";
            if (node_ptr->left() != NULL)
            {
                q2.push(node_ptr->left());
            }

            if (node_ptr->right() != NULL)
            {
                q2.push(node_ptr->right());
            }
        }
            cout << endl;
            while (!q2.empty())
            {
                node_ptr = q2.front();
                q2.pop();
                cout << node_ptr->data() << " ";

                if (node_ptr->left() != NULL)
                {
                    q1.push(node_ptr->left());
                }
                if (node_ptr->right() != NULL)
                {
                    q1.push(node_ptr->right());
                }
            }
        cout << endl;
    }
    }

我检查当前节点的子节点是否为空并将它们推入队列。我怎样才能在关卡输出中显示 "NULL" 而不是跳过它不打印任何内容？

Answer 1

你从队列中取出下一个节点的指针来打印数据。如果此节点有 children（即指向 child 的指针不为空），则将它们放入队列中。这意味着在队列中你永远不会有 nullptr。

您可以使用该算法的变体来解决此问题：您可以在缺少 child 的情况下将 nullptr 放入队列中。但是你必须确保当你从队列中获取指针时不要取消引用它们。

...
while (!q1.empty() || !q2.empty()) {
    while (!q1.empty())
    {
        node_ptr = q1.front();
        q1.pop();
        if (node_ptr==nullptr) {    // if nullptr was on queue
            cout << "<NULL> ";      // tell it 
        }
        else {                      // otherwise handle data and queue its children  
            cout << node_ptr->data() << " "; 
            q2.push(node_ptr->left());    // push even if it's nullptr
            q2.push(node_ptr->right());   //       "           "   
        }
    }
    ... // then same for q2
}

在输出中显示二叉树的空子节点

Displaying null children of binary tree in output

c++

tree

breadth-first-search