treetobt.cpp

树转换为二叉树

#include <stdio.h>
#include <malloc.h>
#define SIZE 100
typedef struct node 
{
	char data;
	struct node * LC;
	struct node * RC;
}Node;
typedef struct stack
{
	struct node *p[SIZE];
	int top;
}Stack;
void PUSH(Node *p1,Stack *s1)
{
	s1->p[++s1->top]=p1;
}
void POP(Node *p2,Stack *s2)
{
	s2->top--;
}
Node * TtoBT(char c[])
{
	int i;
	Node * Root,*pre,*q,*p;
	Stack *s;
	q=(Node *)malloc(sizeof(Node));
	s=(Stack *)malloc(sizeof(Stack));
	s->top=-1;
	Root=pre=q;
	Root->data=c[0];
	Root->LC=Root->RC=NULL;
	PUSH(Root,s);
	i=1;
	while(c[i]!='\0')
	{
		if(c[i]=='(')
		{
			p=(Node *)malloc(sizeof(Node));
			q=p;
			q->LC=NULL;
			q->RC=NULL;
			i++;
			q->data=c[i];
			pre->LC=q;
			pre=q;
			if(c[i+1]=='(')
				PUSH(q,s);
		}
		else if(c[i]==',')
		{
			p=(Node*)malloc(sizeof(Node));
			q=p;
			q->LC=NULL;
			q->RC=NULL;
			i++;
			q->data=c[i];
			pre->RC=q;
			pre=q;
			if(c[i+1]=='(')
				PUSH(q,s);
		}
		else if(c[i]==')')
		{
			pre=q=s->p[s->top];
			POP(q,s);
		}
		i++;
	}
	return Root;
}
void MidOrder(Node *r)
{
	Stack * ss;
	Node *q;
	q=r;
	ss=(Stack*)malloc(sizeof(Stack));
	ss->top=-1;
	printf("转化为二叉树后中序遍历输出结果为：");
	do
	{
        if(q->LC!=NULL)
		{
			ss->p[++ss->top]=q;
		    q=q->LC;
		}
		else
		{
			printf("%c",q->data);
			if(q->RC!=NULL)
				q=q->RC;
			else 
			{
				if(ss->top!=-1)
				{
					q=ss->p[ss->top];
				    ss->top--;
				    q->LC=NULL;
				}
				else break;
			}
		}
		
	}while(q!=NULL);
	printf("\n");
}
void main()
{
	char c[100];
	gets(c);
	Node *R;
	R=TtoBT(c);
    MidOrder(R);
}