二叉树

/*
 *二叉树采用二叉链表结构表示。设计并实现如下算法：
 *后序递归建树，先序非递归遍历该树。
 */
#include <stdio.h>
#include <stdlib.h>

#define ERROR 0
#define OK 1
#define OVERFLOW 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 100

typedef char TElemType;
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

typedef BiTree ElemType;
typedef struct {
    ElemType *base;
    ElemType *top;
    int stacksize;
}SqStack;

int InitStack (SqStack *S)
{
    S->base=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!S->base)
         exit (OVERFLOW);
    S->top=S->base;
    S->stacksize=STACK_INIT_SIZE;
    return OK;
}

int StackEmpty (SqStack S)
{
    if (S.base==S.top)
        return 1;
    else
        return 0;
}

int Push (SqStack *S, ElemType e)
{
    if (S->top - S->base >= S->stacksize)
    {
        S->base=(ElemType *)realloc(S->base,
                              (S->stacksize + STACKINCREMENT)* sizeof(ElemType));
        if (!S->base)
            exit (OVERFLOW);
        S->top=S->base+S->stacksize;
        S->stacksize+=STACKINCREMENT;
    }
    *S->top++ = e;
    return OK;
}

int Pop(SqStack *S,ElemType *e)
{
    if (S->top==S->base)
        return ERROR;
    *e=*(--S->top);
    return OK;
}

void CreateBiTree (BiTree *T)
{
    TElemType temp;
    scanf ("%c", &temp);
    if (temp==' ')
    {
        *T=NULL;
    }
    else
    {
        if (!((*T)=(BiTree)malloc(sizeof(BiTNode))))
            exit (1);
        CreateBiTree (&((*T)->lchild));
        CreateBiTree (&((*T)->rchild));
        (*T)->data=temp;
    }
}

void Traverse (BiTree T)
{
    BiTree P;
    SqStack S;
    InitStack (&S);
    P=T;
    while (P||!StackEmpty(S))
    {
        if (P)
        {
            printf ("%c", P->data);
            Push(&S,P);
            P=P->lchild;
        }
        else
        {
            Pop(&S,&P);
            P=P->rchild;
        }
    }
}

int main ()
{
    BiTree T;
    CreateBiTree (&T);
    printf ("\n");
    Traverse (T);
    printf ("\n");
    printf ("end");
    getch ();
    return 0;
}

/* 二叉树采用二叉链表结构表示。设计并实现如下算法：
* 输入某棵二叉树的广义表形式，建立该二叉树，并按层次遍历该二叉树
*/

#include
#include
#include

#define ERROR 0
#define OK 1
#define OVERFLOW 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 100
#define MAXQSIZE 100
typedef char TElemType;
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

typedef BiTree ElemType;
typedef struct {
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;

typedef struct {
ElemType *base;
int front;
int rear;
}SqQueue;

void InitQueue (SqQueue *Q)
{
Q->base=(ElemType *)malloc(MAXQSIZE * sizeof(ElemType));
if (!Q->base)
exit (0);
Q->front=0;
Q->rear=0;
}

int QueueLength (SqQueue Q)
{
return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE;
}

void EnQueue (SqQueue *Q, ElemType e)
{
if ((Q->rear+1)%MAXQSIZE==Q->front)
return;
Q->base[Q->rear]=e;
Q->rear=(Q->rear+1)%MAXQSIZE;
}

void DeQueue (SqQueue *Q, ElemType *e)
{
if (Q->front==Q->rear)
return;
*e=Q->base[Q->front];
Q->front=(Q->front+1)%MAXQSIZE;
}

int InitStack (SqStack *S)
{
S->base=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!S->base)
exit (OVERFLOW);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}

int StackEmpty (SqStack S)
{
if (S.base==S.top)
return 1;
else
return 0;
}

int Push (SqStack *S, ElemType e)
{
if (S->top - S->base >= S->stacksize)
{
S->base=(ElemType *)realloc(S->base,
(S->stacksize + STACKINCREMENT)* sizeof(ElemType));
if (!S->base)
exit (OVERFLOW);
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++ = e;
return OK;
}

int Pop(SqStack *S,ElemType *e)
{
if (S->top==S->base)
return ERROR;
*e=*(--S->top);
return OK;
}

void Create (BiTree *T)
{
char temp;
BiTree P=NULL,Q=NULL;
SqStack S;
int status=0;
*T=NULL;
InitStack (&S);
scanf ("%c",&temp);
while (temp!='#')
{
switch (temp) {
case '(' :
status=1; //准备处理左子树
if (P!=NULL)
Push (&S,P);
break;
case ')' :
Pop (&S,&P);
break;
case ',' :
status=2;
break;
default :
P=(BiTree)malloc(sizeof(BiTNode));
P->data=temp;
P->lchild=NULL;
P->rchild=NULL;
if (*T==NULL)
*T=P;
else
{
if (status==1)
{
Pop (&S,&Q);
Q->lchild=P;
Push (&S,Q);
}
else if (status==2)
{
Pop (&S,&Q);
Q->rchild=P;
Push (&S,Q);
}
}
}
scanf ("%c",&temp);
}
}

void Traverse (BiTree T)
{
SqQueue Q;
BiTree P;
InitQueue (&Q);
P=T;
EnQueue (&Q, T);
while (QueueLength (Q)!=0)
{
DeQueue (&Q, &P);
printf ("%c", P->data);
if (P->lchild!=NULL)
EnQueue (&Q, P->lchild);
if (P->rchild!=NULL)
EnQueue (&Q, P->rchild);
}
}

int main ()
{
BiTree T;
Create (&T);
Traverse (T);
system ("pause");
return 0;
}