黑马程序员技术交流社区

标题: 二叉先序遍历 [打印本页]

---

作者: 瑞雪雄起    时间: 2015-9-28 16:42
标题: 二叉先序遍历
#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");
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2