Imprimarea unui arbore nivel cu nivel (Revizuirea codului, Java, Coadă, Căutare Pe Lățime Mai Întâi)

Aneesh K a intrebat.

Am scris un program pentru a imprima un arbore binar nivel cu nivel pe diferite linii, așa cum ar arăta arborele dacă ar fi desenat pe hârtie.

Am făcut o traversare BFS și apoi am procedat la imprimarea arborelui presupunând că este un arbore binar complet:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTreeLevelWise {

/**
 * This class represents the individual nodes of the binary tree
 * Each node has a left, right pointer of type Node
 * and Value to hold the value
 * @author Aneesh
 *
 */
class Node {
    Node left;

    Node right;

    int value;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node value=" + value + "";
    }

}

/**
 * Driver function to test the code
 * @param args
 */
public static void main(String[] args) {
    new BinaryTreeLevelWise().run();
}

/**
     * This function inserts an element into the binary tree
     * @param node
     * @param value
     */
    public void insert(Node node, int value) {
        if (value < node.value) {
            if (node.left != null) {
                insert(node.left, value);
            } else {
                System.out.println("  Inserted " + value + " to left of "
                        + node.value);
                node.left = new Node(value);
            }
        } else if (value > node.value) {
            if (node.right != null) {
                insert(node.right, value);
            } else {
                System.out.println("  Inserted " + value + " to right of "
                        + node.value);
                node.right = new Node(value);
            }
        }
    }

/**
 * Builds the tree and executes some functions
 */
public void run() {
    // build the simple tree from chapter 11.
    Node root = new Node(5);
    System.out.println("Binary Tree Example");
    System.out.println("Building tree with root value " + root.value);
    insert(root, 1);
    insert(root, 8);
    insert(root,-2);
    insert(root, 6);
    insert(root, 3);
    insert(root, 9);
    insert(root,-3);
    insert(root,-1);
    /*System.out.println("Traversing tree in order");
    printInOrder(root);
    System.out.println("Traversing tree front-to-back from location 7");
    printFrontToBack(root, 7);*/

    System.out.println("*************
Printing the tree levelWise");

    printLevelWise(root);
}

/**
 * This functions uses a list of nodes and prints them level wise assuming a complete
 * binary tree.
 * Every level will have have 2^L elements where L is the level, root is level L=0 
 * @param Root of the tree of type {@link Node}
 */
public void printLevelWise(Node root) {
    // TODO Auto-generated method stub
    Queue<Node> nodes= new LinkedList<>(); 

    List<Node> listOfNodes = new ArrayList<Node>();
    //add root to the list
    traverseLevels(root, listOfNodes,nodes);
    //printing in a straight line
    //System.out.println("nodes are "+listOfNodes);
    // printing level wise
    int count = 0,level=0;

    while (count < listOfNodes.size()){
        int printLen= (int) Math.pow(2, level++);

        for (int i=count; i < printLen -1 && i < listOfNodes.size();++i){
            System.out.print(listOfNodes.get(i).value+" ");
        }
            System.out.println();
            count = printLen-1;
    }
}

/**
 * This function traverses the tree and puts all the nodes level wise into a list
 * @param root
 * @param listOfNodes
 * @param nodes 
 */
private void traverseLevels(Node root, List<Node> listOfNodes, Queue<Node> nodes) {
    // TODO Auto-generated method stub
    if (root!=null){

        nodes.add(root);
        listOfNodes.add(root);
        while(!nodes.isEmpty()){

            //standard BFS
            root= nodes.poll();
            if (root.left!=null) {
                listOfNodes.add(root.left);
                nodes.add(root.left);
            }
            if (root.right!=null) {
                listOfNodes.add(root.right);
                nodes.add(root.right);
            }
        }

    }
}
}

Ieșire:

5
1 8
-2 3 6 9
-3 -1

Este aceasta metoda corectă? Există vreo metodă mai eficientă?

1 răspunsuri
janos

Este aceasta metoda corectă?

Nu.Încercați să obțineți numărul de nivel dintr-o listă plată de noduri și o anumită putere a lui 2.Acest lucru va funcționa numai cu un arbore de căutare binar echilibrat complet,și nu ați menționat astfel de cerințe să fie prezente.Pentru a vedea un exemplu prost, inserați -4 la exemplul dvs. existent.Arborele rezultat:

            5 
        1      8 
     -2   3   6 9 
   -3 -1
-4

Rezultatul programului dvs:

5 
1 8 
-2 3 6 9 
-3 -1 -4

După cum vedeți, -4 este tipărit la un nivel greșit.Acest lucru se datorează faptului că atunci când aplatizați arborele la o listă de noduri,pierdeți informații importante despre structură,și nu puteți obține nivelurile folosind matematica.

Pentru a remedia acest lucru, nu puteți aplatiza arborele la o listă,aveți nevoie de o listă de liste.

Există o metodă mai eficientă?

Există mai multe alte probleme de eficiență și de stil de codare în cele existente.Să începem de acolo și să ne îndreptăm spre o soluție îmbunătățită și corectă.

Încapsulare

Scopul încapsulării este de a ascunde detaliile de implementare. printLevelWise este un utilizator al metodei traverseLevels metodei, dar știe prea multe despre modul în care aceasta funcționează:

Queue<Node> nodes= new LinkedList<>(); 
List<Node> listOfNodes = new ArrayList<Node>();
traverseLevels(root, listOfNodes,nodes);

printLevelWise este trecerea unui Queue către metodă,dar printLevelWise însăși nu folosește această coadă.Faptul că traverseLevels utilizează o coadă este un detaliu de implementare,printLevelWise nu ar trebui să știe despre el.Îndepărtați acest parametru, inițializați-l în interiorul traverseLevels, , unde este folosit de fapt.

void Metoda cu parametru de ieșire

Adresa traverseLevels este practic o metodă void metodă cu un parametru de ieșire (out-parameter) List<Node> pe care îl completează.În multe cazuri practice, inclusiv în programul dvs. în cauză, o opțiune mai bună este ca metoda să returneze parametrul de ieșire ca rezultat.

Mutarea logicii comune la un nivel superior

În acest cod:

listOfNodes.add(root);
while(!nodes.isEmpty()){
    root= nodes.poll();
    if (root.left!=null) {
        listOfNodes.add(root.left);
        nodes.add(root.left);
    }
    if (root.right!=null) {
        listOfNodes.add(root.right);
        nodes.add(root.right);
    }
}

Se adaugă rădăcina la listOfNodes, și apoi adăugați ramurile.Adică, adăugați la listă în 3 locuri.Ați putea refactoriza acest lucru pentru a adăuga la listă într-un singur loc, imediat după interogare:

while (!nodes.isEmpty()) {
    root = nodes.poll();
    listOfNodes.add(root);
    if (root.left != null) {
        nodes.add(root.left);
    }
    if (root.right != null) {
        nodes.add(root.right);
    }
}

Acest lucru este mai simplu, mai scurt, iar rezultatul este echivalent.

Comentarii greșite

Acestea sunt comentarii proaste:

// TODO Auto-generated method stub
Queue<Node> nodes= new LinkedList<>(); 

//add root to the list
traverseLevels(root, listOfNodes,nodes);

Comentariile generate automat ar trebui să fie eliminate în momentul în care începeți să adăugați implementarea.

Al doilea comentariu este o minciună flagrantă. următoarea linie nu are nimic de-a face cu adăugarea rădăcinii la listă.

Păstrarea nivelurilor

Pentru a păstra nivelurile,aveți nevoie de o gândire diferită în traverseLevelsIată un mod de a rezolva acest lucru:

  • În fiecare ciclu de !nodes.isEmpty()
    • Copiați și consumați toate nodurile aflate în prezent în coada de așteptare
    • Adăugați la coada de așteptare copiii nuli ai nodurilor.
    • În acest fel, fiecare ciclu va corespunde unui nivel.

Implementare:

private List<List<Node>> traverseLevels(Node root) {
    if (root == null) {
        return Collections.emptyList();
    }
    List<List<Node>> levels = new LinkedList<>();

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

    while (!nodes.isEmpty()) {
        List<Node> level = new ArrayList<>(nodes.size());
        levels.add(level);

        for (Node node : new ArrayList<>(nodes)) {
            level.add(node);
            if (node.left != null) {
                nodes.add(node.left);
            }
            if (node.right != null) {
                nodes.add(node.right);
            }
            nodes.poll();
        }
    }
    return levels;
}

Utilizând programul rescris traverseLevels,se va implementa printLevelWise devine foarte simplă:

public void printLevelWise(Node root) {
    List<List<Node>> levels = traverseLevels(root);

    for (List<Node> level : levels) {
        for (Node node : level) {
            System.out.print(node.value + " ");
        }
        System.out.println();
    }
}

Și produce rezultatul corect:

5 
1 8 
-2 3 6 9 
-3 -1 
-4

Comentarii

  • Wow. Mulțumesc mult. Mă gândeam la abordarea List of Lists, dar nu am reușit să înțeleg partea de abordare „consumă toate nodurile din coadă”. Îmi pare foarte rău pentru comentariul „add root the list”, lucram la o altă implementare și am uitat să o înlătur când am scris traverseLevels.-  > Por Aneesh K.