#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
char data;
Node *lchild;
Node *rchild;
}TNode;
typedef struct Stack
{
int top;
TNode *data[15];
}Stack;
void InOrder(TNode *root)
{
if(root!=NULL)
{
InOrder(root->lchild);
printf("%c",root->data);
InOrder(root->rchild);
}
}
void PostOrder(TNode *root)
{
if(root!=NULL)
{
PostOrder(root->lchild);
PostOrder(root->rchild);
printf("%c",root->data);
}
}
void PreOrder(TNode *root)
{
Stack *s=(Stack *)malloc(sizeof(Stack));
s->top=-1;
TNode *p=root;
while(p!=NULL||s->top>-1)
{
if(p!=NULL)
{
printf("%c\n",p->data);
s->top++;
s->data[s->top]=p;
p=p->lchild;
}
else if(s->top>-1)
{
p=s->data[s->top];
p=p->rchild;
s->top--;
}
else break;
}
}
TNode * createTree()
{
char *str="A(B(D(H,),E(,I)),C(F,G(J,)))";
printf("二叉树的序列:%s\n",str);
TNode *root=NULL;
TNode *node;
int tag;
Stack *s=(Stack *)malloc(sizeof(Stack));
s->top=-1;
char ch=*str;
while(ch!='\0')
{
switch(ch)
{
case '(': {tag=0;s->top++;s->data[s->top]=node;break;}
case ')': {s->top--;break;}
case ',': {tag=1;break;}
default:
{
node=(TNode *)malloc(sizeof(TNode));
node->data=ch;
node->lchild =NULL;
node->rchild =NULL;
if(root==NULL)
{
root=node;
}
switch(tag)
{
case 0:{s->data[s->top]->lchild=node;break;}
case 1:{s->data[s->top]->rchild=node;break;}
}
break;
}
}
ch=*(++str);
}
return root;
}
void main()
{
TNode *root=createTree();
PreOrder(root);
InOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
}
|
|
收藏
淘帖
踩
