/* trees.c
 *
 * Trees
 *
 */

#include "trees.h"

/* adds a node containing token, at or below p */
struct tnode *bintree_insert(struct tnode *p, char *t)
{
    int cond;

    if (p == NULL)
    {
        p = (struct tnode *) malloc(sizeof(struct tnode));
        p->text = t;
        p->count = 1;
        p->left = p->right = NULL;
    }
    else if ((cond = strcmp(t, p->text)) == 0)
        p->count++;
    else if (cond < 0) /* go to the left subtree */
        p->left = bintree_insert(p->left, t);
    else               /* go to the right subtree */
        p->right = bintree_insert(p->right, t);

    return p;
}

/* CLR: pre-order / prefix tree print */
void treeprint_prefix(struct tnode *p)
{
    if (p != NULL)
    {
        printf("%4d %s\n", p->count, p->text);
        treeprint_prefix(p->left);
        treeprint_prefix(p->right);
    }
}

/* LCR: in-order / infix tree print */
void treeprint_infix(struct tnode *p)
{
    if (p != NULL)
    {
        treeprint_infix(p->left);
        printf("%4d %s\n", p->count, p->text);
        treeprint_infix(p->right);
    }
}

/* LRC: post-order / postfix tree print */
void treeprint_postfix(struct tnode *p)
{
    if (p != NULL)
    {
        treeprint_postfix(p->left);
        treeprint_postfix(p->right);
        printf("%4d %s\n", p->count, p->text);
    }
}

int main(int argc, char **argv)
{
    struct tnode *root = NULL;

    char *tokens[] = { "Anything", "that", "can", "go", "wrong", "will",
                       "binary", "trees", "are", "useful",
                       "dreaming", "in", "digital", "living", "in", "realtime",
                       "thinking", "in", "binary", "talking", "in", "ip"};
    int i;
    for (i = 0; i < sizeof(tokens) / sizeof(char *); i++)
        root = bintree_insert(root, tokens[i]);

    treeprint_infix(root);

    return 0;
}