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

(Изначально это был реальный код - наскучил, так что это псевдокодей)

Answer 4

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

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

Вот так:

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

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

Answer 6

Следующая реализация использует 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();
    }
}

Answer 7

Мне очень нравится простота кода Анона; это элегантно. Но иногда элегантный код не всегда переводится в код, который интуитивно легко понять. Итак, вот моя попытка показать аналогичный подход, который требует 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);
}

Answer 8

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

}

Answer 9

Попробуйте, используя 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());
}

Answer 10

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

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

  //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's queue
        currentLevel.add(tmpRoot);

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

            //Print the next node on the level, add its childen to the next level's 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's stack. If there is no ponter, add a node with a null value to the next level's 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's stack. If there is no ponter, add a node with a null value to the next level's 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;
 }