On Dec 5, 9:34 pm, gaijinco <[EMAIL PROTECTED]> wrote:
> I remember reading in a book about an algorithm that can read a series
> of ordered numbers from a file and constructing a binary tree from it.
>
> The book is lost, the books I do have doesn't mention anything about
> it.
>
I worked this out once. Haven't seen it in a book. Here's a code.
#include <stdio.h>
#include <stdlib.h>
/* Good for a terranode tree. */
#define LOG_N 40
/* Canonical tree node. */
typedef struct node {
int i;
struct node *l, *r;
} *node_t;
/* Stack and pointers for tree fragments. */
static node_t stk[LOG_N], *p = stk, *root = stk;
/* Add a node to a complete binary tree with fragments stored in the
stack. */
void add_node(node_t n)
{
p[0] = n;
if (p > stk && p[-1] != NULL) {
if (p > root) root = p;
n->l = p[-1], p[-1] = NULL, p = stk;
}
else
for (++p; p[0] != NULL; ++p)
p[0]->r = p[-1], p[-1] = NULL;
}
/* text graphics tree printer */
void print_tree(int level, node_t tree, int left_p)
{
static char branch_p[LOG_N];
int i;
for (i = 0; !left_p && i < level; ++i)
printf(branch_p[i] ? "| " : " ");
if (tree == NULL) { printf("*\n"); return; }
branch_p[level] = left_p;
printf("+%3d", tree->i);
print_tree(level+1, tree->r, 1);
print_tree(level+1, tree->l, 0);
}
int main(void)
{
int i;
node_t q;
/* read SORTED data */
while (scanf("%d", &i) == 1) {
q = malloc(sizeof *q);
q->i = i;
q->l = q->r = NULL;
add_node(q);
}
/* Collect fragments. Generally necessary unless n = 2^k - 1. */
for (q = *root, i = root - stk - 1; i >= 0 && q->r == NULL; --i)
if (stk[i] != NULL)
q->r = stk[i], q = stk[i], stk[i] = NULL;
print_tree(0, *root, 0);
return 0;
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
