Hur man skriver ut ett binärt träddiagram

1. Introduktion

Utskrift är en mycket vanlig visualiseringsteknik för datastrukturer. Det kan dock vara svårt när det gäller träd på grund av deras hierarkiska natur.

I den här handledningen lär vi oss några trycktekniker för binära träd i Java.

2. Träddiagram

Trots begränsningarna med att rita med endast tecken över på konsolen finns det många olika diagramformer som representerar trädstrukturer. Att välja en av dem beror mest på trädets storlek och balans.

Låt oss ta en titt på några av de möjliga typerna av diagram som vi kan skriva ut:

Men vi kommer att förklara en praktisk som också är lättare att genomföra. Genom att ta hänsyn till riktningen där trädet växer kan vi kalla det ett horisontellt träd :

Eftersom det horisontella trädet alltid flyter i samma riktning som texten flyter har vi vissa fördelar med att välja ett horisontellt diagram framför andra:

  1. Vi kan också visualisera stora och obalanserade träd
  2. Längden på nodvärden påverkar inte visningsstrukturen
  3. Det är mycket lättare att genomföra

Därför går vi med det horisontella diagrammet och implementerar en enkel binär trädskrivarklass i nästa avsnitt.

3. Binary Tree Model

Först och främst bör vi modellera ett grundläggande binärt träd som vi kan göra med några få kodrader.

Låt oss definiera en enkel BinaryTreeModel- klass:

public class BinaryTreeModel { private Object value; private BinaryTreeModel left; private BinaryTreeModel right; public BinaryTreeModel(Object value) { this.value = value; } // standard getters and setters } 

4. Provtestdata

Innan vi börjar implementera vår binära trädskrivare måste vi skapa några exempeldata för att stegvis testa vår visualisering:

BinaryTreeModel root = new BinaryTreeModel("root"); BinaryTreeModel node1 = new BinaryTreeModel("node1"); BinaryTreeModel node2 = new BinaryTreeModel("node2"); root.setLeft(node1); root.setRight(node2); BinaryTreeModel node3 = new BinaryTreeModel("node3"); BinaryTreeModel node4 = new BinaryTreeModel("node4"); node1.setLeft(node3); node1.setRight(node4); node2.setLeft(new BinaryTreeModel("node5")); node2.setRight(new BinaryTreeModel("node6")); BinaryTreeModel node7 = new BinaryTreeModel("node7"); node3.setLeft(node7); node7.setLeft(new BinaryTreeModel("node8")); node7.setRight(new BinaryTreeModel("node9"));

5. Binär trädskrivare

Visst behöver vi en separat klass för att hålla vår BinaryTreeModel ren för principen om ett enda ansvar.

Nu kan vi använda besökarmönstret så att trädet hanterar hierarkin och vår skrivare bara hanterar utskriften. Men för den här handledningen håller vi dem tillsammans för att hålla det enkelt.

Således definierar vi en klass som heter BinaryTreePrinter och börjar implementera den.

5.1. Förbeställ traversal

Med tanke på vårt horisontella diagram, för att skriva ut det ordentligt, kan vi göra en enkel start genom att använda förbeställningskorsning .

Följaktligen, för att utföra förbeställningspassering, måste vi implementera en rekursiv metod som först besöker rotnoden, sedan vänster subtree och slutligen rätt subtree.

Låt oss definiera en metod för att korsa vårt träd:

public void traversePreOrder(StringBuilder sb, BinaryTreeModel node) { if (node != null) { sb.append(node.getValue()); sb.append("\n"); traversePreOrder(sb, node.getLeft()); traversePreOrder(sb, node.getRight()); } } 

Låt oss sedan definiera vår utskriftsmetod:

public void print(PrintStream os) { StringBuilder sb = new StringBuilder(); traversePreOrder(sb, this.tree); os.print(sb.toString()); } 

Således kan vi helt enkelt skriva ut vårt testträd:

new BinaryTreePrinter(root).print(System.out); 

Utgången kommer att vara listan över trädnoder i korsad ordning:

root node1 node3 node7 node8 node9 node4 node2 node5 node6 

5.2. Lägga till trädkantar

För att ställa in vårt diagram korrekt använder vi tre typer av tecken "├──", "└──" och "│" för att visualisera noder. De två första är för pekare och den sista är att fylla kanterna och ansluta pekarna.

Låt oss uppdatera vår traversePreOrder- metod, lägg till två parametrar som padding och pekare och använd tecknen respektive:

public void traversePreOrder(StringBuilder sb, String padding, String pointer, BinaryTreeModel node) { if (node != null) { sb.append(padding); sb.append(pointer); sb.append(node.getValue()); sb.append("\n"); StringBuilder paddingBuilder = new StringBuilder(padding); paddingBuilder.append("│ "); String paddingForBoth = paddingBuilder.toString(); String pointerForRight = "└──"; String pointerForLeft = (node.getRight() != null) ? "├──" : "└──"; traversePreOrder(sb, paddingForBoth, pointerForLeft, node.getLeft()); traversePreOrder(sb, paddingForBoth, pointerForRight, node.getRight()); } } 

Vi uppdaterar också utskriftsmetoden :

public void print(PrintStream os) { StringBuilder sb = new StringBuilder(); traversePreOrder(sb, "", "", this.tree); os.print(sb.toString()); } 

Så, låt oss testa vår BinaryTreePrinter igen:

Således, med alla stoppningar och pekare, har vårt diagram formats snyggt.

Vi har dock fortfarande några extra rader att bli av med:

När vi tittar över på diagrammet finns det fortfarande tecken på tre felplatser:

  1. Kolumnen med extra rader under rotnoden
  2. De extra raderna under rätt subtree
  3. De extra raderna under vänster subtree som inte har något rätt syskon

5.3. Olika implementeringar för rot- och barnnoder

För att fixa extra linjer kan vi dela upp vår traversmetod. Vi tillämpar ett beteende på rotnoden och ett annat för barnnoder.

Låt oss anpassa traversePreOrder för endast rotnoden:

public String traversePreOrder(BinaryTreeModel root) { if (root == null) { return ""; } StringBuilder sb = new StringBuilder(); sb.append(root.getValue()); String pointerRight = "└──"; String pointerLeft = (root.getRight() != null) ? "├──" : "└──"; traverseNodes(sb, "", pointerLeft, root.getLeft(), root.getRight() != null); traverseNodes(sb, "", pointerRight, root.getRight(), false); return sb.toString(); } 

Därefter skapar vi en annan metod för barnnoder som traverseNodes. En dditionally kommer vi lägga till en ny parameter hasRightSibling att genomföra ovanstående rader på rätt sätt:

public void traverseNodes(StringBuilder sb, String padding, String pointer, BinaryTreeModel node, boolean hasRightSibling) { if (node != null) { sb.append("\n"); sb.append(padding); sb.append(pointer); sb.append(node.getValue()); StringBuilder paddingBuilder = new StringBuilder(padding); if (hasRightSibling) { paddingBuilder.append("│ "); } else { paddingBuilder.append(" "); } String paddingForBoth = paddingBuilder.toString(); String pointerRight = "└──"; String pointerLeft = (node.getRight() != null) ? "├──" : "└──"; traverseNodes(sb, paddingForBoth, pointerLeft, node.getLeft(), node.getRight() != null); traverseNodes(sb, paddingForBoth, pointerRight, node.getRight(), false); } } 

Vi behöver också en liten förändring av vår utskriftsmetod :

public void print(PrintStream os) { os.print(traversePreOrder(tree)); } 

Slutligen har vårt diagram formats till en fin form med en ren utgång:

6. Sammanfattning

I den här artikeln lärde vi oss ett enkelt och praktiskt sätt att skriva ut ett binärt träd i Java .

Alla exemplen i den här artikeln och ytterligare testfall finns på GitHub.