二叉树的基本操作（遍历与参数计算）

 

递归遍历：前序、中序、后序

非递归遍历：前序、中序、后序、层序

分治法：计算节点数、计算层高、构造联赛

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODE 100
//--------------------------------------------------------------------------------

struct tree_node_t
{
    char item;
    struct tree_node_t *l;
    struct tree_node_t *r;
};


struct tree_node_t* tree_init(void)
{
    struct tree_node_t *root = malloc(sizeof(struct tree_node_t) * MAX_NODE);
    struct tree_node_t *p;
    
    p = root + 0;
    p->item = 'a';
    p->l = root + 1;
    p->r = root + 2;

    p = root + 1;
    p->item = 'b';
    p->l = root + 3;
    p->r = root + 4;

    p = root + 2;
    p->item = 'c';
    p->l = root + 5;
    p->r = root + 6;

    p = root + 3;
    p->item = 'd';
    p->l = NULL;
    p->r = NULL;

    p = root + 4;
    p->item = 'e';
    p->l = NULL;
    p->r = NULL;

    p = root + 5;
    p->item = 'f';
    p->l = NULL;
    p->r = NULL;

    p = root + 6;
    p->item = 'g';
    p->l = NULL;
    p->r = NULL;

    return root;
}

void tree_free(struct tree_node_t *p)
{
    free(p);
}

void tree_visit(struct tree_node_t *p)
{
    printf("%c \n", p->item);
}

void tree_pre1(struct tree_node_t *p)
{
    tree_visit(p);
    if(p->l != NULL) tree_pre1(p->l);
    if(p->r != NULL) tree_pre1(p->r);
}

void tree_in1(struct tree_node_t *p)
{
    if(p->l != NULL) tree_in1(p->l);
    tree_visit(p);
    if(p->r != NULL) tree_in1(p->r);
}

void tree_post1(struct tree_node_t *p)
{

    if(p->l != NULL) tree_post1(p->l);
    if(p->r != NULL) tree_post1(p->r);
    tree_visit(p);
}

//--------------------------------------------------------------------------------

#define ITEM 1
#define TREE 2
struct m_node_t
{
    struct node_t
    {
        char item;
        struct tree_node_t *link;
    }node;
    int type;
};

struct m_node_t *top, *bottom, *cur;

void stack_init(void)
{
    top = malloc(sizeof(struct m_node_t) * MAX_NODE);
    bottom = cur = top + MAX_NODE -1;
}

void stack_free(void)
{
    free(top);
}

void stack_push(struct tree_node_t *p, int type)
{
    if(type == ITEM)
    {
        cur->node.item = p->item;
    }
    else
    {
        cur->node.item = p->item;
        cur->node.link = p;
    }
    cur->type = type;
    cur--;
}

int stack_pop(struct tree_node_t **p)
{
    static struct tree_node_t node;

    cur++;
    if(cur->type == ITEM)
    {
        node.item = cur->node.item;
        *p = &node;
        return ITEM;
    }
    else
    {
        *p = cur->node.link;
        return TREE;
    }
}

int stack_empty(void)
{
    return (bottom == cur)? 1:0;
}

int stack_print(void)
{
    struct m_node_t *p = cur;

    printf(" stack:");

    while(p++ != bottom)
    {
        if(p->type == ITEM)
        {
            printf(" %c ", p->node.item);
        }
        else
        {
            printf("(%c) ", p->node.link->item);
        }
    }

    printf("\n");
}

void tree_pre2(struct tree_node_t *root)
{
    struct tree_node_t *p = root;

    stack_push(p, TREE);

    while(!stack_empty())
    {
        if(stack_pop(&p) == ITEM)
        {
            tree_visit(p);
        }
        else
        {
            if(p->r != NULL)stack_push(p->r, TREE);
            if(p->l != NULL)stack_push(p->l, TREE);
            stack_push(p, ITEM);
        }
        stack_print();
    }
}

void tree_in2(struct tree_node_t *root)
{
    struct tree_node_t *p = root;

    stack_push(p, TREE);

    while(!stack_empty())
    {
        if(stack_pop(&p) == ITEM)
        {
            tree_visit(p);
        }
        else
        {
            if(p->r != NULL)stack_push(p->r, TREE);
            stack_push(p, ITEM);
            if(p->l != NULL)stack_push(p->l, TREE);

        }
        stack_print();
    }
}

void tree_post2(struct tree_node_t *root)
{
    struct tree_node_t *p = root;

    stack_push(p, TREE);

    while(!stack_empty())
    {
        if(stack_pop(&p) == ITEM)
        {
            tree_visit(p);
        }
        else
        {
            stack_push(p, ITEM);
            if(p->r != NULL)stack_push(p->r, TREE);
            if(p->l != NULL)stack_push(p->l, TREE);
        }
        stack_print();
    }
}

//--------------------------------------------------------------------------------

struct m_node_t *q_top, *q_bottom, *q_put, *q_get;

void queue_init(void)
{
    q_top = malloc(sizeof(struct m_node_t) * MAX_NODE);
    q_bottom = q_put = q_get = q_top + MAX_NODE -1;
}

void queue_free(void)
{
    free(q_top);
}

void queue_put(struct tree_node_t *p, int type)
{
    if(type == ITEM)
    {
        q_put->node.item = p->item;
    }
    else
    {
        q_put->node.item = p->item;
        q_put->node.link = p;
    }
    q_put->type = type;

    if(q_put == q_top)
    {
        q_put = q_bottom;
    }
    else
    {
        q_put--;
    }
}

int queue_get(struct tree_node_t **p)
{
    static struct tree_node_t q_node;
    int ret;

    if(q_get->type == ITEM)
    {
        q_node.item = q_get->node.item;
        *p = &q_node;
        ret = ITEM;
    }
    else
    {
        *p = q_get->node.link;
        ret = TREE;
    }

    if(q_get == q_top)
    {
        q_get = q_bottom;
    }
    else
    {
        q_get--;
    }
    return ret;

}

int queue_empty(void)
{
    return (q_put == q_get)? 1:0;
}

int queue_print(void)
{
    struct m_node_t *p = q_get;

    printf(" queue:");

    while(p != q_put)
    {
        if(p->type == ITEM)
        {
            printf(" %c ", p->node.item);
        }
        else
        {
            printf("(%c) ", p->node.link->item);
        }

        if(p == q_top)
        {
            p = q_bottom;
        }
        else
        {
            p--;
        }
    }

    printf("\n");
}

void tree_level(struct tree_node_t *root)
{
    struct tree_node_t *p = root;

    queue_put(p, TREE);

    while(!queue_empty())
    {
        if(queue_get(&p) == ITEM)
        {
            tree_visit(p);
        }
        else
        {
            queue_put(p, ITEM);
            if(p->l != NULL)queue_put(p->l, TREE);
            if(p->r != NULL)queue_put(p->r, TREE);
        }
        queue_print();
    }
}

//--------------------------------------------------------------------------------

int tree_node_count(struct tree_node_t *root)
{
    int n;
    if(root == NULL) return 0;

    n = tree_node_count(root->l) + tree_node_count(root->r) + 1;

    return n;
}

//--------------------------------------------------------------------------------

int tree_node_heigh(struct tree_node_t *root)
{
    int n;
    int nl,nr;
    
    if(root == NULL) return 0;

    nl = tree_node_heigh(root->l);
    nr = tree_node_heigh(root->r);

    n = (nl > nr)? nl: nr + 1;

    return n;
}

//--------------------------------------------------------------------------------

char a[20] = {'A', 'M', 'P', 'L', 'E'};
struct tree_node_t t_tree[100];
int t_node_count;

void t_tree_init(void)
{
    int i;
//    for(i= 0; i < 20; i++)

//        a[i] = 'a' + i;


    t_node_count = 0;
}

struct tree_node_t *t_node_new(char item, struct tree_node_t *l, struct tree_node_t *r)
{
    struct tree_node_t *p = &t_tree[t_node_count];

    p->item = item;
    p->l = l;
    p->r = r;

    t_node_count++;

    return p;
}


struct tree_node_t *t_tree_create(char a[], int s, int e)
{
    int m;
    char max;

    struct tree_node_t *l,*r;

    if(s == e) return t_node_new(a[s], NULL, NULL);

    m = (s+e)/2;

    if(m > s)
    {
        printf("s - m %d - %d\n", s, m);
    }
    else
    {
        printf("m - e %d - %d\n", m + 1, e);
    }

    l = t_tree_create(a, s, m);
    r = t_tree_create(a, m + 1, e);

    max = (l->item > r->item) ? l->item: r->item;
    return t_node_new(max, l, r);
}

//--------------------------------------------------------------------------------

int main()
{
    struct tree_node_t *p;

    p = tree_init();

    printf("-----------------------------------pre-----------------------------------\n");
    tree_pre1(p);
    printf("\n");

    printf("-----------------------------------in------------------------------------\n");
    tree_in1(p);
    printf("\n");

    printf("-----------------------------------post----------------------------------\n");
    tree_post1(p);
    printf("\n");

    stack_init();

    printf("-----------------------------------pre-----------------------------------\n");
    tree_pre2(p);
    printf("\n");

    printf("-----------------------------------in------------------------------------\n");
    tree_in2(p);
    printf("\n");

    printf("-----------------------------------post----------------------------------\n");
    tree_post2(p);
    printf("\n");

    stack_free();

    queue_init();
    printf("-----------------------------------level---------------------------------\n");
    tree_level(p);
    printf("\n");

    printf("-----------------------------------count---------------------------------\n");
    printf("tree_node_count = %d\n", tree_node_count(p));

    printf("-----------------------------------heigh---------------------------------\n");
    printf("tree_node_heigh = %d\n", tree_node_heigh(p));

    tree_free(p);

    printf("-----------------------------------tournament----------------------------\n");
    t_tree_init();
    p = t_tree_create(a, 0, 4);
    tree_level(p);
}