西北工业大学NOJ数据结构—018创建二叉树的二叉链表（以先序和中序为线索）

若是只给出一个先序或者中序或者后序序列，是能够构建多棵树的，可是若给出中序和前序或者给出中序和后序，则必定能够构建惟一的二叉树，由于中序数列最前的节点必定是根节点，而后再前序数列中按照根节点能够将序列分为两部分，左侧为左子树，右侧为右子树，经过递归调用能够依次构建二叉树。函数

不过如果给出前序和后序，则不必定能够构建惟一二叉树，由于根节点位置一样是不肯定的。code

解题思路：blog

1.构建一个递归函数，来构建二叉树，这个函数应该有如下特性：递归

1）每次调用都应该从前序数列中获得一个字符做为当前的根节点，并先把此节点的左右子树初始化为NULL字符串

2）而后从中序数列中找到以前的到的字符的位置iget

3）以中序数列中i左边的序列做为次级中序序列来递归构建左子树string

4）以中序数列中i右边的序列做为次级中序序列来递归构建右子树io

5）递归的3和4应该在i左侧或右侧没有字符时中止,即找到一个左右相碰的位置（挺复杂的函数对吧,,,,,）class

（在纸上写了一下才找到确切的位置）二叉树

2.剩下的就是后序输出

3.为了实现1的函数，须要另外写以一个函数，一个用来在中序序列中找到某个字符的位置，并返回这个位置；

ok了万事大吉搞代码（づ￣3￣）づ╭❤～

#include<stdio.h>  
#include<stdlib.h> 
#include<string.h> 

struct BinTree  
{  //定义二叉链表来储存二叉树
    char data;  
    struct BinTree *left;  
    struct BinTree *right;  
}; 

char pre[100];
char mid[100];//定义两个字符串来储存前序和中序

int lentgh(char *t)//获得一个字符串的长度
{
	int i=0;
	while(1)
	{
		if(!t[i])
			break;
		i++;
	}
	return i;
}

int find(int l,int r,char mi)//输入一个元素和查找范围，在中序序列中找到这个元素
{//并返回这个元素在中序列中的位置i
	int i;
	for(i=l;i<=r;i++)
	{
		if(mid[i]==mi)
			return (i);
	}
	return 0;
}

struct BinTree *creat(int l,int r,int *i)//建立二叉树，选择输入范围和在前序数列中的位置
{
	struct BinTree *cur;//abdfgceh和bfdgaceh序列
	cur=(struct BinTree*)malloc(sizeof(struct BinTree));
	cur->data=pre[*i];//根节点就是前序数列的元素
	cur->left=NULL;
	cur->right=NULL;
	(*i)++;
	int midnumber;
	midnumber=find(l,r,cur->data);//在中序中找到这个元素所在的位置
	if(midnumber>l)//若是这个位置比左极限大，就生成这个节点的左子树，直到相等就不建立了
		cur->left=creat(l,midnumber-1,i);//生成左子树，查找范围变为从左极限到中序数列位置减一
	if(midnumber<r)
		cur->right=creat(midnumber+1,r,i);//生成右子树，查找范围变为从中序数列位置加一到右极限
	return cur; 
}

void PostOrd(struct BinTree *T)
{//后序输出二叉树
	if(T->left)
		PostOrd(T->left);
	if(T->right)
		PostOrd(T->right);
	printf("%c",T->data);
}

int main()
{	
	memset(pre,0,sizeof(pre));
	memset(mid,0,sizeof(mid));//清零
	gets(pre);
	gets(mid);//依此输入前序和中序列
	int l=0,r=0;
	int len=lentgh(pre);//获得长度
	r=len-1;//最右位置为长度减一
	int i=0;
	struct BinTree *T;
	T=creat(l,r,&i);//建立二叉树
	PostOrd(T);//后序输出
	return 0;
}