Trees, representation of trees, traversal of trees

Puu, puu esitusviisid ja töötlemine Javas

Puu (programmeerimisalal tavaliselt järjestatud puu):

• dünaamiline andmestruktuur
• komponentideks nn. puu tipud: juurtipp e. juur, vahetipud, lehed (terminaalsed tipud)
• peegeldab ranget hierarhiat: juurtipp on kõige kõrgema taseme "ülemus", kõigil ülejäänud tippudel on täpselt üks ülemus (kasutatakse ka "vanemad-lapsed-vennad" metafoori)
• alluvateta tipud = puu lehed, kõik ülejäänud tipud on vahetipud
• sama ülemuse alluvad - kolleegid, naabrid
• järjestatud puu korral on oluline iga tipu alluvate (naabrite) omavaheline järjestus 

Näide:  aritmeetilise avaldise puu

Puu läbimine

Eesjärjestus (pre-order):

1. Töödelda juur
2. Töödelda juure alampuud järjestuses vasakult paremale

Lõppjärjestus (post-order, end-order):

1. Töödelda juure alampuud järjestuses vasakult paremale
2. Töödelda juur

1. Töödelda vasak alampuu
2. Töödelda juur
3. Töödelda parem alampuu
   

Avaldise prefikskuju saadakse puu läbimisega eesjärjestuses, postfikskuju (ja pööratud poola kuju) puu läbimisega lõppjärjestuses; läbimine keskjärjestuses ei anna praegusel juhul üheselt taastatavat avaldist!

Puu esitusviisid

Graafiline (joonisena)

Vasakpoolne suluesitus

A(B(D(G,H),E,F(I)),C(J))

Parempoolne suluesitus

(((G,H)D,E,(I)F)B,(J)C)A

Tekstiline "treppimine"

A

B

D

G

H

E

F

I

C

J

Tippudele viitamine liitnimedega

A, A.B, A.C, A.B.D, A.B.E, A.B.F, A.B.D.G, A.B.D.H, A.B.F.I, A.C.J

Mittejärjestatud puu esitamiseks sobivad ka graafi esitusviisid (vajadusel fikseerida juurtipp) - näit. külgnevusmaatriks vms.

Puu esitusviisid töötlemiseks arvutis sõltuvad lahendatavast ülesandest - universaalset "parimat" kujutusviisi ei leidu:

• tekstilised esitused
• viidastruktuurid
• peitmine muude mehhanismide sisse
• ...

• Igas tipus on viit tema ülemusele (juurtipus nullviit). Puudus: puu tippe ei saa lähtudes juurtipust süstemaatiliselt "läbi käia". Saab teha töötlust "alt üles", kui on korraldatud juurdepääs lehtede hulgale .
• Igast tipust lähtub selle tipu vahetute alluvate ahel (lehtede korral tühi ahel) ning viit (parempoolsele) naabrile. Puudus: antud tipust ei pääse lisavõimalusi (näit. magasini) kasutamata "üles". Kasulik rekursiivsete töötlusprogrammide korral.
• Eelmise kujutusviisi modifikatsioon: lisatunnus näitab, kas tipul on parempoolset naabrit. Kui ei ole, siis on nullviida asemel viit ülemusele.
• Tipud on seotud ahelasse. Igast tipust lähtub väljuvate kaarte ahel. Igas kaares on viit tipule, millesse kaar suubub (suhteliselt üldine meetod graafide kujutamiseks)
• Nn. kahendpuu tipus on viit vasakule alampuule ning viit paremale alampuule. Läbimiseks tuleb kasutada magasini või rekursiivset algoritmi.

         Joonis  

Mõned puudega seotud ülesanded

• Avaldiste arvutamine: näit. aritmeetilise avaldise puu töötlemine "alt üles"
• Transleerimine: programmi süntaksipuu põhjal koodi genereerimine või programmi tõlkimine näit. "postfikskujule"
• Struktureeritud andmete jaoks tabelivormide genereerimine

Puu kujutamine

#!/usr/bin/env python3
"""
Module: node.py
General trees.
"""

import sys
import random
import math
import time

__author__ = 'Jaanus'


class Node(object):
    """
    Class Node.
    Tree node with two pointers.
    """
    __name = 'noname_node'
    __first_child = None
    __next_sibling = None
    __info = 0

    def __init__(self, name, down, right):
        self.__name = name
        self.__first_child = down
        self.__next_sibling = right

    def get_name(self):
        return self.__name

    def set_name(self, name):
        self.__name = name

    def get_first_child(self):
        return self.__first_child

    def set_first_child(self, node):
        self.__first_child = node

    def get_next_sibling(self):
        return self.__next_sibling

    def set_next_sibling(self, node):
        self.__next_sibling = node

    def get_info(self):
        return self.__info

    def set_info(self, info):
        self.__info = info

    def size(self):
        res = 1
        child = self.get_first_child()
        while child:
            res += child.size()
            child = child.get_next_sibling()
        return res

    def process_node(self):
        print(self.get_name(), end=' ')

    def pre_order(self):
        self.process_node()
        child = self.get_first_child()
        while child:
            child.pre_order()
            child = child.get_next_sibling()

    def add_child(self, tipp):
        if tipp:
            if not self.get_first_child():
                self.set_first_child(tipp)
            else:
                laps = self.get_first_child()
                while laps.get_next_sibling():
                    laps = laps.get_next_sibling()
                laps.set_next_sibling(tipp)

    @staticmethod
    def create_tree():
        return Node('A',
                    Node('B',
                         None,
                    Node('C',
                         Node('D',
                              None,
                         None),
                    Node('E',
                         None,
                    None))),
               None)


def main():
    """
    Main method.
    """
    tree = Node.create_tree()
    tree.pre_order()
    print()


if __name__ == '__main__':
    main()