Αποστολέας Θέμα: Ανάγνωση δυαδικού δένδρου με τέσσερις τρόπους  (Αναγνώστηκε 262 φορές)

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 388
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Παραλλαγή του κώδικα με τους κόμβους. Τώρα ο πίνακας κομ[] είναι δυο διαστάσεων για να γράφουμε δυο δείκτες, τον αριστερό και το δεξιό ως τιμές δεύτερης διάστασης 1 και 2. Έτσι τώρα κάθε κόμβος έχει δυο δείκτες. Ο πίνακας τιμ[] έγινε πίνακας χαρακτήρων.
Για τη κατασκευή του δένδρου, υπάρχουν πολλοί τρόποι. Εδώ ξεκίνησα από το 7, πήγα στο 4 και έβαλα το 7 σαν αριστερό παιδί, και μετά πήγα στο 2 όπου πέρασα το δένδρο σαν αριστερό παιδί και έβαλα το 3 ως δεξιό παιδί. μετά έβαλα ότι είχα σαν παιδί στο κόμβο με το 1 το οποίο και "σημάδεψα" στη μεταβλητή ρίζα. Κατόπιν γέμισα και ότι χρειάζονταν από την δεξιά πλευρά κάτω από το 1.

Οι τρεις τρόποι preorder, inorder, και postorder, έχουν γίνει με διαδικασία που καλεί τον εαυτό της όποτε το χρειάζεται, δηλαδή χρησιμοποιεί αναδρομή.

Ο τέταρτος τρόπος είναι πιο δύσκολος γιατί η ΓΛΩΣΣΑ δεν έχει κάποια δομή έτοιμη για ουρά, οπότε χρησιμοποίησα την δομή που είχα για ουρά, χωρίς να χρησιμοποιήσω για κάθε κόμβο τον πίνακα τιμ[]. Έτσι ο αριστερός δείκτης δείχνει τον επόμενο κόμβο, και ο δεξιός απλά κρατάει τον αριθμό του κόμβου που θέλουμε να βάλουμε στην ουρά. Υπάρχουν δυο διαδικασίες, η ΕισαγωγήΚόμβου και η ΕξαγωγήΚόμβου, και δεν χρησιμοποιούμε αναδρομή, απλά μια επανάληψη μέχρι η ουρά να αδειάσει. Τη πρώτη φορά βάζουμε στην ουρά την ρίζα.

Κάθε φορά που αδειάζει η ουρά διαγράφεται και το στοιχείο, δηλαδή πηγαίνει στην στοίβα ελεύθερων. Υπάρχει τέλος μια διαδικασία που μοιάζει με την postorder αλλά διαγράφει τα στοιχεία του δένδρου από τη ρίζα, και τα στέλνει στη στοίβα των ελεύθερων.

Στο τέλος μας δίνει το νούμερο των ελεύθερων κόμβων, το 100.


Το δένδρο είναι αυτό:
!         1
!        / \
!       /   \
!      /     \
!     2       3
!    / \     /
!   4   5   6
!  /       / \
! 7       8   9


Δηλαδή έχουμε 9 κόμβους.

Το αποτέλεσμα είναι αυτό:

Παράθεση
Ελεύθερη Μνήμη 91 κόμβων
preorder:    124753689
inorder:     742518693
postorder:   745289631
level-order: 123456789
Ελεύθερη Μνήμη 100 κόμβων


Κώδικας: [Επιλογή]
ΠΡΟΓΡΑΜΜΑ Δένδρο1
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: κομ[100, 2], ελεύθερο, μπροστά, πίσω, κορυφή
  ΧΑΡΑΚΤΗΡΕΣ: τιμ[100]
  ΑΚΕΡΑΙΕΣ: ι, βοηθητική1, βοηθητική2, ρίζα
ΑΡΧΗ
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 99
    κομ[ι, 1] <- ι + 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  κομ[100, 1] <- 0
!δείκτης ελεύθερων
  ελεύθερο <- 1
! θα φτιάξουμε το παρακάτω δένδρο
!         1
!        / \
!       /   \
!      /     \
!     2       3
!    / \     /
!   4   5   6
!  /       / \
! 7       8   9
  ρίζα <- 0
  ΚΑΛΕΣΕ Νεο(ρίζα, ελεύθερο, κομ)
  τιμ[ρίζα] <- "7"
  βοηθητική1 <- ρίζα
  ΚΑΛΕΣΕ Νεο(ρίζα, ελεύθερο, κομ)
  τιμ[ρίζα] <- "4"
! το 7 είναι αριστερό παιδί του 4
  κομ[ρίζα, 1] <- βοηθητική1
  βοηθητική1 <- ρίζα
  ΚΑΛΕΣΕ Νεο(ρίζα, ελεύθερο, κομ)
  τιμ[ρίζα] <- "2"
! το 4 είναι αριστερό παιδί του 2
  κομ[ρίζα, 1] <- βοηθητική1
  βοηθητική2 <- 0
  ΚΑΛΕΣΕ Νεο(βοηθητική2, ελεύθερο, κομ)
  τιμ[βοηθητική2] <- "5"
! το 5 είναι δεξιό παιδί του 4
  κομ[ρίζα, 2] <- βοηθητική2

  βοηθητική1 <- ρίζα
  ΚΑΛΕΣΕ Νεο(ρίζα, ελεύθερο, κομ)
  τιμ[ρίζα] <- "1"
! το 2 είναι αριστερό παιδί του 1
  κομ[ρίζα, 1] <- βοηθητική1
  βοηθητική2 <- 0
  ΚΑΛΕΣΕ Νεο(βοηθητική2, ελεύθερο, κομ)
  τιμ[βοηθητική2] <- "3"
! το 3 είναι δεξιό παιδί του 1
  κομ[ρίζα, 2] <- βοηθητική2
  βοηθητική1 <- 0
  ΚΑΛΕΣΕ Νεο(βοηθητική1, ελεύθερο, κομ)
  τιμ[βοηθητική1] <- "6"
! το 6 είναι αριστερό παιδί του 3
  κομ[βοηθητική2, 1] <- βοηθητική1
! τώρα η βοηθητική2 θα δείχνει το 6
  βοηθητική2 <- βοηθητική1

  βοηθητική1 <- 0
  ΚΑΛΕΣΕ Νεο(βοηθητική1, ελεύθερο, κομ)
  τιμ[βοηθητική1] <- "8"
! το 8 είναι αριστερό παιδί του 6
  κομ[βοηθητική2, 1] <- βοηθητική1
  βοηθητική1 <- 0
  ΚΑΛΕΣΕ Νεο(βοηθητική1, ελεύθερο, κομ)
  τιμ[βοηθητική1] <- "9"
! το 9 είναι δεξιό παιδί του 6
  κομ[βοηθητική2, 2] <- βοηθητική1
  ΚΑΛΕΣΕ Ελεύθερη_Μνήμη(ελεύθερο, κομ)
 
  ΑΝ ρίζα > 0 ΤΟΤΕ
    ΓΡΑΨΕ "preorder:    ", " "
    ΚΑΛΕΣΕ ΔείξεΔένδρο(ρίζα, κομ, τιμ)
  ΤΕΛΟΣ_ΑΝ
  ΓΡΑΨΕ
  ΑΝ ρίζα > 0 ΤΟΤΕ
    ΓΡΑΨΕ "inorder:     ", " "
    ΚΑΛΕΣΕ ΔείξεΔένδρο2(ρίζα, κομ, τιμ)
  ΤΕΛΟΣ_ΑΝ
  ΓΡΑΨΕ
  ΑΝ ρίζα > 0 ΤΟΤΕ
    ΓΡΑΨΕ "postorder:   ", " "
    ΚΑΛΕΣΕ ΔείξεΔένδρο3(ρίζα, κομ, τιμ)
  ΤΕΛΟΣ_ΑΝ
  ΓΡΑΨΕ
  ΑΝ ρίζα > 0 ΤΟΤΕ
    ΓΡΑΨΕ "level-order: ", " "
    ΚΑΛΕΣΕ ΔείξεΔένδρο4(ρίζα, ελεύθερο, κομ, τιμ)
  ΤΕΛΟΣ_ΑΝ
  ΓΡΑΨΕ
  ΚΑΛΕΣΕ ΔιαγραφήΚόμβων(ρίζα, ελεύθερο, κομ, τιμ)
  ΚΑΛΕΣΕ Ελεύθερη_Μνήμη(ελεύθερο, κομ)
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
ΔΙΑΔΙΚΑΣΙΑ ΔείξεΔένδρο(ρίζα, μνημη, περιεχόμενο)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ρίζα, μνημη[100, 2]
  ΧΑΡΑΚΤΗΡΕΣ: περιεχόμενο[100]
ΑΡΧΗ
  ΓΡΑΨΕ περιεχόμενο[ρίζα], " "
  ΑΝ μνημη[ρίζα, 1] > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΔείξεΔένδρο(μνημη[ρίζα, 1], μνημη, περιεχόμενο)
  ΤΕΛΟΣ_ΑΝ

  ΑΝ μνημη[ρίζα, 2] > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΔείξεΔένδρο(μνημη[ρίζα, 2], μνημη, περιεχόμενο)
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΔείξεΔένδρο2(ρίζα, μνημη, περιεχόμενο)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ρίζα, μνημη[100, 2]
  ΧΑΡΑΚΤΗΡΕΣ: περιεχόμενο[100]
ΑΡΧΗ

  ΑΝ μνημη[ρίζα, 1] > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΔείξεΔένδρο2(μνημη[ρίζα, 1], μνημη, περιεχόμενο)
  ΤΕΛΟΣ_ΑΝ
  ΓΡΑΨΕ περιεχόμενο[ρίζα], " "
  ΑΝ μνημη[ρίζα, 2] > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΔείξεΔένδρο2(μνημη[ρίζα, 2], μνημη, περιεχόμενο)
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΔείξεΔένδρο3(ρίζα, μνημη, περιεχόμενο)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ρίζα, μνημη[100, 2]
  ΧΑΡΑΚΤΗΡΕΣ: περιεχόμενο[100]
ΑΡΧΗ

  ΑΝ μνημη[ρίζα, 1] > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΔείξεΔένδρο3(μνημη[ρίζα, 1], μνημη, περιεχόμενο)
  ΤΕΛΟΣ_ΑΝ
  ΑΝ μνημη[ρίζα, 2] > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΔείξεΔένδρο3(μνημη[ρίζα, 2], μνημη, περιεχόμενο)
  ΤΕΛΟΣ_ΑΝ
  ΓΡΑΨΕ περιεχόμενο[ρίζα], " "
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΔιαγραφήΚόμβων(ρίζα, ελ, μνημη, περιεχόμενο)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ρίζα, μνημη[100, 2], ελ
  ΧΑΡΑΚΤΗΡΕΣ: περιεχόμενο[100]
ΑΡΧΗ

  ΑΝ μνημη[ρίζα, 1] > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΔιαγραφήΚόμβων(μνημη[ρίζα, 1], ελ, μνημη, περιεχόμενο)
  ΤΕΛΟΣ_ΑΝ
  ΑΝ μνημη[ρίζα, 2] > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΔιαγραφήΚόμβων(μνημη[ρίζα, 2], ελ, μνημη, περιεχόμενο)
  ΤΕΛΟΣ_ΑΝ
  περιεχόμενο[ρίζα] <- ""
  μνημη[ρίζα, 1] <- ελ
  ελ <- ρίζα
  μνημη[ρίζα, 2] <- 0
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ Νεο(επιστροφή, ελ, μνήμη)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: επιστροφή, ελ, μνήμη[100, 2]
ΑΡΧΗ
  επιστροφή <- ελ
  ελ <- μνήμη[ελ, 1]
  μνήμη[επιστροφή, 1] <- 0
  μνήμη[επιστροφή, 2] <- 0
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ Ελεύθερη_Μνήμη(ελ, μνήμη)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: βοηθητική, ελ, μνήμη[100, 2], ι
ΑΡΧΗ
  βοηθητική <- ελ
  ι <- 0
  ΟΣΟ βοηθητική <> 0 ΕΠΑΝΑΛΑΒΕ
    ι <- ι + 1
    βοηθητική <- μνήμη[βοηθητική, 1]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ "Ελεύθερη Μνήμη ", ι, " κόμβων"
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
! Η ουρά αυτή είναι βοηθητική, και χρησιμοποιεί μόνο το πίνακα κόμβων
! στο αριστερό παιδί συνδέουμε το επόμενο της ουράς, στο δεξιό συνδέουμε έναν κόμβο
! από το κύριο δένδρο
ΔΙΑΔΙΚΑΣΙΑ ΕισαγωγήΟυράς(κόμβος, μπροστά, ελ, μνήμη)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: βοηθητική, ελ, μνήμη[100, 2], κόμβος, μπροστά
ΑΡΧΗ
  βοηθητική <- μπροστά
  ΚΑΛΕΣΕ Νεο(μπροστά, ελ, μνήμη)
  μνήμη[μπροστά, 2] <- κόμβος
  ΑΝ βοηθητική <> 0 ΤΟΤΕ
    μνήμη[βοηθητική, 1] <- μπροστά
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΕξαγωγήΟυράς(κόμβος, πίσω, μπροστά, ελ, μνήμη)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: βοηθητική, ελ, μνήμη[100, 2], κόμβος, πίσω, μπροστά
ΑΡΧΗ
  κόμβος <- μνήμη[πίσω, 2]
  βοηθητική <- πίσω
  πίσω <- μνήμη[πίσω, 1]
  μνήμη[βοηθητική, 1] <- ελ
  ελ <- βοηθητική
! αν το πίσω γίνει 0 τότε άδειασε η ουρά
  ΑΝ πίσω = 0 ΤΟΤΕ
    πίσω <- ελ
    μπροστά <- 0
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΔείξεΔένδρο4(ρίζα, ελ, μνημη, περιεχόμενο)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ρίζα, μνημη[100, 2], μπροστά, πίσω, βοηθητική, ελ
  ΧΑΡΑΚΤΗΡΕΣ: περιεχόμενο[100]
ΑΡΧΗ
  πίσω <- ελ
  μπροστά <- 0
  ΚΑΛΕΣΕ ΕισαγωγήΟυράς(ρίζα, μπροστά, ελ, μνημη)
  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    ΚΑΛΕΣΕ ΕξαγωγήΟυράς(βοηθητική, πίσω, μπροστά, ελ, μνημη)
   
    ΓΡΑΨΕ περιεχόμενο[βοηθητική], " "
    ΑΝ μνημη[βοηθητική, 1] > 0 ΤΟΤΕ
      ΚΑΛΕΣΕ ΕισαγωγήΟυράς(μνημη[βοηθητική, 1], μπροστά, ελ, μνημη)
    ΤΕΛΟΣ_ΑΝ
    ΑΝ μνημη[βοηθητική, 2] > 0 ΤΟΤΕ
      ΚΑΛΕΣΕ ΕισαγωγήΟυράς(μνημη[βοηθητική, 2], μπροστά, ελ, μνημη)
    ΤΕΛΟΣ_ΑΝ
  ΜΕΧΡΙΣ_ΟΤΟΥ μπροστά = 0
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
« Τελευταία τροποποίηση: 17 Ιούλ 2019, 03:21:42 μμ από bugman »

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 388
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Απ: Ανάγνωση δυαδικού δένδρου με τέσσερις τρόπους
« Απάντηση #1 στις: 17 Ιούλ 2019, 03:06:51 μμ »
Το ίδιο πρόγραμμα χωρίς αναδρομή στα τρία πρώτα (preorder, inorder, postorder).
Εδώ αντί για αναδρομή χρησιμοποιούμε μια ουρά. Θέλουμε στην ουρά να μπαίνει ο αριθμός κόμβου με αρνητικό πρόσημο όταν απλά θέλουμε να τυπωθεί. Όταν στην ουρά μπαίνει με θετικό πρόσημο τότε η ουρά ανατροφοδοτείται με ένα έως τρια στοιχεία ανάλογα αν υπάρχουν παιδιά στον κόμβο.

Προστέθηκαν δυο διαδικασίες για ώθηση και απώθηση σε σωρό.

Η διαγραφή κόμβων έγινε και αυτή μη αναδρομική (παραλλαγή της postorder)

Τώρα το πρόγραμμα δεν έχει αναδρομή δηλαδή είναι εντός της ύλης!

Η εξαγωγή είναι η ίδια
Παράθεση
Ελεύθερη Μνήμη 91 κόμβων
preorder:    124753689
inorder:     742518693
postorder:   745289631
level-order: 123456789
Ελεύθερη Μνήμη 100 κόμβων



Κώδικας: [Επιλογή]
ΠΡΟΓΡΑΜΜΑ ΔένδροΑναζήτησης
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: κομ[100, 2], ελεύθερο, μπροστά, πίσω, κορυφή
  ΧΑΡΑΚΤΗΡΕΣ: τιμ[100]
  ΑΚΕΡΑΙΕΣ: ι, βοηθητική1, βοηθητική2, ρίζα
ΑΡΧΗ
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 99
    κομ[ι, 1] <- ι + 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  κομ[100, 1] <- 0
!δείκτης ελεύθερων
  ελεύθερο <- 1
! θα φτιάξουμε το πααακάτω δένδρο
!         1
!        / \
!       /   \
!      /     \
!     2       3
!    / \     /
!   4   5   6
!  /       / \
! 7       8   9
  ρίζα <- 0
  ΚΑΛΕΣΕ Νεο(ρίζα, ελεύθερο, κομ)
  τιμ[ρίζα] <- "7"
  βοηθητική1 <- ρίζα
  ΚΑΛΕΣΕ Νεο(ρίζα, ελεύθερο, κομ)
  τιμ[ρίζα] <- "4"
! το 7 είναι αριστερό παιδί του 4
  κομ[ρίζα, 1] <- βοηθητική1
  βοηθητική1 <- ρίζα
  ΚΑΛΕΣΕ Νεο(ρίζα, ελεύθερο, κομ)
  τιμ[ρίζα] <- "2"
! το 4 είναι αριστερό παιδί του 2
  κομ[ρίζα, 1] <- βοηθητική1
  βοηθητική2 <- 0
  ΚΑΛΕΣΕ Νεο(βοηθητική2, ελεύθερο, κομ)
  τιμ[βοηθητική2] <- "5"
! το 5 είναι δεξιό παιδί του 4
  κομ[ρίζα, 2] <- βοηθητική2

  βοηθητική1 <- ρίζα
  ΚΑΛΕΣΕ Νεο(ρίζα, ελεύθερο, κομ)
  τιμ[ρίζα] <- "1"
! το 2 είναι αριστερό παιδί του 1
  κομ[ρίζα, 1] <- βοηθητική1
  βοηθητική2 <- 0
  ΚΑΛΕΣΕ Νεο(βοηθητική2, ελεύθερο, κομ)
  τιμ[βοηθητική2] <- "3"
! το 3 είναι δεξιό παιδί του 1
  κομ[ρίζα, 2] <- βοηθητική2
  βοηθητική1 <- 0
  ΚΑΛΕΣΕ Νεο(βοηθητική1, ελεύθερο, κομ)
  τιμ[βοηθητική1] <- "6"
! το 6 είναι αριστερό παιδί του 3
  κομ[βοηθητική2, 1] <- βοηθητική1
! τώρα η βοηθητική2 θα δείχνει το 6
  βοηθητική2 <- βοηθητική1

  βοηθητική1 <- 0
  ΚΑΛΕΣΕ Νεο(βοηθητική1, ελεύθερο, κομ)
  τιμ[βοηθητική1] <- "8"
! το 8 είναι αριστερό παιδί του 6
  κομ[βοηθητική2, 1] <- βοηθητική1
  βοηθητική1 <- 0
  ΚΑΛΕΣΕ Νεο(βοηθητική1, ελεύθερο, κομ)
  τιμ[βοηθητική1] <- "9"
! το 9 είναι δεξιό παιδί του 6
  κομ[βοηθητική2, 2] <- βοηθητική1
  ΚΑΛΕΣΕ Ελεύθερη_Μνήμη(ελεύθερο, κομ)
 
  ΑΝ ρίζα > 0 ΤΟΤΕ
    ΓΡΑΨΕ "preorder:    ", " "
    ΚΑΛΕΣΕ ΔείξεΔένδρο(ρίζα, ελεύθερο, κομ, τιμ)
  ΤΕΛΟΣ_ΑΝ
  ΓΡΑΨΕ
  ΑΝ ρίζα > 0 ΤΟΤΕ
    ΓΡΑΨΕ "inorder:     ", " "
    ΚΑΛΕΣΕ ΔείξεΔένδρο2(ρίζα, ελεύθερο, κομ, τιμ)
  ΤΕΛΟΣ_ΑΝ
  ΓΡΑΨΕ
  ΑΝ ρίζα > 0 ΤΟΤΕ
    ΓΡΑΨΕ "postorder:   ", " "
    ΚΑΛΕΣΕ ΔείξεΔένδρο3(ρίζα, ελεύθερο, κομ, τιμ)
  ΤΕΛΟΣ_ΑΝ
  ΓΡΑΨΕ
  ΑΝ ρίζα > 0 ΤΟΤΕ
    ΓΡΑΨΕ "level-order: ", " "
    ΚΑΛΕΣΕ ΔείξεΔένδρο4(ρίζα, ελεύθερο, κομ, τιμ)
  ΤΕΛΟΣ_ΑΝ
  ΓΡΑΨΕ
  ΚΑΛΕΣΕ ΔιαγραφήΚόμβων(ρίζα, ελεύθερο, κομ, τιμ)
  ΚΑΛΕΣΕ Ελεύθερη_Μνήμη(ελεύθερο, κομ)
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
! Η Στοίβα αυτή είναι βοηθητική και χρησιμοποιεί μόνο το πίνακα κόμβων
! στο αριστερό παιδί συνδέουμε την προηγούμενη κορυφή, στο δεξιό συνδέουμε έναν κόμβο
! από το κύριο δένδρο
ΔΙΑΔΙΚΑΣΙΑ ΩθησηΣτοίβας(κόμβος, κορυφή, ελ, μνήμη)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: βοηθητική, ελ, μνήμη[100, 2], κόμβος, κορυφή
ΑΡΧΗ
  βοηθητική <- κορυφή
  ΚΑΛΕΣΕ Νεο(κορυφή, ελ, μνήμη)
  μνήμη[κορυφή, 2] <- κόμβος
  μνήμη[κορυφή, 1] <- βοηθητική
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΑπωθησηΣτοίβας(κόμβος, κορυφή, ελ, μνήμη)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: βοηθητική, ελ, μνήμη[100, 2], κόμβος, κορυφή
ΑΡΧΗ
  ΑΝ κορυφή > 0 ΤΟΤΕ
    κόμβος <- μνήμη[κορυφή, 2]
    μνήμη[κορυφή, 2] <- 0
    βοηθητική <- κορυφή
    κορυφή <- μνήμη[κορυφή, 1]
! Απελευθέρωση παλιάς κορυφής
    μνήμη[βοηθητική, 1] <- ελ
    ελ <- βοηθητική
  ΑΛΛΙΩΣ
    κόμβος <- 0
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΔείξεΔένδρο(ρίζα, ελ, μνημη, περιεχόμενο)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ρίζα, μνημη[100, 2], κορυφή, ελ, βοηθητική, βοηθητική2
  ΧΑΡΑΚΤΗΡΕΣ: περιεχόμενο[100]
ΑΡΧΗ
  βοηθητική <- ρίζα
  κορυφή <- 0
  βοηθητική2 <- μνημη[βοηθητική, 2]
  ΑΝ βοηθητική2 > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
  ΤΕΛΟΣ_ΑΝ
  βοηθητική2 <- μνημη[βοηθητική, 1]
  ΑΝ βοηθητική2 > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
  ΤΕΛΟΣ_ΑΝ
  ΚΑΛΕΣΕ ΩθησηΣτοίβας(-βοηθητική, κορυφή, ελ, μνημη)
  ΟΣΟ κορυφή > 0 ΕΠΑΝΑΛΑΒΕ
    ΚΑΛΕΣΕ ΑπωθησηΣτοίβας(βοηθητική, κορυφή, ελ, μνημη)
    ΑΝ βοηθητική < 0 ΤΟΤΕ
      ΓΡΑΨΕ περιεχόμενο[-βοηθητική], " "
    ΑΛΛΙΩΣ_ΑΝ βοηθητική > 0 ΤΟΤΕ
      βοηθητική2 <- μνημη[βοηθητική, 2]
      ΑΝ βοηθητική2 > 0 ΤΟΤΕ
        ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
      ΤΕΛΟΣ_ΑΝ
      βοηθητική2 <- μνημη[βοηθητική, 1]
      ΑΝ βοηθητική2 > 0 ΤΟΤΕ
        ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
      ΤΕΛΟΣ_ΑΝ
      ΚΑΛΕΣΕ ΩθησηΣτοίβας(-βοηθητική, κορυφή, ελ, μνημη)
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΔείξεΔένδρο2(ρίζα, ελ, μνημη, περιεχόμενο)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ρίζα, μνημη[100, 2], κορυφή, ελ, βοηθητική, βοηθητική2
  ΧΑΡΑΚΤΗΡΕΣ: περιεχόμενο[100]
ΑΡΧΗ
  βοηθητική <- ρίζα
  κορυφή <- 0
  βοηθητική2 <- μνημη[βοηθητική, 2]
  ΑΝ βοηθητική2 > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
  ΤΕΛΟΣ_ΑΝ
  ΚΑΛΕΣΕ ΩθησηΣτοίβας(-βοηθητική, κορυφή, ελ, μνημη)
  βοηθητική2 <- μνημη[βοηθητική, 1]
  ΑΝ βοηθητική2 > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
  ΤΕΛΟΣ_ΑΝ
  ΟΣΟ κορυφή > 0 ΕΠΑΝΑΛΑΒΕ
    ΚΑΛΕΣΕ ΑπωθησηΣτοίβας(βοηθητική, κορυφή, ελ, μνημη)
    ΑΝ βοηθητική < 0 ΤΟΤΕ
      ΓΡΑΨΕ περιεχόμενο[-βοηθητική], " "
    ΑΛΛΙΩΣ_ΑΝ βοηθητική > 0 ΤΟΤΕ
      βοηθητική2 <- μνημη[βοηθητική, 2]
      ΑΝ βοηθητική2 > 0 ΤΟΤΕ
        ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
      ΤΕΛΟΣ_ΑΝ
      ΚΑΛΕΣΕ ΩθησηΣτοίβας(-βοηθητική, κορυφή, ελ, μνημη)
      βοηθητική2 <- μνημη[βοηθητική, 1]
      ΑΝ βοηθητική2 > 0 ΤΟΤΕ
        ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΔείξεΔένδρο3(ρίζα, ελ, μνημη, περιεχόμενο)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ρίζα, μνημη[100, 2], κορυφή, ελ, βοηθητική, βοηθητική2
  ΧΑΡΑΚΤΗΡΕΣ: περιεχόμενο[100]
ΑΡΧΗ
  βοηθητική <- ρίζα
  κορυφή <- 0
  ΚΑΛΕΣΕ ΩθησηΣτοίβας(-βοηθητική, κορυφή, ελ, μνημη)
  βοηθητική2 <- μνημη[βοηθητική, 2]
  ΑΝ βοηθητική2 > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
  ΤΕΛΟΣ_ΑΝ
  βοηθητική2 <- μνημη[βοηθητική, 1]
  ΑΝ βοηθητική2 > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
  ΤΕΛΟΣ_ΑΝ
  ΟΣΟ κορυφή > 0 ΕΠΑΝΑΛΑΒΕ
    ΚΑΛΕΣΕ ΑπωθησηΣτοίβας(βοηθητική, κορυφή, ελ, μνημη)
    ΑΝ βοηθητική < 0 ΤΟΤΕ
      ΓΡΑΨΕ περιεχόμενο[-βοηθητική], " "
    ΑΛΛΙΩΣ_ΑΝ βοηθητική > 0 ΤΟΤΕ
      ΚΑΛΕΣΕ ΩθησηΣτοίβας(-βοηθητική, κορυφή, ελ, μνημη)
      βοηθητική2 <- μνημη[βοηθητική, 2]
      ΑΝ βοηθητική2 > 0 ΤΟΤΕ
        ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
      ΤΕΛΟΣ_ΑΝ
      βοηθητική2 <- μνημη[βοηθητική, 1]
      ΑΝ βοηθητική2 > 0 ΤΟΤΕ
        ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΔιαγραφήΚόμβων(ρίζα, ελ, μνημη, περιεχόμενο)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ρίζα, μνημη[100, 2], κορυφή, ελ, βοηθητική, βοηθητική2
  ΧΑΡΑΚΤΗΡΕΣ: περιεχόμενο[100]
ΑΡΧΗ
  βοηθητική <- ρίζα
  κορυφή <- 0
  ΚΑΛΕΣΕ ΩθησηΣτοίβας(-βοηθητική, κορυφή, ελ, μνημη)
  βοηθητική2 <- μνημη[βοηθητική, 2]
  ΑΝ βοηθητική2 > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
  ΤΕΛΟΣ_ΑΝ
  βοηθητική2 <- μνημη[βοηθητική, 1]
  ΑΝ βοηθητική2 > 0 ΤΟΤΕ
    ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
  ΤΕΛΟΣ_ΑΝ
  ΟΣΟ κορυφή > 0 ΕΠΑΝΑΛΑΒΕ
    ΚΑΛΕΣΕ ΑπωθησηΣτοίβας(βοηθητική, κορυφή, ελ, μνημη)
    ΑΝ βοηθητική < 0 ΤΟΤΕ
      βοηθητική <- -βοηθητική
      περιεχόμενο[βοηθητική] <- ""
      μνημη[βοηθητική, 1] <- ελ
      ελ <- βοηθητική
      μνημη[βοηθητική, 2] <- 0
    ΑΛΛΙΩΣ_ΑΝ βοηθητική > 0 ΤΟΤΕ
      ΚΑΛΕΣΕ ΩθησηΣτοίβας(-βοηθητική, κορυφή, ελ, μνημη)
      βοηθητική2 <- μνημη[βοηθητική, 2]
      ΑΝ βοηθητική2 > 0 ΤΟΤΕ
        ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
      ΤΕΛΟΣ_ΑΝ
      βοηθητική2 <- μνημη[βοηθητική, 1]
      ΑΝ βοηθητική2 > 0 ΤΟΤΕ
        ΚΑΛΕΣΕ ΩθησηΣτοίβας(βοηθητική2, κορυφή, ελ, μνημη)
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ Νεο(επιστροφή, ελ, μνήμη)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: επιστροφή, ελ, μνήμη[100, 2]
ΑΡΧΗ
  επιστροφή <- ελ
  ελ <- μνήμη[ελ, 1]
  μνήμη[επιστροφή, 1] <- 0
  μνήμη[επιστροφή, 2] <- 0
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ Ελεύθερη_Μνήμη(ελ, μνήμη)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: βοηθητική, ελ, μνήμη[100, 2], ι
ΑΡΧΗ
  βοηθητική <- ελ
  ι <- 0
  ΟΣΟ βοηθητική <> 0 ΕΠΑΝΑΛΑΒΕ
    ι <- ι + 1
    βοηθητική <- μνήμη[βοηθητική, 1]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ "Ελεύθερη Μνήμη ", ι, " κόμβων"
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
! Η ουρά αυτή είναι βοηθητική, και χρησιμοποιεί μόνο το πίνακα κόμβων
! στο αριστερό παιδί συνδέουμε το επόμενο της ουράς, στο δεξιό συνδέουμε έναν κόμβο
! από το κύριο δένδρο
ΔΙΑΔΙΚΑΣΙΑ ΕισαγωγήΟυράς(κόμβος, μπροστά, ελ, μνήμη)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: βοηθητική, ελ, μνήμη[100, 2], κόμβος, μπροστά
ΑΡΧΗ
  βοηθητική <- μπροστά
  ΚΑΛΕΣΕ Νεο(μπροστά, ελ, μνήμη)
  μνήμη[μπροστά, 2] <- κόμβος
  ΑΝ βοηθητική <> 0 ΤΟΤΕ
    μνήμη[βοηθητική, 1] <- μπροστά
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΕξαγωγήΟυράς(κόμβος, πίσω, μπροστά, ελ, μνήμη)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: βοηθητική, ελ, μνήμη[100, 2], κόμβος, πίσω, μπροστά
ΑΡΧΗ
  κόμβος <- μνήμη[πίσω, 2]
  βοηθητική <- πίσω
  πίσω <- μνήμη[πίσω, 1]
  μνήμη[βοηθητική, 1] <- ελ
  ελ <- βοηθητική
! αν το πίσω γίνει 0 τότε άδειασε η ουρά
  ΑΝ πίσω = 0 ΤΟΤΕ
    πίσω <- ελ
    μπροστά <- 0
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
ΔΙΑΔΙΚΑΣΙΑ ΔείξεΔένδρο4(ρίζα, ελ, μνήμη, περιεχόμενο)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ρίζα, μνήμη[100, 2], μπροστά, πίσω, βοηθητική, ελ
  ΧΑΡΑΚΤΗΡΕΣ: περιεχόμενο[100]
ΑΡΧΗ
  πίσω <- ελ
  μπροστά <- 0
  ΚΑΛΕΣΕ ΕισαγωγήΟυράς(ρίζα, μπροστά, ελ, μνήμη)
  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    ΚΑΛΕΣΕ ΕξαγωγήΟυράς(βοηθητική, πίσω, μπροστά, ελ, μνήμη)
    ΓΡΑΨΕ περιεχόμενο[βοηθητική], " "
    ΑΝ μνήμη[βοηθητική, 1] > 0 ΤΟΤΕ
      ΚΑΛΕΣΕ ΕισαγωγήΟυράς(μνήμη[βοηθητική, 1], μπροστά, ελ, μνήμη)
    ΤΕΛΟΣ_ΑΝ
    ΑΝ μνήμη[βοηθητική, 2] > 0 ΤΟΤΕ
      ΚΑΛΕΣΕ ΕισαγωγήΟυράς(μνήμη[βοηθητική, 2], μπροστά, ελ, μνήμη)
    ΤΕΛΟΣ_ΑΝ
  ΜΕΧΡΙΣ_ΟΤΟΥ μπροστά = 0
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

« Τελευταία τροποποίηση: 17 Ιούλ 2019, 03:37:13 μμ από bugman »