Skip to content

Instantly share code, notes, and snippets.

@athas
Created July 27, 2022 15:37
Show Gist options
  • Save athas/1f234711af8909faf424336ad0904da1 to your computer and use it in GitHub Desktop.
Save athas/1f234711af8909faf424336ad0904da1 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
double seconds() {
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return ts.tv_sec + ts.tv_nsec/1000000000.0;
}
struct node {
int data;
struct node* parent;
struct node* left;
struct node* right;
};
struct node* mk_tree(struct node *parent, int d) {
if (d == 0) {
return NULL;
} else {
struct node *x = malloc(sizeof(struct node));
x->data = 0;
x->parent = parent;
x->left = mk_tree(x, d-1);
x->right = mk_tree(x, d-1);
return x;
}
}
void print_tree(int d, struct node* x) {
if (x) {
print_tree(d+1, x->left);
for (int i = 0; i < d; i++) {
printf(" ");
}
printf("%d\n", x->data);
print_tree(d+1, x->right);
}
}
void visit(struct node *x) {
x->data++;
}
void walk_tree_withstack(struct node *x) {
if (x) {
visit(x);
walk_tree_withstack(x->left);
walk_tree_withstack(x->right);
}
}
void walk_tree_stackfree(struct node *x) {
struct node *cur = x;
struct node *prev = NULL;
while (cur) {
struct node *next = cur->parent;
if (prev == cur->parent) {
visit(cur);
if (cur->left) {
next = cur->left;
} else if (cur->right) {
next = cur->right;
}
} else if (prev == cur->left) {
if (cur->right) {
next = cur->right;
}
}
prev = cur;
cur = next;
}
}
void free_tree(struct node* x) {
if (x) {
free_tree(x->left);
free_tree(x->right);
free(x);
}
}
int main(int argc, char** argv) {
if (argc != 2) {
fprintf(stderr, "Usage: %s N\n", argv[0]);
exit(1);
}
int d = atoi(argv[1]);
double a,b;
a = seconds();
struct node *t = mk_tree(NULL, d);
b = seconds();
printf("Constructing:\t\t%fs\n", b-a);
a = seconds();
walk_tree_withstack(t);
b = seconds();
printf("Walking with stack:\t%fs\n", b-a);
a = seconds();
walk_tree_stackfree(t);
b = seconds();
printf("Walking without stack:\t%fs\n", b-a);
a = seconds();
free_tree(t);
b = seconds();
printf("Freeing:\t\t%fs\n", b-a);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment