/* Mesurer la hauteur d'un arbre binaire mutable avec l'algorithme Joseph M. Morris Traversing binary trees simply and cheaply Information Processing Letters 9(5), 1979 */ #include <stdlib.h> #include <assert.h> int max(int x, int y) { return x > y ? x : y; } typedef struct T* tree; struct T { tree left, right; }; int morris(tree t) { int d = 0, h = 0; while (t != NULL) { if (t->left == NULL) { t = t->right; h = max(h, ++d); } else { tree p = t->left; int delta = 1; while (p->right != NULL && p->right != t) { p = p->right; delta++; } if (p->right == NULL) { p->right = t; t = t->left; h = max(h, ++d); } else { p->right = NULL; t = t->right; d -= delta; } } } return h; } // tests tree Node(tree left, tree right) { tree t = (tree)malloc(sizeof(struct T)); t->left = left; t->right = right; return t; } int height(tree t) { if (t == NULL) return 0; return 1 + max(height(t->left), height(t->right)); } tree left(tree t, int n) { if (n == 0) return t; return left(Node(t, NULL), n-1); } tree right(tree t, int n) { if (n == 0) return t; return right(Node(NULL, t), n-1); } tree randomtree(int n) { if (n == 0) return NULL; int n1 = rand() % n; return Node(randomtree(n1), randomtree(n-1-n1)); } int main() { for (int n = 0; n < 100; n++) { assert(morris(left(NULL, n)) == n); assert(morris(right(NULL, n)) == n); tree t = randomtree(n); assert(height(t) == morris(t)); } } /* Local Variables: */ /* compile-command: "gcc morris.c -o morris" */ /* End: */