在 Java 中以树结构打印值？

Question

我正在尝试编写此代码以在后面的树结构中打印给定的用户输入

      x
  x       x
x            x

但它不会那样输出。我得到的输出为

x
x
x

这是我编写的获取并打印的函数：

private void inOrder(Node n)
{
    if(n == null) // recursion ends when node is null
    return;
{
    inOrder(n.left);
    System.out.println(n.data);
    inOrder(n.right);
}
}

public void printInorder()
{
    inOrder(root);
}

Answer 1

您无法按所需方式打印。 In order 将打印 left、current 和 right。这些在树中处于不同级别。一旦你打印下一层，你就不能打印上面的当前层，因为它已经被打印了。

另外不要忘记 println 将打印该字符串并在其后换行。

要拥有精美的设计，您可能需要进行一些精美的工程以完美对齐它们，如下所示：

您需要一个队列供节点访问。

printNode(Node root, queueWithNodesAndStartAndEnd, start, end)
   print me at the middle of start and end
   put my left child in the queue with start = myStart and end = middle of my start and my end
   put my right child in the queue with start = middle of my start and my end and end  = my end
   pop (get and remove) first element from queue
   if not empty print popped node with start and end provided

我知道这是伪代码，但你应该能够实现它。

Answer 2

这种方法运行会遇到麻烦，因为对 println() 的任何调用都会阻止在一行上打印更多节点。使用 level order traversal/BFS 将使您能够调用 println() 仅当给定树级别上的所有节点都已打印时才移动到下一行。

更大的困难在于跟踪关卡中每个节点的水平位置。正确地执行此操作涉及考虑节点数据的深度、长度和任何空子节点。如果可以的话，考虑打印你的树，深度从左到右增加，类似于 unix 命令tree，而不是自上而下，这样可以简化算法。

这是自上而下打印的概念验证。间距公式来自 this excellent post 关于这个主题。我使用的策略是运行使用队列的 BFS，在每个级别的列表中存储节点（和空占位符）。一旦到达级别的末尾，间距将根据级别上的节点数确定，即 2^n-1，并打印。一个简化的假设是节点数据宽度为 1.

import java.util.*;
import static java.lang.System.out;

public class Main {
    static void printLevelOrder(Node root) {
        LinkedList<QItem> queue = new LinkedList<>();
        ArrayList<Node> level = new ArrayList<>();
        int depth = height(root);
        queue.add(new QItem(root, depth));

        for (;;) {
            QItem curr = queue.poll();

            if (curr.depth < depth) {
                depth = curr.depth;

                for (int i = (int)Math.pow(2, depth) - 1; i > 0; i--) { 
                    out.print(" ");
                }

                for (Node n : level) {
                    out.print(n == null ? " " : n.val);

                    for (int i = (int)Math.pow(2, depth + 1); i > 1; i--) {
                        out.print(" ");
                    }
                }

                out.println();
                level.clear();

                if (curr.depth <= 0) {
                    break;
                }
            }

            level.add(curr.node);

            if (curr.node == null) {
                queue.add(new QItem(null, depth - 1));
                queue.add(new QItem(null, depth - 1));
            }
            else {
                queue.add(new QItem(curr.node.left, depth - 1));
                queue.add(new QItem(curr.node.right, depth - 1));
            }
        }
    }

    static int height(Node root) {
        return root == null ? 0 : 1 + Math.max(
            height(root.left), height(root.right)
        );
    }

    public static void main(String[] args) {
        printLevelOrder(
            new Node<Integer>(
                1, 
                new Node<Integer>(
                    2, 
                    new Node<Integer>(
                        4, 
                        new Node<Integer>(7, null, null), 
                        new Node<Integer>(8, null, null)
                    ),
                    null
                ),
                new Node<Integer>(
                    3, 
                    new Node<Integer>(
                        5, 
                        new Node<Integer>(9, null, null),
                        null
                    ),
                    new Node<Integer>(
                        6,
                        null,
                        new Node<Character>('a', null, null)    
                    )
                )
            )
        );
    }
}

class Node<T> {
    Node left;
    Node right;
    T val;

    public Node(T val, Node left, Node right) {
        this.left = left;
        this.right = right;
        this.val = val;
    }
}

class QItem {
    Node node;
    int depth;

    public QItem(Node node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

输出：

       1
   2       3
 4       5   6
7 8     9     a

Try it!

Answer 3

这是我见过的最好的解决方案：

这是我利用它的代码片段。 class 将运行保持原样。

class Node {
    final int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }

    public void print() {
        print("", this, false);
    }

    private void print(String prefix, Node n, boolean isLeft) {
        if (n != null) {
            System.out.println(prefix + (isLeft ? "|-- " : "\-- ") + n.value);
            print(prefix + (isLeft ? "|   " : "    "), n.left, true);
            print(prefix + (isLeft ? "|   " : "    "), n.right, false);
        }
    }


}

class BinaryTree {
    Node root;

    private Node addRecursive(Node current, int value) {
        if (current == null) {
            return new Node(value);
        }

        if (value < current.value) {
            current.left = addRecursive(current.left, value);
        } else if (value > current.value) {
            current.right = addRecursive(current.right, value);
        } else {
            // value already exists
            return current;
        }

        return current;
    }

    public void add(int value) {
        root = addRecursive(root, value);
    }

    public void traverseInOrder(Node node) {
        if (node != null) {
            traverseInOrder(node.left);
            System.out.print(" " + node.value);
            traverseInOrder(node.right);
        }
    }


}

public class Main {

    public static void main(String[] args) {

        BinaryTree bt = new BinaryTree();
        bt.add(6);
        bt.add(4);
        bt.add(8);
        bt.add(3);
        bt.add(5);
        bt.add(7);
        bt.add(9);

        System.out.println("Print in order->");
        bt.traverseInOrder(bt.root);

        System.out.println("\n\nPrint Tree Structure");
        bt.root.print();
    }

}

Output example

在 Java 中以树结构打印值？

Printing values in a tree structure in Java?

java

tree

treenode