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

istvh

递归遍历：前序、中序、后序
非递归遍历：前序、中序、后序、层序
分治法：计算节点数、计算层高、构造联赛
#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
//        a = '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, 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);
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/99982/showart_2126443.html