在Java中为树构建一个基本的漂亮打印机

Question

我需要帮助来理解如何为任何给定的二叉树编写漂亮的打印机.

我知道第一步是预先订购以获取所有节点.

我知道在前序遍历期间,这就是所有美丽将被实现的地方.

只是不知道如何开始.我有一个预订序遍历功能,但我不知道从哪里开始修改它或我应该只是自己的功能.

没有代码,只是询问别人如何去做的想法.

如果我绝望的话可能是后来的代码:P

具体来说,它应该是这样的:

Answer 1

如果您知道树的深度,即等级的数量就可以计算出在最后一级节点的最大数量(这为n ²对于n =层数- 1,1元,如果你只有根).如果你进一步知道元素的宽度(例如,如果你有至多2位数字,每个元素的宽度为2),你可以计算出最后一个级别的宽度: ((number of elements - 1) * (element width + spacing) + element width).

实际上上段并不重要.您所需要的只是树的深度,即要显示的最大级别.但是,如果树是稀疏的,即不存在最后一级和上面的所有元素,则需要获取正在渲染的节点的位置,以便相应地调整该情况的缩进/间距.

在预订迭代中,您可以计算每个级别的元素之间的缩进和间距.缩进的公式为:2 ^{(最高级别 - 级别)} - 1和间距:2 ^{(最高级别 - 级别+ 1)} - 1 (级别为1)

例:

       1
   2       3
 4   5   6   7
8 9 A B C D E F

在该树中,级别数为4.最后一级的间距为1,而缩进为0.您将获得以下值:

• 1级:
  • indent = 7:(2 ^(4-1) - 1 = 2 ³ - 1 = 8 - 1 = 7)
  • 第一级,所以间距无关紧要
• 第2级:
  • indent = 3:(2 ^(4-2) - 1 = 2 ² - 1 = 4 - 1 = 3)
  • spacing = 7(2 ^(4-1) - 1 = 2 ³ - 1 = 8 - 1 = 7)
• 3级:
  • indent = 1:(2 ^(4-3) - 1 = 2 ¹ - 1 = 2 - 1 = 1)
  • spacing = 3(2 ^(4-2) - 1 = 2 ² - 1 = 4 - 1 = 3)
• 4级:
  • indent = 0:(2 ^(4-4) - 1 = 2 ⁰ - 1 = 1 - 1 = 0)
  • spacing = 1:(2 ^(4-3) - 1 = 2 ¹ - 1 = 2 - 1 = 1)

请注意,在最后一级,您将始终具有1*元素宽度的间距.因此,对于最大元素宽度为3(例如3位数字),您在最后一级的间距为3,以便获得较高级别的一些相当对齐.

编辑:对于漂亮的打印,您只需要计算缩进,width element * level因为级别将从零开始.然后,如果节点不是叶子,则在绘制子项后使用前面的开始paranthesis和关闭的paranthesis绘制它,如果它是叶子只是绘制它并且如果叶子丢失,则绘制双重paranthis.

因此你会得到这样的东西:

public void printSubtree( int indent, node ) {
  for( int i = 0; i < indent; ++i) {
    System.out.print(" ");
  }

  if( inner node) {
    System.out.println("(" + value);     
    printSubtree(indent + elem width, left child); //this is a recursive call, alternatively use the indent formula above if you don't use recursion
    printSubtree(indent + elem width, right child);

    //we have a new line so print the indent again
    for( int i = 0; i < indent; ++i) {
      System.out.print(" ");
    }
    System.out.println(")"); 
  } else if( not empty) {
    System.out.println(value);
  } else { //empty/non existing node
    System.out.println("()");
  }
}

Answer 2

这适用于所有输入并打印一条链接线,如下图所示

package com.sai.samples;

/**
 * @author Saiteja Tokala
 */
import java.util.ArrayList;
import java.util.List;


/**
 * Binary tree printer
 *
 * @author saiteja
 */
public class TreePrinter
{
    /** Node that can be printed */
    public interface PrintableNode
    {
        /** Get left child */
        PrintableNode getLeft();


        /** Get right child */
        PrintableNode getRight();


        /** Get text to be printed */
        String getText();
    }


    /**
     * Print a tree
     *
     * @param root
     *            tree root node
     */
    public static void print(PrintableNode root)
    {
        List<List<String>> lines = new ArrayList<List<String>>();

        List<PrintableNode> level = new ArrayList<PrintableNode>();
        List<PrintableNode> next = new ArrayList<PrintableNode>();

        level.add(root);
        int nn = 1;

        int widest = 0;

        while (nn != 0) {
            List<String> line = new ArrayList<String>();

            nn = 0;

            for (PrintableNode n : level) {
                if (n == null) {
                    line.add(null);

                    next.add(null);
                    next.add(null);
                } else {
                    String aa = n.getText();
                    line.add(aa);
                    if (aa.length() > widest) widest = aa.length();

                    next.add(n.getLeft());
                    next.add(n.getRight());

                    if (n.getLeft() != null) nn++;
                    if (n.getRight() != null) nn++;
                }
            }

            if (widest % 2 == 1) widest++;

            lines.add(line);

            List<PrintableNode> tmp = level;
            level = next;
            next = tmp;
            next.clear();
        }

        int perpiece = lines.get(lines.size() - 1).size() * (widest + 4);
        for (int i = 0; i < lines.size(); i++) {
            List<String> line = lines.get(i);
            int hpw = (int) Math.floor(perpiece / 2f) - 1;

            if (i > 0) {
                for (int j = 0; j < line.size(); j++) {

                    // split node
                    char c = ' ';
                    if (j % 2 == 1) {
                        if (line.get(j - 1) != null) {
                            c = (line.get(j) != null) ? '?' : '?';
                        } else {
                            if (j < line.size() && line.get(j) != null) c = '?';
                        }
                    }
                    System.out.print(c);

                    // lines and spaces
                    if (line.get(j) == null) {
                        for (int k = 0; k < perpiece - 1; k++) {
                            System.out.print(" ");
                        }
                    } else {

                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? " " : "?");
                        }
                        System.out.print(j % 2 == 0 ? "?" : "?");
                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? "?" : " ");
                        }
                    }
                }
                System.out.println();
            }

            // print line of numbers
            for (int j = 0; j < line.size(); j++) {

                String f = line.get(j);
                if (f == null) f = "";
                int gap1 = (int) Math.ceil(perpiece / 2f - f.length() / 2f);
                int gap2 = (int) Math.floor(perpiece / 2f - f.length() / 2f);

                // a number
                for (int k = 0; k < gap1; k++) {
                    System.out.print(" ");
                }
                System.out.print(f);
                for (int k = 0; k < gap2; k++) {
                    System.out.print(" ");
                }
            }
            System.out.println();

            perpiece /= 2;
        }
    }
}