如何垂直打印二叉搜索树类？

Question

我一直在学习如何使用C++中的链表编程二叉树搜索。所有功能都正常工作，我也理解了二叉树的工作原理，但我想要能够按照下面所示的方式打印树：头部在上方，所有节点在下方。

                                     [root or head]
                            [left]                    [right]

                      [left]      [right]       [left]       [right]

我正在使用控制台打印树形结构，因此您可以使用 'cout' 或 'printf'。我认为需要设置控制台的宽度，但我不确定如何开始。

谢谢，Y_Y

- Y_Y

---

Y：抽象类标签与你的问题有什么关系？ :) - Armen Tsirunyan

如果您想以这样对称的方式完成操作，就需要预先知道所需打印数据的深度和长度，以便正确对齐父节点。左对齐输出可能更容易实现。 - sbi

Answer 1

正如sbi所提到的，制作左对齐版本比居中对齐更容易。但是无论您选择哪种对齐方式，您的基本算法方法都应该是：

广度优先遍历树。使用以下算法来执行此操作：

1. 声明一个队列
2. 将根节点添加到队列中
3. 当队列包含更多节点时，执行4-6：
4. 出队一个节点
5. 打印该节点。在每次打印后， 这是2的幂次方减1次（从1开始），还要 打印一个换行符。
6. 将节点的子节点入队

（请参见http://www.cs.bu.edu/teaching/c/tree/breadth-first/）

为了打印居中对齐的树，请执行以下操作（仅适用于树是完整的情况。如果不完整，则最简单的方法是创建一个完整副本，在应该有节点的每个位置上都放置某种空节点）：

• 不要将内容打印到屏幕上，而是将每一行都存储在一个字符串数组中。
• 在此过程中，记录你打印的最长元素的字符长度。我们将其称为maxElemLen。
• 每当你打印一个元素时，在它之前和之后各打印一个制表符。
• 最后，在数组中的每一行中，将每个制表符替换为2^(nLines - lineNum)个制表符。
• 然后，将每个出现在制表符或换行符后面的制表符扩展为maxElemLen+1个空格，并将每个出现在任何其他位置（即，在打印的元素后面）的制表符扩展为(maxElemLen + 1 -（自上一个制表符以来经过的字符数）)个空格。
• 最后，按顺序打印数组的每一行。

- AlcubierreDrive

---

请注意，如果树是完整的，则“在每次打印2的幂减1次（从0开始），还要打印一个换行符”这部分才是正确的。 如果它不完整，则需要另一种方法来跟踪何时完成了一级别。 - AlcubierreDrive

@Jon：你为什么要重复第一部分？是不小心搞错了还是我漏掉了什么？ - sbi

@Jon：（这是我发表的评论。）从这里看，你的答案似乎有三个部分，其中前两个部分是相同的。 - sbi

@sbi 1) 哎呀 2) 哎呀。抱歉，阿尔门，感谢sbi。这里是凌晨3点18分，所以我可能读错了并打错了字。 - AlcubierreDrive

我不明白如何完成评论的第一部分中的第5步...？你能展示一下你的意思吗？ - Y_Y

Answer 2

这是打印二叉树的代码 - 以下代码按从左到右的方式打印二叉树。

private void printTree(Node nNode,int pos){
    if (nNode==null) {
        for(int i=0;i<pos;i++) System.out.print("\t");
        System.out.println("*");
        return;
    }
    printTree(nNode.right,pos+1);
    for(int i=0;i<pos;i++) System.out.print("\t");
    System.out.println(nNode.data);
    printTree(nNode.left,pos+1);
}

以下是上述方法的输出：

以上输出中的 '*' 表示空值。

- IsAs

---

那么我们要把头歪向一侧才能得到预期的输出吗？ - Thomas

Answer 3

@IsAs的解决方案。C++中逆时针旋转90度的树。建议仅在大小不超过2^4的树上使用。

print(root);
void BinarySearchTree::print(BinaryNode* n, int pos = 0){
    if (n==NULL) {
        for(int i = 0; i < pos; ++i)
            cout << "\t";
        cout << 'X' << endl;
        return;
    }
    print(n->right,pos+1);
    for(int i = 0; i < pos; i++)
        cout << "\t";
    cout << n->key << endl;
    print(n->left,pos+1);
}

- BajaBob