#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
typedef struct node { | |
int value; | |
struct node *left; | |
struct node *right; | |
} node; | |
int depth(node *tree) { | |
if (!tree) | |
return 0; | |
int l = depth(tree->left); | |
int r = depth(tree->right); | |
return 1 + (l > r ? l : r); | |
} | |
int depth2(node *tree) { | |
int retval; | |
int l; | |
int r; | |
if (!tree) { | |
retval = 0; | |
return retval; | |
} | |
l = depth(tree->left); | |
r = depth(tree->right); | |
retval = 1 + (l > r ? l : r); | |
return retval; | |
} | |
typedef struct depth_stack { | |
int l; | |
int r; | |
node *tree; | |
int resume_point; | |
struct depth_stack *parent; | |
int retval; | |
int returned_val; | |
} depth_stack; | |
int depth3(node *tree) { | |
depth_stack *pStack = malloc(sizeof(depth_stack)); | |
pStack->parent = NULL; | |
pStack->tree = tree; | |
if (!pStack->tree) { | |
pStack->retval = 0; | |
return pStack->retval; | |
} | |
pStack->l = depth(pStack->tree->left); | |
pStack->r = depth(pStack->tree->right); | |
pStack->retval = 1 + (pStack->l > pStack->r ? pStack->l : pStack->r); | |
return pStack->retval; | |
} | |
int depth4(node *tree) { | |
depth_stack *tmp_stack = malloc(sizeof(depth_stack)); | |
tmp_stack->tree = tree; | |
depth_stack *pStack = NULL; | |
push: | |
tmp_stack->parent = pStack; | |
pStack = tmp_stack; | |
if (!pStack->tree) { | |
pStack->retval = 0; | |
goto pop; | |
} | |
// Recurse left call | |
pStack->resume_point = 1; // will pick up back here | |
tmp_stack = malloc(sizeof(depth_stack)); | |
*tmp_stack = *pStack; | |
tmp_stack->tree = pStack->tree->left; | |
goto push; | |
recur1done: | |
pStack->l = pStack->returned_val; | |
// Recurse right call | |
pStack->resume_point = 2; // will pick up back here | |
tmp_stack = malloc(sizeof(depth_stack)); | |
*tmp_stack = *pStack; | |
tmp_stack->tree = pStack->tree->right; | |
goto push; | |
recur2done: | |
pStack->r = pStack->returned_val; | |
pStack->retval = 1 + (pStack->l > pStack->r ? pStack->l : pStack->r); | |
goto pop; | |
pop: | |
if (pStack->parent) { | |
tmp_stack = pStack; | |
pStack = tmp_stack->parent; | |
pStack->returned_val = tmp_stack->retval; | |
free(tmp_stack); | |
if (pStack->resume_point == 1) goto recur1done; | |
if (pStack->resume_point == 2) goto recur2done; | |
} | |
return pStack->retval; | |
} | |
int main() | |
{ | |
node *myTree = calloc(1, sizeof(*myTree)); | |
for (int i = 1; i < 150; ++i) { | |
node *newTree = calloc(1, sizeof(*newTree)); | |
newTree->left = myTree; | |
myTree = newTree; | |
} | |
printf("%d\n", depth(myTree)); | |
printf("%d\n", depth2(myTree)); | |
printf("%d\n", depth3(myTree)); | |
printf("%d\n", depth4(myTree)); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment