Drzewo - ogólna implementacja

Struktury drzewiaste są dość często wykorzystywane w informatyce. Java nie posiada żadnej gotowej klasy do obsługi drzew. Dzisiaj prosta implementacja dowolnego drzewa ogólnego (każdy element drzewa może posiadać nieograniczoną liczbę potomków). Samo drzewo to struktura elementów, węzłów (ang. node) pozostających w zależności hierarchicznej tak jak na poniższym diagramie.

Szczególnym elementem drzewa jest korzeń (ang. root) czyli element nie posiadający rodzica (elementu nadrzędnego). Dodatkowe pojęcia związane z drzewem to liść (element nie posiadający dzieci), stopień węzła (liczba potomków węzła), elementy siostrzane węzła (elementy mające tego samego rodzica co dany węzeł), wysokość węzła (długość najdłuższej ścieżki od danego węzła do liścia), poziom węzła (długość ścieżki od korzenia do danego węzła). Patrząc na powyższy diagram możemy ustalić, że każdy węzeł:

• przechowuje jakieś dane,
• posiada referencję do węzła będącego jego rodzicem (w przypadku korzenia będzie to wartość null),
• ma listę swoich dzieci (czyli listę referencji do węzłów będących jego potomkami).

Wykorzystując typy generyczne (pisałem o nich wcześniej: Typy generyczne) oraz listę powiązaną (też wspominałem: LinkedList przykład wykorzystania) jesteśmy w stanie stosunkowo łatwo zbudować klasę odpowiadającą pojedynczemu węzłowi:

class Node<T> {
 // dane przechowywane w węźle
 private T data; 
 // referencja do rodzica
 private Node<T> parent; 
 // lista dzieci
 private LinkedList<Node<T>> children; 
}

Dodajemy potrzebne konstruktory, domyślny (węzeł bez rodzica i z pustą listą dzieci), jednoparametrowy (węzeł z ustawionym rodzicem) i dwuparametrowy (węzeł z rodzicem i danymi):

public Node() {
 // brak referencji do rodzica
 parent = null; 
 // tworzymy pustą listę dzieci
 children = new LinkedList<Node<T>>(); 
}

public Node(Node<T> parent) {
 // wywołujemy konstruktor domyślny
 this(); 
 // ustawiamy rodzica
 this.parent = parent; 
} 

public Node(Node<T> parent, T data) {
 // wywołujemy konstruktor jednoparametrowy
 this(parent); 
 // ustawiamy dane
 this.data = data; 
} 

Dodajmy również do klasy podstawowe metody dostępowe i modyfikujące dla danych i rodzica:

public Node<T> getParent(){
 // zwracamy referencję do rodzica
 return parent; 
}

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

public T getData() {
 // zwracamy przechowywane dane
 return data; 
}

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

Stopień węzła, czyli liczbę jego potomków możemy łatwo określić zwracając rozmiar listy przechowującej referencję dzieci.

public int getDegree() {
 // zwracamy rozmiar listy przechowującej potomków węzła
 return children.size();
}

Tak samo sprawdzenie czy dany węzeł jest liściem (ang. leaf). Jeśli jego lista dzieci jest pusta, jest liściem.

public boolean isLeaf(){
 // jeśli lista dzieci jest pusta zwracamy true (węzeł jest liściem)
 return children.isEmpty();
}

Do węzła możemy dodawać dzieci. Jeden sposób to dodanie do listy potomków referencji węzła przekazanego jako parametr. Musimy pamiętać o ustawieniu w "dziecku" naszego "ojcostwa" (węzeł będący na liście naszych dzieci musi wiedzieć, że jesteśmy jego rodzicem).

public Node<T> addChild(Node<T> child) {
 // ustawiamy w dziecku rodzica (wskazujemy na nas)
 child.setParent(this);
 // dodajemy dziecko do listy naszych dzieci
 children.add(child);
 // zwracamy dziecko
 return child;
}

Drugi sposób wygodniejszy podczas tworzenia struktury drzewa to dodatnie do węzła dziecka z określonymi danymi. Nasza metoda utworzy na podstawie przekazanych danych nowy węzeł oraz doda go do listy jego dzieci.

public Node<T> addChild(T data) {
 //tworzymy nowy węzeł (ustawiamy od razu rodzica i dane)
 Node<T> child = new Node<T>(this, data); 
 // dopisujemy węzeł do listy naszych dzieci
 children.add(child);
 // zwracamy dziecko
 return child;
}

Dodatkowe operacje związane z dziećmi to pobranie i-tego dziecka z listy, usunięcia konkretnego dziecka, oraz usunięcie wszystkich dzieci węzła. Wykorzystamy metody dostępne w klasie LinkedList.

public Node<T> getChild(int i){
 // zwracamy referencję do i-tego dziecka (metoda get(int) z klasy LinkedList)
 return children.get(i);
}

public Node<T> removeChild(int i) {
 // usuwamy i-te dziecko (metoda remove(int) z klasy LinkedList)
 return children.remove(i);
}

public void removeChildren() {
 // usuwamy wszystkie nasze dzieci, czyścimy listę(metoda clear() z klasy LinkedList)
 children.clear();
}

Możemy również napisać metodę dostępową zwracającą listę dzieci węzła.

public LinkedList<Node<T>> getChildren() {
 // zwracamy referencję do listy naszych dzieci
 return children;
}

Pozostają nam jeszcze dwie metody, które przydadzą się do implementacji sposobów trawersowania drzewa. Pierwsza z nich zwróci nam najbardziej wysunięte w lewo dziecko węzła (czyli pierwszego potomka z listy o ile tylko taki istnieje).

public Node<T> getLeftMostChild() {
 // jeśli nie mamy dzieci zwrócimy null
 if (children.isEmpty()) return null;
 // w przciwnym wypadku pierwsze dziecko z listy naszych dzieci
 return children.get(0);
}

Druga zwraca prawy element siostrzany (o ile istnieje) węzła.

public Node<T> getRightSibling() {
 // jeśli nie jesteśmy korzeniem
 if (parent != null) {
  // pobieramy listę dzieci naszego rodzica
  LinkedList<Node<T>> parentsChildren = parent.getChildren();
  // szukamy się na tej liście
  int pos = parentsChildren.indexOf(this);
  // sprawdzamy czy są jeszcze jakieś dzieci za nami
  if (pos < (parentsChildren.size()-1))
   // jesli tak zwracamy kolejne dziecko
   return parentsChildren.get(pos+1);
 }
 // zwracamy null jak węzeł jest korzeniem, albo nie ma już elementu siostrzanego po prawej
 return null;
}

Ostatnią częścią naszej klasy będzie przesłonięcie metody toString(). Zwrócimy po prostu dane przechowywane w węźle.

public String toString() {
 // zwracamy dane w formie łańcucha tekstowego
 return data.toString();
}

Poniżej cała gotowa klasa Node<T> opisująca węzeł naszego drzewa (komentarze zostały pominięte).

/**
 * 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();
 }
}

Ostatnią czynnością będzie zbudowanie konkretnego drzewa. Sam proces sprowadza się do utworzenia odpowiednich węzłów, połączenie ich w strukturę hierarchiczną oraz wskazania węzła będącego korzeniem. Nasza klasa będzie posiadała tylko jedno pole, referencję do węzła będącego korzeniem. Dwa konstruktory, domyślny puste drzewo i jednoparametrowy ustawiający referencję do korzenia.

/**
 * Klasa Tree<T> - drzewo
 * @author kodatnik.blogspot.com
 */
class Tree<T> {
 // referencja do węzła będącego korzeniem
 private Node<T> root;

 public Tree() {
  // brak korzenia
  root = null;
 }

 public Tree(Node<T> root) {
  // ustawiamy korzeń
  this.root = root;
 } 
}

Wykorzystajmy gotowe klasy Node<T> oraz Tree<T>  do budowy drzewa z diagramu.

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

Zbudowaliśmy strukturę drzewa. Pozostaje wyświetlenie naszego drzewa na ekranie oraz przedstawienie sposobów poruszania się po drzewie. To wszystko w następnej części...