Java 使用特定格式的级别顺序打印二叉树

format java binary-tree order-of-execution

2022-09-02 22:56:24

好的，我已经通读了所有其他相关问题，但找不到一个有助于Java的问题。我从破译其他语言中所能获得的总体想法;但我还没有弄清楚。

问题：我想对排序（我使用递归工作）并以树的一般形状打印出来。

所以说我有这个：

我的代码打印出水平顺序，如下所示：

1 2 3 4 5 6

我想像这样打印出来：

1
2 3
4 5 6

现在，在你给我一个关于做我的工作的道德演讲之前......我已经完成了我的AP Comp Sci项目，当我的老师提到广度优先搜索时，我对此感到好奇。

我不知道它是否会有所帮助，但这是我到目前为止的代码：

/**
  * Calls the levelOrder helper method and prints out in levelOrder.
  */
 public void levelOrder()
 {
  q = new QueueList();
  treeHeight = height();
  levelOrder(myRoot, q, myLevel);
 }

 /**
  * Helper method that uses recursion to print out the tree in 
  * levelOrder
  */
 private void levelOrder(TreeNode root, QueueList q, int curLev)
 {
  System.out.print(curLev);
  if(root == null)
  {
   return;
  }

  if(q.isEmpty())
  {
   System.out.println(root.getValue());
  }
  else
  {
   System.out.print((String)q.dequeue()+", ");
  }

  if(root.getLeft() != null)
  {
   q.enqueue(root.getLeft().getValue());
   System.out.println();
  }
  if(root.getRight() != null)
  {
   q.enqueue(root.getRight().getValue());
   System.out.println();
   curLev++;
  }

  levelOrder(root.getLeft(),q, curLev);
  levelOrder(root.getRight(),q, curLev);
 }

从我能弄清楚的，我需要使用树的总高度，并使用水平计数器...唯一的问题是，当我的 levelOrder 使用递归返回树时，我的关卡计数器会一直在计数。

抱歉，如果这是很多，但一些提示会很好。:)

答案 1

这是代码，这个问题是在一次采访中问我的......

public void printTree(TreeNode tmpRoot) {

        Queue<TreeNode> currentLevel = new LinkedList<TreeNode>();
        Queue<TreeNode> nextLevel = new LinkedList<TreeNode>();

        currentLevel.add(tmpRoot);

        while (!currentLevel.isEmpty()) {
            Iterator<TreeNode> iter = currentLevel.iterator();
            while (iter.hasNext()) {
                TreeNode currentNode = iter.next();
                if (currentNode.left != null) {
                    nextLevel.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    nextLevel.add(currentNode.right);
                }
                System.out.print(currentNode.value + " ");
            }
            System.out.println();
            currentLevel = nextLevel;
            nextLevel = new LinkedList<TreeNode>();

        }

    }

答案 2

这是最简单的解决方案

public void byLevel(Node root){
     Queue<Node> level  = new LinkedList<>();
     level.add(root);
     while(!level.isEmpty()){
         Node node = level.poll();
         System.out.print(node.item + " ");
         if(node.leftChild!= null)
         level.add(node.leftChild);
         if(node.rightChild!= null)
         level.add(node.rightChild);
     }
}

https://github.com/camluca/Samples/blob/master/Tree.java 在我的github中，您可以在类树中找到其他有用的函数，例如：

显示树

****......................................................****
                            42
            25                              65                              
    12              37              43              87              
9      13      30      --      --      --      --      99      
****......................................................****
Inorder traversal
9 12 13 25 30 37 42 43 65 87 99  
Preorder traversal
42 25 12 9 13 37 30 65 43 87 99  
Postorder traversal
9 13 12 30 37 25 43 99 87 65 42  
By Level
42 25 65 12 37 43 87 9 13 30 99