Wyświetlanie drzewa na konsoli

W poprzednich postach utworzyliśmy strukturę drzewa (Ogólna implementacja) oraz poznaliśmy metody umożliwiające przejście przez wszystkie jego węzły w określonej kolejności (Trawersowanie drzewa). Kolejnym krokiem będzie przedstawienie struktury drzewa w jakiejś czytelnej formie na ekranie komputera. Wykorzystamy do tego celu konsolę. Jest kilka sposobów prezentacji drzewa, najczęściej wykorzystuje się zapis, gdzie poszczególne elementy są w odpowiednich kolumnach lub zapis z nawiasami, które symbolizują dzieci danego elementu. Przyjrzyjmy się naszemu drzewu jeszcze raz w formie graficznej.

W postaci konsolowej możemy zapisać jego strukturę tak:

Adam
        Ewa
                Jurek
                Max
                Iza
        Jarek
                Iwona
        Marta
                Rafał
                Ola

lub tak:

Adam(Ewa(Jurek, Max, Iza), Jarek(Iwona), Marta(Rafał, Ola))

W obu przypadkach odczytujemy: Adam jest korzeniem i ma trójkę "dzieci" (Ewa, Jarek oraz Marta), Ewa ma trójkę "dzieci" (Jurek, Max oraz Iza), Jarek ma jedno "dziecko" (Iwona), Marta ma dwójkę "dzieci" (Rafał i Ola).

Jak utworzyć metody, które wyświetlą nam odpowiednią kolejność elementów oraz zapewnią formatowanie? Przyjrzyjmy się najpierw kolejności elementów....tak dokładnie to jest kolejność preorder. Wystarczy teraz tylko odpowiednio dokonać formatowania oraz wyświetlić zawartość elementów. Pierwszy sposób wymaga dopisania metody, która będzie dla danego elementu zwracać jego poziom (odległość od korzenia drzewa). Napiszemy w klasie Tree<T> prostą metodę rekurencyjną getLevel():

public int getLevel(Node<T> n) {
 if (n == root) return 0;
 else return 1 + getLevel(n.getParent());
}

Dodatkowo dodamy do naszej klasy pole output typu StringBuilder (taki dynamiczny String). W tej zmiennej będziemy przechowywać widok naszego drzewa. Metoda, która przygotuje nam ten widok działa bardzo podobnie jak metoda trawersująca typu preorder. Jedyne modyfikacje to pobieranie poziomu węzła i dodawanie odpowiedniej ilości znaków tabulacji (symulacja kolumn).

private void makeTreeStringOutline(Node<T> n) {
 for(int i=0; i < getLevel(n); i++) output.append("\t");
 output.append(n + "\n");
 Node<T> temp = n.getLeftMostChild();
 while (temp != null) {
  makeString(temp);
  temp = temp.getRightSibling();
 }
}

Drugi sposób prezentacji drzewa zostanie zrealizowany bardzo podobnie. Opieramy się na trawersowaniu preorder oraz wstawiamy w odpowiednie miejsca znaki nawiasów (otwierające i zamykające).

private void makeTreeStringBrackets(Node<T> n) {
 output.append(n);
 Node<T> temp = n.getLeftMostChild();
 if( temp != null) output.append("(");
 while (temp != null) {
  makeStringPar(temp);
  temp = temp.getRightSibling();
  if (temp != null) output.append(", ");
  else output.append(")");
 }
}

Wywołanie tych metod możemy umieścić w dowolnej metodzie. Najlepiej będzie wykorzystać do tego celu metodę toString(). Przesłonięta wersja tej metody poniżej (prezentacja drzewa możliwa jest na dwa sposoby, jeden jest ujęty w komentarz).

public String toString() {
 output = new StringBuilder();

 makeTreeStringOutline(root); // wersja "drzewiasta"
 //makeTreeStringBrackets(root); // wersja z nawiasami

 return output.toString();
}

Pozostaje tylko sprawdzenie czy nasz kod działa. Utwórzmy drzewo i wyświetlmy je na konsoli.

Node<String> korzen = new Node<String>(null, "Adam");
Node<String> n1 = korzen.addChild("Ewa");
Node<String> n2 = korzen.addChild("Jarek");
Node<String> n3 = korzen.addChild("Marta");

n1.addChild("Jurek");
n1.addChild("Max");
n1.addChild("Iza");

n2.addChild("Iwona");

n3.addChild("Rafał");
n3.addChild("Ola");

Tree<String> drzewo = new Tree<String>(korzen);

System.out.println (drzewo);

Efekt działania:

Adam
        Ewa
                Jurek
                Max
                Iza
        Jarek
                Iwona
        Marta
                Rafał
                Ola

Poniżej cały kod drzewa wraz ze wszystkimi klasami i metodami.

import java.util.*;

/**
 * Klasa Node<T> - węzeł drzewa
 * @author kodatnik.blogspot.com
 */
class Node<T> {
 private T data;
 private Node<T> parent;
 private LinkedList<Node<T>> children;

 public Node() {
  parent = null;
  children = new LinkedList<Node<T>>();
 }

 public Node(Node<T> parent) {
  this();
  this.parent = parent;
 }

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

 public Node<T> getParent(){
  return parent;
 }

 public void setParent(Node<T> parent) {
  this.parent = parent;
 }

 public T getData() {
  return data;
 }

 public void setData(T data) {
  this.data = data;
 }

 public int getDegree() {
  return children.size();
 }

 public boolean isLeaf(){
  return children.isEmpty();
 }

 public Node<T> addChild(Node<T> child) {
  child.setParent(this);
  children.add(child);
  return child;
 }

 public Node<T> addChild(T data) {
  Node<T> child = new Node<T>(this, data);
  children.add(child);
  return child;
 }

 public Node<T> getChild(int i){
  return children.get(i);
 }

 public Node<T> removeChild(int i) {
  return children.remove(i);
 }

 public void removeChildren() {
  children.clear();
 }

 public LinkedList<Node<T>> getChildren() {
  return children;
 }

 public Node<T> getLeftMostChild() {
  if (children.isEmpty()) return null;
  return children.get(0);
 }

 public Node<T> getRightSibling() {
  if (parent != null) {
   LinkedList<Node<T>> parentsChildren = parent.getChildren();
   int pos = parentsChildren.indexOf(this);
   if (pos < (parentsChildren.size()-1))
    return parentsChildren.get(pos+1);
  }
  return null;
 }

 public String toString() {
  return data.toString();
 }
}

/**
 * Klasa Tree<T> - drzewo
 * @author kodatnik.blogspot.com
 */
class Tree<T> {

 private Node<T> root;
 private StringBuilder output;

 public Tree() {
  root = null;
 }

 public Tree(Node<T> root) {
  this.root = root;
 }

 public Node<T> getRoot() {
  return root;
 }

 public void preOrder() {
  preOrder(root);
 }

 public void postOrder() {
  postOrder(root);
 }

 public void inOrder() {
  inOrder(root);
 }

// metoda wyświetla węzły w kolejności preorder
public void preOrder(Node<T> n) {
 //najpierw korzeń
 System.out.print(n + " ");
 // potem lewe skrajne poddrzewo, a później prawe
 Node<T> temp = n.getLeftMostChild();
 while (temp != null) {
  preOrder(temp);
  temp = temp.getRightSibling();
 }
}

// metoda wyświetla węzły w kolejności postorder
public void postOrder(Node<T> n) {
 // najpierw lewe skrajne poddrzewo, potem prawe
 Node<T> temp = n.getLeftMostChild();
 while (temp != null) {
  postOrder(temp);
  temp = temp.getRightSibling();
 }
 // na końcu korzeń
 System.out.print(n + " ");
}

// metoda wyświetla węzły w kolejności inorder
public void inOrder(Node<T> n) {
 if (n.isLeaf())
  System.out.print(n + " ");
 else {
  // najpierw lewe skrajne poddrzewo
  Node<T> temp = n.getLeftMostChild();
  inOrder(temp);
  // potem korzeń
  System.out.print(n + " ");
  // potem prawe
  temp = temp.getRightSibling();
  while (temp != null) {
   inOrder(temp);
   temp = temp.getRightSibling();
  }
 }
}

 // metoda zwraca poziom węzła
 public int getLevel(Node<T> n) {
  if (n == root) return 0;
  else return 1 + getLevel(n.getParent());
 }

 private void makeTreeStringOutline(Node<T> n) {
  for(int i=0; i < getLevel(n); i++) output.append("\t");
  output.append(n + "\n");
  Node<T> temp = n.getLeftMostChild();
  while (temp != null) {
   makeTreeStringOutline(temp);
   temp = temp.getRightSibling();
  }
 }

 private void makeTreeStringBrackets(Node<T> n) {
  output.append(n);
  Node<T> temp = n.getLeftMostChild();
  if( temp != null) output.append("(");
  while (temp != null) {
   makeTreeStringBrackets(temp);
   temp = temp.getRightSibling();
   if (temp != null) output.append(", ");
   else output.append(")");
  }
 }

 public String toString() {
  output = new StringBuilder();

  makeTreeStringOutline(root); // reprezentacja drzewiasta
  //makeTreeStringBrackets(root); // reprezentacja z nawiasami

  return output.toString();
 }
}

public class NaszeDrzewo {
 public static void main(String args[]) {

  // tworzymy węzeł będący korzeniem
  Node<String> korzen = new Node<String>(null, "Adam");

  // dodajemy do niego kolejne węzły
  Node<String> n1 = korzen.addChild("Ewa");
  Node<String> n2 = korzen.addChild("Jarek");
  Node<String> n3 = korzen.addChild("Marta");

  n1.addChild("Jurek");
  n1.addChild("Max");
  n1.addChild("Iza");

  n2.addChild("Iwona");

  n3.addChild("Rafał");
  n3.addChild("Ola");

  // tworzymy drzewo i wskazujemy, który węzeł jest korzeniem
  Tree<String> drzewo = new Tree<String>(korzen);

  System.out.println(drzewo);
 }
}