Trees, representation of trees, traversal of trees

Definitions: nodes, parent-child relationship, root, leaves, external and internal nodes, ordered trees. Preorder traversal, postorder traversal. Binary trees, in-order traversal.
Arithmetic expression tree. Representation of trees: textual (left parenthetic and right parenthetic expressions, indented text, composite names), pointer structures. Implementation and examples.

Puu, puu esitusviisid ja töötlemine Javas

Puu (programmeerimisalal tavaliselt järjestatud puu):


Näide:  aritmeetilise avaldise puu

Aritmeetilise avaldise puu  



Infikskuju prioriteedisulgudega:  (5 - 1) * 7 + 6 / 3

Prefikskuju sulgudega:  + (* (- (5, 1), 7), / (6, 3))

Postfikskuju sulgudega:  (((5, 1)-, 7)*, (6, 3)/ )+

Pööratud poola kuju:  5 1 - 7 * 6 3 / +


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
Kahendpuu läbimine keskjärjestuses (in-order)
  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


Preorder: A B D G H E F I C J

Postorder: G H D E I F B J C A


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:

Puu kujutamine ahelate abil

         Joonis  

Mõned puudega seotud ülesanded


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()



Jaanus Pöial