Following code illustrates various binary tree traversal algorithms - both recursively and iteratively. All algorithms provided below are DFS algorithms.
Please note that recursive algorithm will also work on regular tree data structure (i.e. without parent and visited). However, iterative algorithms only works with following data structure:
Time Complexity: O(n) - for all algorithms
/* recursive pre order traversal */
void pre_order_traversal_recursive(tree2 *t)
{
if (t == NULL) {
return;
}
/* process node here */
printf ("%d ", t->data);
pre_order_traversal_recursive(t->left);
pre_order_traversal_recursive(t->right);
}
/* recursive in order traversal */
void in_order_traversal_recursive(tree2 *t)
{
if (t == NULL) {
return;
}
in_order_traversal_recursive(t->left);
/* process node here */
printf ("%d ", t->data);
in_order_traversal_recursive(t->right);
}
/* recursive post order traversal */
void post_order_traversal_recursive(tree2 *t)
{
if (t == NULL) {
return;
}
post_order_traversal_recursive(t->left);
post_order_traversal_recursive(t->right);
/* process node here */
printf ("%d ", t->data);
}
/* iterative pre order traversal */
void pre_order_traversal_iterative(tree2 *t)
{
while (t) {
/* condition to control type of traversal */
if (((t->left && !t->left->visited) || !t->left) &&
((t->right && !t->right->visited) || !t->right)) {
/* process node here */
printf("%d ", t->data);
}
/* actual tree traversal */
if (t->left && !t->left->visited) {
t = t->left;
} else if (t->right && !t->right->visited) {
t = t->right;
} else {
t->visited = 1;
t = t->parent;
}
}
}
/* iterative in order traversal */
void in_order_traversal_iterative(tree2 *t)
{
while (t) {
/* condition to control type of traversal */
if (((t->left && t->left->visited) || !t->left) &&
((t->right && !t->right->visited) || !t->right)) {
/* process node here */
printf("%d ", t->data);
}
/* actual tree traversal */
if (t->left && !t->left->visited) {
t = t->left;
} else if (t->right && !t->right->visited) {
t = t->right;
} else {
t->visited = 1;
t = t->parent;
}
}
}
/* iterative post order traversal */
void post_order_traversal_iterative(tree2 *t)
{
while (t) {
/*
** Following condition controls the type of tree traversal
** PRE ORDER : !t->left->visited and !t->right->visited
** IN ORDER : t->left->visited and !t->right->visited
** POST ORDER : t->left->visited and t->right->visited
*/
if (((t->left && t->left->visited) || !t->left) &&
((t->right && t->right->visited) || !t->right)) {
/* process node here */
printf("%d ", t->data);
}
/* actual tree traversal */
if (t->left && !t->left->visited) {
t = t->left;
} else if (t->right && !t->right->visited) {
t = t->right;
} else {
t->visited = 1;
t = t->parent;
}
}
}
Please note that recursive algorithm will also work on regular tree data structure (i.e. without parent and visited). However, iterative algorithms only works with following data structure:
typedef struct tree2_s {
u32 data;
struct tree2_s *left;
struct tree2_s *right;
struct tree2_s *parent;
u32 visited;
} tree2;
No comments:
Post a Comment