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

2022-01-15 00:00:00 format binary-tree java order-of-execution

好的，我已经阅读了所有其他相关问题，但找不到对 java 有帮助的问题.我从解读其他语言的内容中得到了大致的想法；但我还没有弄清楚.

Okay, I have read through all the other related questions and cannot find one that helps with java. I get the general idea from deciphering what i can in other languages; but i am yet to figure it out.

问题:我想对排序进行级别排序(我使用递归)并以树的一般形状将其打印出来.

Problem: I would like to level sort (which i have working using recursion) and print it out in the general shape of a tree.

所以说我有这个:

    1 
   / 
  2   3
 /   / 
4   5   6

我的代码打印出这样的级别顺序:

My code prints out the level order like this:

1 2 3 4 5 6

我想这样打印出来:

1
2 3
4 5 6

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

Now before you give me a moral speech about doing my work... I have already finished my AP Comp Sci project and got curious about this when my teacher mentioned the Breadth First Search thing.

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

I don't know if it will help, but here is my code so far:

/**
  * 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 使用递归返回通过树时不断计数.

From what i can figure out, i will need to use the total height of the tree, and use a level counter... Only problem is my level counter keeps counting when my levelOrder uses recursion to go back through the tree.

对不起，如果这太多了，但一些提示会很好.:)

Sorry if this is to much, but some tips would be nice. :)

推荐答案

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

Here is the code, this question was asked to me in one of the interviews...

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>();

        }

    }

相关文章