Java Печать бинарного дерева с использованием уровня порядка в определенном формате - PullRequest
Новая
       45

Java Печать бинарного дерева с использованием уровня порядка в определенном формате

17 голосов
/ 11 февраля 2010

Хорошо, я прочитал все другие связанные вопросы и не могу найти тот, который помогает с 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 использует рекурсию для возврата по дереву.

Извините, если это слишком много, но некоторые советы были бы хорошими.:)

Ответы [ 22 ]

0 голосов
/ 17 ноября 2017 
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        Node leftMost = null;
        while (!queue.isEmpty()) {
            Node node = queue.poll();

            if (leftMost == node) {
                System.out.println();
                leftMost = null;
            }

            System.out.print(node.getData() + " ");

            Node left = node.getLeft();
            if (left != null) {
                queue.add(left);
                if (leftMost == null) {
                    leftMost = left;
                }
            }

            Node right = node.getRight();
            if (right != null) {
                queue.add(right);

                if (leftMost == null) {
                    leftMost = right;
                }
            }
        }
0 голосов
/ 27 марта 2014

Самый простой способ сделать это без использования информации об уровне, неявно предполагаемой в каждом узле. Просто добавьте «нулевой» узел после каждого уровня. проверьте, чтобы этот нулевой узел знал, когда печатать новую строку: 

public class BST{
     private Node<T> head;
     BST(){}
     public void setHead(Node<T> val){head = val;}

     public static void printBinaryTreebyLevels(Node<T> head){
         if(head == null) return;
         Queue<Node<T>> q = new LinkedList<>();//assuming you have type inference (JDK 7)
         q.add(head);
         q.add(null);
         while(q.size() > 0){
              Node n = q.poll();
              if(n == null){
                   System.out.println();
                   q.add(null);
                   n = q.poll();
              }
              System.out.print(n.value+" ");
              if(n.left != null) q.add(n.left);
              if(n.right != null) q.add(n.right);
         }
     }
     public static void main(String[] args){
           BST b = new BST();
           c = buildListedList().getHead();//assume we have access to this for the sake of the example
           b.setHead(c);
           printBinaryTreeByLevels();
           return;
     }
}
class Node<T extends Number>{
     public Node left, right;
     public T value;
     Node(T val){value = val;}
}
Страница:
...