如何打印二叉树图（垂直）并确保不正确打印相当不平衡的树？

Question

我正在尝试编写打印垂直二叉树图的功能，

我已经编写了正确的广度优先搜索算法，它将 BFS 有序树遍历输出为整数向量。代码如下：

void bst::printlist(Node* node)
{
    std::queue<Node*> travQueue;
    std::vector<int> result;

    travQueue.push(node);

    while (!travQueue.empty())
    {
        result.push_back(node->val);
        if (node->prev != NULL)
        {
            travQueue.push(node->prev);
        }
        if (node->next != NULL)
        {
            travQueue.push(node->next);
        }
        travQueue.pop();
        node = travQueue.front();
    }
}

但是，我完全不知道如何将结果向量转换为准确表示所有缺失节点的向量，这些节点在相当不平衡的树中作为间隙存在，

对于这个例子，当它需要包含每个缺失节点的信息一直到底层时，向量将只用从左到右的顺序填充整数。在编写实际代码以使用 ASCII 字符打印树时，如果我能够确定在何处绘制节点以及在何处不绘制节点，我将需要此信息——因此，我计划在这些间隙处包含虚拟值以区分。

有人对解决这个问题的方法有什么建议吗？

谢谢！

Answer 1

这是一个很好的答案，感谢@NicoSchertler：

“您可以将 prev 和 next 推送到 travQueue，即使它们是 nullptr。当您在迭代中到达 nullptr 时，将虚拟值添加到结果中，并将另外两个 nullptr 添加到 travQueue 以用于不存在的子项。”

这是我的代码：

std::queue<Node*> travQueue;
    std::vector<int> result;

    int h = treeheight(root) + 1;
   
    travQueue.push(node);

    for (int i = 0; i < pow(2, h) - 1; i++)
    {   
        node = travQueue.front();
        if (node != nullptr)
        {
            if (node->prev != nullptr)
            {
                travQueue.push(node->prev);
            } else
            {
                travQueue.push(nullptr);
            }
            if (node->next != nullptr)
            {
                travQueue.push(node->next);
            } else
            {
                travQueue.push(nullptr);
            }
        } else
        {
            travQueue.push(nullptr);
            travQueue.push(nullptr);
        }
        if (node != nullptr)
        {
            result.push_back(node->val);
        } else
        {
            result.push_back(-1);
        }
        travQueue.pop();
    }
    return result;

如何打印二叉树图（垂直）并确保不正确打印相当不平衡的树？

How to print a Binary Tree diagram (vertical) and ensure fairly unbalanced trees are not improperly printed?

c++

binary-tree

breadth-first-search