中序和后序列确定惟一的二叉树.c

数据结构课程设计的题目

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"Chang.h"
 
typedef struct qnode
{       
        char data;
        struct qnode  *leftchild;
        struct qnode  *rightchild;
}BiTreeNode;
int i;
void Visit(char  x)
{
	printf("%c ",x);
	
} 
#include"二叉树递归遍历.h"
BiTreeNode *Creat(char a[],char b[],int j,int k,int n)
{
	int m;  
	BiTreeNode  *r; 
	if(j<0||j>k||k>=n)return NULL;
	if(i>=0)
	{
		r=(BiTreeNode*)malloc(sizeof(BiTreeNode));
		r->data=a[i];
		for(m=j;m<=k;m++)
			if(b[m]==a[i])break; 
			i--;
			r->rightchild=Creat(a,b,m+1,k,n);
			r->leftchild=Creat(a,b,j,m-1,n);
	}
	return r;
}


















































int main()
{
    char a[100],b[100],n,k,j;
    BiTreeNode *root;
    while(scanf("%s",a)!=EOF)
    {
		//A和B分别为二叉树结点遍历的后序和中序结点序列 
		n=strlen(a);
		//扫描后序列的指针从数组末开始 
	    Chang(a,n,b);
	    a[n-1]='\0'; 
	    n--;
	    for(k=0;k<n;k++)
	    {
                          if(a[k]=='('||a[k]==')')
	                     {
                        for(j=k;j<n-1;j++)
	                      a[j]=a[j+1];
	                      n--;
                       }
        }
        printf("%d\n",n);
        printf("%s\n%s\n",b,a);
        i=n-1;
		root=Creat(b,a,0,n-1,n);
	   
		
		/*printf("\n"); 
		printf("中序遍历所构造的二叉树结点:\n"); 
		InOrder(root);
		printf("\n");
        printf("后序遍历所构造的二叉树结点:\n"); 
		PostOrder( root);
		printf("\n");*/
		printf("用凹入法表示法打印所构造的二叉树:\n");
		Print(root,0);
		
    }
    return 0;
}
//后序和中序构造与前序和中序惟一确定二叉树相同，只不过一个是用指针扫描前序序列，在中序中先找
//左孩子结点再找右孩子结点，而后序是从数组的末尾到头进行扫描，在中序中先找右孩子结点再找左孩子