Δένδρα

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Ορισμοί

Ιδιότητες

Υλοποίηση σε C

Παράδειγμα:
#include <stdlib.h>

/*
 * Declare a binary tree of integers
 */
struct s_tree {
	int val;
	struct s_tree *left, *right;
};

main()
{
	struct s_tree *tree, *node;

	node = (struct s_tree *)malloc(sizeof(struct s_tree));
	node->val = 5;
	node->left = node->right = NULL;
	tree = node;

	node = (struct s_tree *)malloc(sizeof(struct s_tree));
	node->val = 12;
	node->left = node->right = NULL;
	tree->right = node;
}

Δένδρα αναζήτησης

Παράδειγμα αναζήτησης

/*
 * Search for the integer i in the ordered binary tree t
 * If found return its node; otherwise return NULL
 */
struct s_tree
search(struct s_tree *t, int i)
{
	if (t == NULL)
		return (NULL);
	else if (t->val == i)
		return (t);
	else if (i < t->val)
		return (search(t->left, i));
	else
		return (search(t->right, i));
}

Διάσχιση δένδρων

Η διάσχιση ενός δένδρου μπορεί να γίνει με τους παρακάτω τρόπους ανάλογα με τη σειρά επίσκεψης των κόμβων:
Προδιαταγμένη διάσχιση (preorder traversal)
  1. επίσκεψη της ρίζας
  2. επίσκεψη του αριστερού υποδένδρου
  3. επίσκεψη του δεξιού υποδένδρου
Μεταδιαταγμένη διάσχιση (postorder traversal)
  1. επίσκεψη του αριστερού υποδένδρου
  2. επίσκεψη του δεξιού υποδένδρου
  3. επίσκεψη της ρίζας
Ενδοδιαταγμένη διάσχιση (inorder traversal)
  1. επίσκεψη του αριστερού υποδένδρου
  2. επίσκεψη της ρίζας
  3. επίσκεψη του δεξιού υποδένδρου
Επιπεδοδιαταγμένη διάσχιση (level order traversal)
  1. επίσκεψη των κόμβων από πάνω προς τα κάτω

Οι αντίστοιχες διασχίσεις διάσχισης υλοποιούνται αναδρομικά ως εξής:

Προδιαταγμένη διάσχιση
void
visit(struct s_tree *t, void(*process)(int val))
{
	if (t == NULL)
		return;
	process(t->val);
	visit(t->left);
	visit(t->right);
}
Μεταδιαταγμένη διάσχιση
void
visit(struct s_tree *t, void(*process)(int val))
{
	if (t == NULL)
		return;
	visit(t->left);
	visit(t->right);
	process(t->val);
}
Ενδοδιαταγμένη διάσχιση
void
visit(struct s_tree *t, void(*process)(int val))
{
	if (t == NULL)
		return;
	visit(t->left);
	process(t->val);
	visit(t->right);
}
Επιπεδοδιαταγμένη διάσχιση
/*
 * Process all nodes at taget level given a tree t and its current depth level
 * Return the number of nodes processed
 * (Used by the visit function)
 */
static int
visit_level(struct s_tree *t, int current_level, int target_level, void(*process)(int val))
{
	if (t == NULL || current_level > target_level)
		return (0);
	else if (current_level == target_level) {
		process(t->val);
		return (1);
	} else
		return (
		    visit_level(t->left, current_level + 1, target_level, process) +
		    visit_level(t->left, current_level + 1, target_level, process));
}

void
visit(struct s_tree *t, void(*process)(int val))
{
	int i = 0;
	int nodes_processed;

	do {
		nodes_processed = visit_level(t, 0, i, process);
		i++;
	} while (nodes_processed > 0);
}

Εφαρμογές

Βιβλιογραφία

Ασκήσεις

Άσκηση 5

  1. Να υλοποιηθεί σε C πρόγραμμα το οποίο με τη χρήση διατεταγμένου δυαδικού δένδρου διαβάζει από το χρήστη μια σειρά από ονόματα μέχρι να τελειώσει το αρχείο που διαβάζει (π.χ. ο χρήστης πληκτρολογήσει CTRL-Z) και τα εκτυπώνει με αλφαβητική σειρά. Παράδειγμα:
    Verdi
    Strauss
    Mozart
    Wagner
    Adams
    Gounod
    Bellini
    Gauss
    Bizet
    Donizetti
    Mascagni
    Puccini
    Rossini
    ^Z
    Adams
    Bellini
    Bizet
    Donizetti
    Gauss
    Gounod
    Mascagni
    Mozart
    Puccini
    Rossini
    Strauss
    Verdi
    Wagner
    
    Σημείωση 1: Η συνάρτηση strcmp συγκρίνει αλφαβητικά δύο συμβολοσειρές (α, β), και επιστρέφει ανάλογα -1 (α < β), 0 (α = β), ή 1 (α > β). Ορίζεται στην string.h.

    Σημείωση 2: Ανάγνωση των συμβολοσειρών μέχρι το τέλος του αρχείου, αντιγραφή τους σε χώρο που έχει επιστραφεί από τη malloc, και αποθήκευσή του δείκτη σε μεταβλητή p τύπου char * μπορεί να γίνει ως εξής:

    	char buff[80];
    
    	while (fgets(buff, sizeof(buff), stdin)) {
    		p = strdup(buff);
    		...
    	}
    
    Η δήλωση της strdup βρίσκεται στην επικεφαλίδα string.h.

    Σημείωση 3: Ο ορισμός των παρακάτω δύο συναρτήσεων μπορεί να σας βοηθήσει στη δομή του προγράμματος:

    static void add_tree(struct s_btree **t, char *name);
    static void print_tree(struct s_btree *t);