Подтвердить что ты не робот

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

Хорошо, я прочитал все другие связанные вопросы и не могу найти тот, который помогает с java. Я получаю общую идею от расшифровки того, что могу, на других языках; но я еще не понял это.

Проблема: я хотел бы выполнить сортировку (которая работает с рекурсией) и распечатать ее в общей форме дерева.

Так сказать, у меня есть это:

    1 
   / \
  2   3
 /   / \
4   5   6

Мой код печатает порядок уровня следующим образом:

1 2 3 4 5 6

Я хочу распечатать его следующим образом:

1
2 3
4 5 6

Теперь, прежде чем вы дадите мне моральную речь о выполнении моей работы... Я уже закончил проект AP Comp Sci, и мне стало любопытно, когда мой учитель упомянул о первой вещи поиска в Breadth.

Я не знаю, поможет ли это, но вот мой код:

/**
  * 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 использует рекурсию для возврата через дерево.

Извините, если это много, но некоторые советы будут приятными.:)

4b9b3361

ОТВЕТЫ

Ответ 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

Ответ 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)

Ответ 4

Просто подумал о том, чтобы поделиться предложением Anon в реальном Java-коде и исправить пару проблем KEY (например, для рекурсии не существует конечного условия, поэтому он никогда не перестает добавлять в стек, а не проверяет значение null в полученном массиве вы исключение нулевого указателя).

Также нет никакого исключения, как предлагает Эрик Хаузер, потому что он не изменяет цикл его цикла, он модифицирует новый.

Вот он:

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

Ответ 5

Ниже метод возвращает ArrayList из ArrayList, содержащий все уровни узлов по уровню: -

 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {

    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); 
    if(root == null) return result;
    Queue q1 = new LinkedList();
    Queue q2 = new LinkedList();

    ArrayList<Integer> list = new ArrayList<Integer>();
    q1.add(root);

    while(!q1.isEmpty() || !q2.isEmpty()){

        while(!q1.isEmpty()){
            TreeNode temp = (TreeNode)q1.poll();
            list.add(temp.val);
            if(temp.left != null) q2.add(temp.left);
            if(temp.right != null) q2.add(temp.right);
        }
        if(list.size() > 0)result.add(new ArrayList<Integer>(list));
        list.clear();
        while(!q2.isEmpty()){
            TreeNode temp = (TreeNode)q2.poll();
            list.add(temp.val);
            if(temp.left != null) q1.add(temp.left);
            if(temp.right != null) q1.add(temp.right);
        }
        if(list.size() > 0)result.add(new ArrayList<Integer>(list));
        list.clear();
    }
    return result;
}

Ответ 6

Ответ близок... Единственная проблема, с которой я мог убедиться, заключается в том, что если дерево не имеет node в определенной позиции, вы должны установить этот указатель в нуль. Что происходит, когда вы пытаетесь поместить нулевой указатель в список?

Вот что я сделал для недавнего задания. Он работает безупречно. Вы можете использовать его, начиная с любого корня.

  //Prints the tree in level order
  public void printTree(){
    printTree(root);
  }

 public void printTree(TreeNode tmpRoot){

    //If the first node isn't null....continue on
    if(tmpRoot != null){

        Queue<TreeNode> currentLevel = new LinkedList<TreeNode>(); //Queue that holds the nodes on the current level
        Queue<TreeNode> nextLevel = new LinkedList<TreeNode>();     //Queue the stores the nodes for the next level

        int treeHeight = height(tmpRoot);     //Stores the height of the current tree
        int levelTotal = 0;  //keeps track of the total levels printed so we don't  pass the height and print a billion "null"s

        //put the root on the currnt level queue
        currentLevel.add(tmpRoot);

        //while there is still another level to print and we haven't gone past the tree height
        while(!currentLevel.isEmpty()&& (levelTotal< treeHeight)){

            //Print the next node on the level, add its childen to the next level queue, and dequeue the node...do this until the current level has been printed
            while(!currentLevel.isEmpty()){

                //Print the current value
                System.out.print(currentLevel.peek().getValue()+" ");

                //If there is a left pointer, put the node on the nextLevel stack. If there is no ponter, add a node with a null value to the next level stack
                tmpRoot = currentLevel.peek().getLeft();
                if(tmpRoot != null)
                    nextLevel.add(tmpRoot);
                else
                    nextLevel.add(new TreeNode(null));

                //If there is a right pointer, put the node on the nextLevel stack. If there is no ponter, add a node with a null value to the next level stack
                tmpRoot = currentLevel.remove().getRight();
                if(tmpRoot != null)
                    nextLevel.add(tmpRoot);
                else
                    nextLevel.add(new TreeNode(null));

            }//end while(!currentLevel.isEmpty())

            //populate the currentLevel queue with items from the next level
            while(!nextLevel.isEmpty()){
                currentLevel.add(nextLevel.remove());
            }

            //Print a blank line to show height
            System.out.println("");

            //flag that we are working on the next level
            levelTotal++;

        }//end while(!currentLevel.isEmpty())

    }//end if(tmpRoot != null)

}//end method printTree

public int height(){
    return height(getRoot());
}

public int height(TreeNode tmpRoot){

    if (tmpRoot == null)
        return 0;
    int leftHeight = height(tmpRoot.getLeft());
    int rightHeight = height(tmpRoot.getRight());

    if(leftHeight >= rightHeight)
        return leftHeight + 1;
    else
        return rightHeight + 1;
 }

Ответ 7

Мне очень нравится простота кода Anon; его элегантный. Но иногда элегантный код не всегда переводится в код, который интуитивно легко понять. Итак, здесь моя попытка показать аналогичный подход, который требует Log (n) большего пространства, но должен более естественно читаться тем, кто больше всего знаком с поиском глубины (спускается по длине дерева).

Следующий фрагмент кода устанавливает узлы, принадлежащие определенному уровню в списке, и упорядочивает этот список в списке, который содержит все уровни дерева. Следовательно, List<List<BinaryNode<T>>>, который вы увидите ниже. Остальное должно быть достаточно объяснительным.

public static final <T extends Comparable<T>> void printTreeInLevelOrder(
        BinaryTree<T> tree) {
    BinaryNode<T> root = tree.getRoot();
    List<List<BinaryNode<T>>> levels = new ArrayList<List<BinaryNode<T>>>();
    addNodesToLevels(root, levels, 0);
    for(List<BinaryNode<T>> level: levels){
        for(BinaryNode<T> node: level){
            System.out.print(node+ " ");
        }
        System.out.println();
    }
}

private static final <T extends Comparable<T>> void addNodesToLevels(
        BinaryNode<T> node, List<List<BinaryNode<T>>> levels, int level) {
    if(null == node){
        return;
    }

    List<BinaryNode<T>> levelNodes;
    if(levels.size() == level){
        levelNodes = new ArrayList<BinaryNode<T>>();
        levels.add(level, levelNodes);
    }
    else{
        levelNodes = levels.get(level);
    }

    levelNodes.add(node);
    addNodesToLevels(node.getLeftChild(), levels, level+1);
    addNodesToLevels(node.getRightChild(), levels, level+1);
}

Ответ 8

В следующей реализации используется 2 очереди. Использование ListBlokcingQueue здесь, но любая очередь будет работать.

import java.util.concurrent.*;

public class Test5 {

    public class Tree {
        private String value;
        private Tree left;
        private Tree right;

        public Tree(String value) {
            this.value = value;
        }

        public void setLeft(Tree t) {
            this.left = t;
        }

        public void setRight(Tree t) {
            this.right = t;
        }

        public Tree getLeft() {
            return this.left;
        }

        public Tree getRight() {
            return this.right;
        }

        public String getValue() {
            return this.value;
        }
    }

    Tree tree = null;

    public void setTree(Tree t) {
        this.tree = t;
    }

    public void printTree() {
        LinkedBlockingQueue<Tree> q = new LinkedBlockingQueue<Tree>();
        q.add(this.tree);
        while (true) {
            LinkedBlockingQueue<Tree> subQueue = new LinkedBlockingQueue<Tree>();
            while (!q.isEmpty()) {
                Tree aTree = q.remove();
                System.out.print(aTree.getValue() + ", ");
                if (aTree.getLeft() != null) {
                    subQueue.add(aTree.getLeft());
                }
                if (aTree.getRight() != null) {
                    subQueue.add(aTree.getRight());
                }
            }
            System.out.println("");
            if (subQueue.isEmpty()) {
                return;
            } else {
                q = subQueue;
            }
        }
    }

    public void testPrint() {
        Tree a = new Tree("A");
        a.setLeft(new Tree("B"));
        a.setRight(new Tree("C"));
        a.getLeft().setLeft(new Tree("D"));
        a.getLeft().setRight(new Tree("E"));
        a.getRight().setLeft(new Tree("F"));
        a.getRight().setRight(new Tree("G"));
        setTree(a);
        printTree();
    }

    public static void main(String args[]) {
        Test5 test5 = new Test5();
        test5.testPrint();
    }
}

Ответ 9

public class PrintATreeLevelByLevel {
public static class Node{
    int data;
    public Node left;
    public Node right;

    public Node(int data){
        this.data = data;
        this.left = null;
        this.right = null;

    }
}

public void printATreeLevelByLevel(Node n){
    Queue<Node> queue =  new LinkedList<Node>();
    queue.add(n);
    int node = 1; //because at root
    int child = 0; //initialize it with 0 
    while(queue.size() != 0){
        Node n1 = queue.remove();
        node--;
        System.err.print(n1.data +" ");

        if(n1.left !=null){
            queue.add(n1.left);
            child ++;
        }
        if(n1.right != null){
            queue.add(n1.right);
            child ++;
        }
        if( node == 0){
            System.err.println();
            node = child ;
            child = 0;
        }

    }


}

public static void main(String[]args){
    PrintATreeLevelByLevel obj = new PrintATreeLevelByLevel();
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    Node node6 = new Node(6);
    Node node7 = new Node(7);
    Node node8 = new Node(8);

    node4.left = node2;
    node4.right = node6;
    node2.left = node1;
//  node2.right = node3;
    node6.left = node5;
    node6.right = node7;
    node1.left = node8;
    obj.printATreeLevelByLevel(node4);
}

}

Ответ 10

Попробуйте это, используя 2 очереди для отслеживания уровней.

public static void printByLevel(Node root){
    LinkedList<Node> curLevel = new LinkedList<Node>();
    LinkedList<Node> nextLevel = curLevel;

    StringBuilder sb = new StringBuilder();
    curLevel.add(root);
    sb.append(root.data + "\n");

    while(nextLevel.size() > 0){
        nextLevel = new LinkedList<Node>();
        for (int i = 0; i < curLevel.size(); i++){
            Node cur = curLevel.get(i);
            if (cur.left != null) {
                nextLevel.add(cur.left);
                sb.append(cur.left.data + " ");
            }
            if (cur.right != null) {
                nextLevel.add(cur.right);
                sb.append(cur.right.data + " ");
            }
        }
        if (nextLevel.size() > 0) {
            sb.append("\n");
            curLevel = nextLevel;

        } 
    }
    System.out.println(sb.toString());
}

Ответ 11

public void printAllLevels(BNode node, int h){
    int i;
    for(i=1;i<=h;i++){
        printLevel(node,i);
        System.out.println();
    }
}

public void printLevel(BNode node, int level){
    if (node==null)
        return;
    if (level==1)
        System.out.print(node.value + " ");
        else if (level>1){
            printLevel(node.left, level-1);
            printLevel(node.right, level-1);
        }
}

public int height(BNode node) {
    if (node == null) {
        return 0;
    } else {
        return 1 + Math.max(height(node.left),
                height(node.right));
    }
}

Прежде всего, я не люблю брать кредит на это решение. Это модификация какой-то функции, и я приспособил ее для обеспечения решения.

Я использую здесь 3 функции.

  • Сначала я вычисляю высоту дерева.
  • Затем у меня есть функция для печати определенного уровня дерева.
  • Используя высоту дерева и функцию для печати уровня дерева, я пересекаю дерево и повторяю и печатаю все уровни дерева с помощью моей третьей функции.

Надеюсь, это поможет.

EDIT: временная сложность этого решения для печати всего node в обход уровня не будет O (n). Причина в том, что каждый раз, когда вы опускаетесь на уровень, вы снова и снова будете посещать те же узлы.

Если вы ищете решение O (n), я думаю, что использование Queues будет лучшим вариантом.

Ответ 12

Я думаю, мы можем добиться этого, используя одну очередь. Это реализация Java, использующая только одну очередь. На основе BFS...

public void BFSPrint()
{
    Queue<Node> q = new LinkedList<Node>();
    q.offer(root);
    BFSPrint(q);
}

private void BFSPrint(Queue<Node> q)
{
    if(q.isEmpty())
        return;
    int qLen = q.size(),i=0;
     /*limiting it to q size when it is passed, 
       this will make it print in next lines. if we use iterator instead, 
       we will again have same output as question, because iterator 
       will end only q empties*/
    while(i<qLen) 
        {
        Node current = q.remove();
        System.out.print(current.data+" ");
        if(current.left!=null)
            q.offer(current.left);
        if(current.right!=null)
            q.offer(current.right);
        i++;
    }
    System.out.println();
    BFSPrint(q);

}

Ответ 13

верхние решения только печатают дочерние элементы каждого из node вместе. Это неверно в соответствии с описанием.

Нам нужны все узлы одного уровня вместе в одной строке.

1) Применить BFS

2) Храните высоты узлов на карте, которая будет удерживать уровень - список узлов.

3) Перейдите по карте и распечатайте результаты.

Смотрите код Java ниже:

public void printByLevel(Node root){
    Queue<Node> q = new LinkedBlockingQueue<Node>();
    root.visited = true;
    root.height=1;
    q.add(root);
    //Node height - list of nodes with same level
    Map<Integer, List<Node>> buckets = new HashMap<Integer, List<Node>>();
    addToBuckets(buckets, root);
    while (!q.isEmpty()){
        Node r = q.poll();

        if (r.adjacent!=null)
        for (Node n : r.adjacent){
            if (!n.visited){
                n.height = r.height+1; //adjust new height
                addToBuckets(buckets, n);
                n.visited = true;
                q.add(n);
            }
        }
    }

    //iterate over buckets and print each list
    printMap(buckets);

}

//helper method that adds to Buckets list
private void addToBuckets(Map<Integer, List<Node>> buckets, Node n){
        List<Node> currlist = buckets.get(n.height);
    if (currlist==null)
    {
        List<Node> list = new ArrayList<Node>();
        list.add(n);
        buckets.put(n.height, list);
    }
    else{
        currlist.add(n);
    }

}

//prints the Map
private void printMap(Map<Integer, List<Node>> buckets){
    for (Entry<Integer, List<Node>> e : buckets.entrySet()){
        for (Node n : e.getValue()){
            System.out.print(n.value + " ");
        }
    System.out.println();
}

Ответ 14

Простейший способ сделать это без использования какой-либо информации уровня, неявно предполагаемой в каждом Node. Просто добавьте 'null' node после каждого уровня. проверьте этот нуль node, чтобы узнать, когда печатать новую строку:

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;}
}

Ответ 15

Это работает для меня. Передайте список массивов с rootnode при вызове printLevel.

void printLevel(ArrayList<Node> n){
    ArrayList<Node> next = new ArrayList<Node>();       
    for (Node t: n) {
        System.out.print(t.value+" "); 
        if (t.left!= null)
            next.add(t.left);
        if (t.right!=null)
            next.add(t.right);
    }
    System.out.println();
    if (next.size()!=0)
        printLevel(next);
}

Ответ 16

Печать двоичного дерева в порядке уровня с одной очередью:

public void printBFSWithQueue() {
    java.util.LinkedList<Node> ll = new LinkedList<>();
    ll.addLast(root);
    ll.addLast(null);
    Node in = null;
    StringBuilder sb = new StringBuilder();
    while(!ll.isEmpty()) {
        if(ll.peekFirst() == null) {
            if(ll.size() == 1) {
                break;
            }
            ll.removeFirst();
            System.out.println(sb);
            sb = new StringBuilder();
            ll.addLast(null);
            continue;
        }
        in = ll.pollFirst();
        sb.append(in.v).append(" ");
        if(in.left != null) {
            ll.addLast(in.left);
        }
        if(in.right != null) {
            ll.addLast(in.right);
        }
    }
}

Ответ 17

void printTreePerLevel(Node root)
    {
        Queue<Node> q= new LinkedList<Node>();
        q.add(root);
        int currentlevel=1;
        int nextlevel=0;
        List<Integer> values= new ArrayList<Integer>();
        while(!q.isEmpty())
        {
            Node node = q.remove();
            currentlevel--;
            values.add(node.value);
            if(node.left != null)
            {
                q.add(node.left);
                nextlevel++;
            }
            if(node.right != null)
            {
                q.add(node.right);
                nextlevel++;
            }
            if(currentlevel==0)
            {
                for(Integer i:values)
                {
                    System.out.print(i + ",");
                }
                System.out.println();
                values.clear();
                currentlevel=nextlevel;
                nextlevel=0;
            }


        }

    }

Ответ 18

A - Решение

Я написал прямое решение здесь. Если вам нужен подробный ответ, демонстрационный код и пояснения, вы можете пропустить и проверить остальные заголовки ответа;

public static <T> void printLevelOrder(TreeNode<T> root) {
    System.out.println("Tree;");
    System.out.println("*****");

    // null check
    if(root == null) {
        System.out.printf(" Empty\n");
        return;
    }

    MyQueue<TreeNode<T>> queue = new MyQueue<>();
    queue.enqueue(root);

    while(!queue.isEmpty()) {
        handleLevel(queue);
    }
}

// process each level
private static <T> void handleLevel(MyQueue<TreeNode<T>> queue) {
    int size = queue.size();

    for(int i = 0; i < size; i++) {
        TreeNode<T> temp = queue.dequeue();
        System.out.printf("%s ", temp.data);
        queue.enqueue(temp.left);
        queue.enqueue(temp.right);
    }

    System.out.printf("\n");
}

B - Пояснение

Чтобы печатать дерево в порядке уровня, вы должны обрабатывать каждый уровень с помощью простой реализации очереди. В моей демонстрации я написал очень минималистский простой класс очереди, называемый MyQueue.

Открытый метод printLevelOrder будет принимать экземпляр объекта TreeNode<T> root как параметр, который обозначает корень дерева. Частный метод handleLevel принимает экземпляр MyQueue в качестве параметра.

На каждом уровне метод handleLevel убирает очередь в очереди столько же, сколько размер очереди. Ограничение уровня контролируется, так как этот процесс выполняется только с размером очереди, который в точности равен элементам этого уровня, а затем выводит на выход новый символ строки.

C - класс TreeNode

public class TreeNode<T> {

    T data;
    TreeNode<T> left;
    TreeNode<T> right;

    public TreeNode(T data) {
        this.data = data;;
    }

}

D - класс MyQueue: простая реализация очереди

public class MyQueue<T> {

    private static class Node<T> {

        T data;
        Node next;

        public Node(T data) {
            this(data, null);
        }

        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }

    }

    private Node head;
    private Node tail;
    private int size;

    public MyQueue() {
        head = null;
        tail = null;
    }

    public int size() {
        return size;
    }

    public void enqueue(T data) {
        if(data == null)
            return;

        if(head == null)
            head = tail = new Node(data);
        else {
            tail.next = new Node(data);
            tail = tail.next;
        }

        size++;
    }

    public T dequeue() {

        if(tail != null) {
            T temp = (T) head.data;
            head = head.next;

            size--;

            return temp;
        }

        return null;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void printQueue() {
        System.out.println("Queue: ");
        if(head == null)
            return;
        else {
            Node<T> temp = head;
            while(temp != null) {
                System.out.printf("%s ", temp.data);
                temp = temp.next;
            }
        }
        System.out.printf("%n");
    }
}

E - ДЕМО: печать дерева в порядке уровня

public class LevelOrderPrintDemo {

    public static void main(String[] args) {
        // root level
        TreeNode<Integer> root = new TreeNode<>(1);

        // level 1
        root.left           = new TreeNode<>(2);
        root.right          = new TreeNode<>(3);

        // level 2
        root.left.left      = new TreeNode<>(4);

        root.right.left     = new TreeNode<>(5);
        root.right.right    = new TreeNode<>(6);

        /*
         *      1      root
         *     / \
         *    2   3    level-1
         *   /   / \
         *  4   5   6  level-2
         */

        printLevelOrder(root);
    }

    public static <T> void printLevelOrder(TreeNode<T> root) {
        System.out.println("Tree;");
        System.out.println("*****");

        // null check
        if(root == null) {
            System.out.printf(" Empty\n");
            return;
        }

        MyQueue<TreeNode<T>> queue = new MyQueue<>();
        queue.enqueue(root);

        while(!queue.isEmpty()) {
            handleLevel(queue);
        }
    }

    // process each level
    private static <T> void handleLevel(MyQueue<TreeNode<T>> queue) {
        int size = queue.size();

        for(int i = 0; i < size; i++) {
            TreeNode<T> temp = queue.dequeue();
            System.out.printf("%s ", temp.data);
            queue.enqueue(temp.left);
            queue.enqueue(temp.right);
        }

        System.out.printf("\n");
    }

}

F - ввод образца

    1      // root
   / \
  2   3    // level-1
 /   / \
4   5   6  // level-2

G - Образец вывода

Tree;
*****
1 
2 3 
4 5 6

Ответ 19

Реализация Python

# Function to  print level order traversal of tree
def printLevelOrder(root):
    h = height(root)
    for i in range(1, h+1):
        printGivenLevel(root, i)


# Print nodes at a given level
def printGivenLevel(root , level):
    if root is None:
        return
    if level == 1:
        print "%d" %(root.data),
    elif level > 1 :
        printGivenLevel(root.left , level-1)
        printGivenLevel(root.right , level-1)


""" Compute the height of a tree--the number of nodes
    along the longest path from the root node down to
    the farthest leaf node
"""
def height(node):
    if node is None:
        return 0
    else :
        # Compute the height of each subtree 
        lheight = height(node.left)
        rheight = height(node.right)

        #Use the larger one
        if lheight > rheight :
            return lheight+1
        else:
            return rheight+1

Ответ 20

        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;
                }
            }
        }

Ответ 21

Ого. Так много ответов. Для чего это стоит, мое решение выглядит следующим образом:

Мы знаем нормальный способ обхода порядка: для каждого node сначала посещается node, а затем его дочерние узлы помещаются в очередь FIFO. Нам нужно следить за каждым уровнем, так что все узлы на этом уровне печатаются в одной строке без новой строки.

Поэтому я, естественно, думал о том, что он представляет очередь очередей. Основная очередь содержит внутренние очереди для каждого уровня. Каждая внутренняя очередь содержит все узлы на одном уровне в порядке FIFO. Когда мы выгружаем внутреннюю очередь, мы перебираем ее, добавляем все ее дочерние элементы в новую очередь и добавляем эту очередь в основную очередь.

public static void printByLevel(Node root) {

    Queue<Node> firstQ = new LinkedList<>();
    firstQ.add(root);

    Queue<Queue<Node>> mainQ = new LinkedList<>();
    mainQ.add(firstQ);

    while (!mainQ.isEmpty()) {
        Queue<Node> levelQ = mainQ.remove();
        Queue<Node> nextLevelQ = new LinkedList<>();
        for (Node x : levelQ) {
            System.out.print(x.key + " ");
            if (x.left != null)    nextLevelQ.add(x.left);
            if (x.right != null)   nextLevelQ.add(x.right);
        }
        if (!nextLevelQ.isEmpty()) mainQ.add(nextLevelQ);
        System.out.println();
    }
}

Ответ 22

public void printAtLevel(int i){
    printAtLevel(root,i);
}
private void printAtLevel(BTNode<T> n,int i){
    if(n != null){
        sop(n.data);
    } else {
        printAtLevel(n.left,i-1);
        printAtLevel(n.right,i-1);
    }
}
private void printAtLevel(BTNode<T> n,int i){
    if(n != null){
        sop(n.data);
        printAtLevel(n.left,i-1);
        printAtLevel(n.right,i-1);
    }
}