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

Η διάσχιση ενός δένδρου μπορεί να γίνει με τους παρακάτω τρόπους ανάλογα με τη σειρά επίσκεψης των κόμβων:

Προδιαταγμένη διάσχιση (preorder traversal)

επίσκεψη της ρίζας
επίσκεψη του αριστερού υποδένδρου
επίσκεψη του δεξιού υποδένδρου

Μεταδιαταγμένη διάσχιση (postorder traversal)

επίσκεψη του αριστερού υποδένδρου
επίσκεψη του δεξιού υποδένδρου
επίσκεψη της ρίζας

Ενδοδιαταγμένη διάσχιση (inorder traversal)

επίσκεψη του αριστερού υποδένδρου
επίσκεψη της ρίζας
επίσκεψη του δεξιού υποδένδρου

Επιπεδοδιαταγμένη διάσχιση (level order traversal)

επίσκεψη των κόμβων από πάνω προς τα κάτω

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

Προδιαταγμένη διάσχιση

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);
}