二叉树的建立

张重 — Sat, 26 Apr 2008 01:15:00 GMT

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

struct tree{ struct tree *lchild; char data;
    struct tree *rchild;
};
struct stack{
    struct tree *data;
    struct stack *next;
}*top,*base;

void initstack(){
    base=(struct stack*)malloc(sizeof(struct stack));
    base->data = NULL;
    base->next = NULL;
    top=base;
}
void destroystack(){
    while (top!=base)
    {
        struct    stack * top;
        top = top->next;
        free(top);
    }
    free(base);
    base = 0;
}
void push(struct tree *T){
    struct stack *p;
    p=top;
    top=(struct stack*)malloc(sizeof(struct stack));
    top->data = T;
    top->next=p;
}
int empty()
{
    return top == base;
}
struct tree* pop(/*struct tree *T*/){
    struct tree* data = top->data;
    struct stack* temp = top;
    if(top==base)
    {
        return NULL; /*栈为空*/
    }
    top = top->next;
    free(temp);
    return data;
}

void build(struct tree** t, char** str)//递归方式
{
    if (!**str) return;
    if (**str=='#')
    {
        *t = NULL;
        (*str)++;
        return;
    }
    *t = (struct tree*)malloc(sizeof(struct tree));
    (*t)->data = **str;
    (*t)->lchild = NULL;
    (*t)->rchild = NULL;
    (*str)++;
    build(&(*t)->lchild, str);
    build(&(*t)->rchild, str);
}

void build1(struct tree** tr, char** str)//非递归
{
    char* curr = *str;
    struct tree** root = tr;
    struct tree** t = root;
    initstack();
    while (*curr&&(*curr!='#' ||!empty()))
    {
        while (*curr&&*curr!='#')
        {
            *t = (tree*)malloc(sizeof(struct tree));
            (*t)->lchild = NULL;
            (*t)->rchild = NULL;
            (*t)->data = *curr;
            curr++;
            push(*t);
            t = &((*t)->lchild);
        }
        if (!*curr) break;
        if (!empty())
        {
            t = &(pop()->rchild);
            curr++;
        }
    }
    destroystack();
    *tr = *root;
}

void creat(struct tree **t)
{
    char ch[20], *p;
    printf("input every elem:\n");
    scanf("%s",ch);
    p = ch;
    build1(t, &p);
}

void pre_visit(struct tree *T){
    initstack();
    while (T||!empty())
    {
        while (T!=NULL)
        {
            printf("%c",T->data);
            push(T);
            T=T->lchild;
        }
        if (!empty())
        {
            T=pop();
            T=T->rchild;
        }
    }
    destroystack();
}

void main(){
    struct tree *t;
    creat(&t);
    pre_visit(t);
}

张重 2008-04-26 09:15 发表评论

C++博客-跟你丫死磕-c++

二叉树的建立