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

Question

好的,我已经阅读了所有其他相关问题,但找不到有助于java的问题.我从破译其他语言的内容中得到了一般性的想法; 但我还没搞清楚.

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

所以说我有这个:

    1 
   / \
  2   3
 /   / \
4   5   6

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

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使用递归返回树.

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

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

        }

    }

Answer 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中你可以在类Tree中找到其他有用的函数:

显示树

****......................................................****
                            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  

Answer 3

我将如何做到这一点:

levelOrder(List<TreeNode> n) {
    List<TreeNode> next = new List<TreeNode>();
    foreach(TreeNode t : n) {
        print(t);
        next.Add(t.left);
        next.Add(t.right);
    }
    println();
    levelOrder(next);
}

(最初是真正的代码 - 中途变得无聊,所以它是psueodocodey)

Answer 4

只是想在真正的java代码中分享Anon的建议并修复一些KEY问题(比如没有递归的结束条件,所以它永远不会停止添加到堆栈,而不是在接收到的数组中检查null会得到一个null指针异常).

Eric Hauser建议也不例外,因为它不会修改集合的循环,它正在修改一个新集合.

在这里:

public void levelOrder(List<TreeNode> n) {
    List<TreeNode> next = new ArrayList<TreeNode>();
    for (TreeNode t : n) {
        if (t != null) {
            System.out.print(t.getValue());
            next.add(t.getLeftChild());
            next.add(t.getRightChild());
        }
    }
    System.out.println();
    if(next.size() > 0)levelOrder(next);
}