search query: @author Hämäläinen, Petteri / total: 2
reference: 1 / 2
« previous | next »
Author: | Hämäläinen, Petteri |
Title: | Puu-tietorakenteen havainnollistaminen |
Draeing the Tree Data Structure | |
Publication type: | Master's thesis |
Publication year: | 1998 |
Pages: | 90 Language: fin |
Department/School: | Sähkö- ja tietoliikennetekniikan osasto |
Main subject: | Ohjelmistotekniikka (Tik-106) |
Supervisor: | Soisalon-Soininen, Eljas |
Instructor: | Oksanen, Kenneth |
OEVS: | Electronic archive copy is available via Aalto Thesis Database.
Instructions Reading digital theses in the closed network of the Aalto University Harald Herlin Learning CentreIn the closed network of Learning Centre you can read digital and digitized theses not available in the open network. The Learning Centre contact details and opening hours: https://learningcentre.aalto.fi/en/harald-herlin-learning-centre/ You can read theses on the Learning Centre customer computers, which are available on all floors.
Logging on to the customer computers
Opening a thesis
Reading the thesis
Printing the thesis
|
Location: | P1 Ark S80 | Archive |
Keywords: | tree drawing algorithms Walker's node-positioning algorithm aesthetic rules binary tree m-ary tree puunpiirtoalgoritmit Walkerin solmunasennusalgoritmi esteettisyyssäännöt binääripuu m-lapsinen puu |
Abstract (fin): | Työssä on toteutettu kaksi puunpiirto-ohjelmaa, joille puu kuvataan puunkuvauslistan muodossa. Ohjelmat on kirjoitettu Java-ohjelmointikielellä, joten ne toimivat kaikissa tietokoneissa. Java-sovellusohjelma lukee puunkuvauslistan tiedostosta ja näyttää puun omassa ikkunassaan. Puu voidaan tallettaa PostScript-tiedostoon kirjoittimelle tulostamista varten. Java-appletti toimii WorldWideWeb-selaimessa, ja puunkuvauslista kirjoitetaan appletin tekstikomponenttiin. Puun piirtäminen vaatii monimutkaisen algoritmin. Lukuisia epätäydellisiä algoritmeja esitettiin, ennen kuin Reingold ja Tilford keksivät muodostaa alipuut itsenäisesti muista solmuista riippumatta ja sitten sijoittaa ne mahdollisimman lähelle toisiaan. Tämä algoritmi toimii hyvin binääripuille, mutta m-lapsisilla puilla kahden ison alipuun väliin jäävät pienet alipuut pakkautuvat kiinni vasemmanpuoleiseen isoon alipuuhun, vaikka pienet alipuut pitäisi sijoittaa tasaisesti suurten alipuiden väliin. Radack, Walker ja Luo ovat kukin esittäneet omat ratkaisunsa tähän ongelmaan. Mikään niistä ei ole kuitenkaan täydellinen, vaikka ne tuottavatkin kauniin näköisiä puita. Walkerin algoritmi valittiin tässä työssä käytettäväksi, mutta sen suoritusaika osoittautui suureksi. Algoritmista on esitetty tässä työssä tehokkaampi versio, ja sen suorituskykyä on vertailtu alkuperäiseen algoritmiin käytännön testeillä. Korkeilla puilla uusi algoritmi on huomattavasti alkuperäistä algoritmia nopeampi. Työn alussa on pohdittu esteettisyyssääntöjen muodossa, millainen on kauniisti piirretty puu. M-lapsiselle puulle säännöt ovat seuraavat: samalla tasolla olevat solmut tulee sijaita suoralla viivalla, isä tulee keskittää lapsien yläpuolelle ja alipuu pitää piirtää samalla tavalla riippumatta sen sijainnista puussa. |
ED: | 1998-10-09 |
INSSI record number: 13581
+ add basket
« previous | next »
INSSI