Skip to content

Instantly share code, notes, and snippets.

@eduardoleon
Last active November 12, 2019 19:54
Show Gist options
  • Save eduardoleon/f71190157cc45127946f6154e8f78d07 to your computer and use it in GitHub Desktop.
Save eduardoleon/f71190157cc45127946f6154e8f78d07 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <stdlib.h>
struct tree {
struct tree *left;
struct tree *right;
};
struct stack {
int state;
struct tree *current;
struct stack *next;
};
void create(struct stack **stack)
{
*stack = NULL;
}
void push(int state, struct tree *tree, struct stack **stack)
{
struct stack *new = malloc(sizeof (struct stack));
new->state = state;
new->current = tree;
new->next = *stack;
*stack = new;
}
int pop(int *state, struct tree **tree, struct stack **stack)
{
struct stack *old = *stack;
if (!old) return 0;
if (state) *state = old->state;
if (tree) *tree = old->current;
*stack = old->next;
free(old);
return 1;
}
void destroy(struct stack **stack)
{
while (pop(NULL, NULL, stack));
}
void make_tree(struct tree *nodes, int bound)
{
int twice = 2 * bound;
for (int i = 1; i < bound; i++) {
nodes[i].left = &nodes[2*i];
nodes[i].right = &nodes[2*i + 1];
}
for (int i = bound; i < twice; i++) {
nodes[i].left = NULL;
nodes[i].right = NULL;
}
}
int balanced(struct tree *tree)
{
int state;
struct stack *schedule;
struct stack *heights;
create(&heights);
create(&schedule);
push(0, tree, &schedule);
while (pop(&state, &tree, &schedule))
if (state) {
int m, n, p, q;
pop(&m, NULL, &heights);
pop(&n, NULL, &heights);
p = (m < n) ? m : n;
q = (m > n) ? m : n;
if (q - p > 1) {
destroy(&heights);
destroy(&schedule);
return 0;
}
push(q + 1, NULL, &heights);
}
else if (tree) {
push(1, NULL, &schedule);
push(0, tree->left, &schedule);
push(0, tree->right, &schedule);
}
else
push(0, NULL, &heights);
return 1;
}
void test(struct tree *tree)
{
if (balanced(tree))
printf("The tree is balanced.\n");
else
printf("The tree is not balanced.\n");
}
int main()
{
struct tree small[16];
struct tree large[64];
struct tree unbal;
make_tree(small, 8);
make_tree(large, 32);
unbal.left = &small[1];
unbal.right = &large[1];
test(unbal.left);
test(unbal.right);
test(&unbal);
}
datatype tree = Empty | Tree of tree * tree
datatype step = One | Many of tree
fun visit (m :: n :: ns, One :: ss) =
let
val p = Int.min (m, n)
val q = Int.max (m, n)
in
if q - p > 1 then false else visit (q + 1 :: ns, ss)
end
| visit (ns, Many Empty :: ss) = visit (0 :: ns, ss)
| visit (ns, Many (Tree (a, b)) :: ss) = visit (ns, Many a :: Many b :: One :: ss)
| visit _ = true
fun balanced xs = visit (nil, Many xs :: nil)
datatype step = Zero | One | Many of int
fun many (c, x, ss) = if x < c then Many (2*x) :: Many (2*x+1) :: One :: ss else Zero :: ss
fun make (c, b :: a :: us, One :: vs) = make (c, Tree (a, b) :: us, vs)
| make (c, us, Zero :: vs) = make (c, Empty :: us, vs)
| make (c, us, Many x :: vs) = make (c, us, many (c, x, vs))
| make (_, xs :: _, _) = xs
| make _ = Empty
val small = make (16, nil, Many 1 :: nil)
val large = make (64, nil, Many 1 :: nil)
val unbal = Tree (small, large)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment