洛谷P1087 [NOIP2004 普及组] FBI 树c语言

洛谷P1087 [NOIP2004 普及组] FBI 树

二叉树的后序遍历

• 思想
• 代码

[1] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。
　　[2] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。

注释：本题就是用到了二叉树。解题时思路清晰、目的明确就好了，主要分以下几个步骤：
1、以字符串的形式录入原始串s；
2、按题意求欲设的01串的长度：pow(2,n);
3、将字符串s转换为01串：全0为B，全1为I，混合串为F；
4、递归创建二叉树；
5、后序遍历二叉树并输出。

#include
#include
#include
#include
#define max 10000
int num[max];
char s[max];

//定义结构体
struct Node{
	Node *left,*right;
	char c;
};

//将字符数组转为整型数组 
void strtoint(char *s,int *num,int len)
{
	int i = 0;
	for(i = 0; i < len ; i++)
	{
		num[i] = s[i] - '0';
	}
}

//后序遍历：递归遍历左右子树 
void lastdfs(Node *head)
{
	if(head->left)
		lastdfs(head->left);
	if(head->right)
		lastdfs(head->right);
	printf("%c",head->c);
}

//判断并返回01串是否为全0，全1，混合串 
char FBI(int *num,int begin,int end)
{
	int sum = 0;
	int i;
	for(i = begin;i <= end; i++)
	{
		sum += num[i];
	}
	if(sum == 0) return'B';
	else if(sum == end - begin + 1) return 'I';
	else return 'F';	
}

//创建二叉树 
Node *buildtree(int *num, int begin, int end)
{
	//char c = FBI(num,begin,end);
	Node *p = (Node*)malloc(sizeof(Node));
	//p->c = c;
	if(begin < end)//说明子串不为空 
	{
		int mid = (begin + end) / 2;
		p->left = buildtree(num,begin,mid);
		p->right = buildtree(num,mid + 1,end);
	}
	else{
		//若子串为空，左右子树赋NULL 
		p->left = NULL;
		p->right = NULL;
	}
	return p;
}

int main()
{
	int n;
	scanf("%d",&n);
	getchar();//处理回车 
	scanf("%s",s);
	int len = pow(2,n);//01串的长度为2的n次方 
	strtoint(s,num,len);
	Node *head = buildtree(num,0,len - 1);
	lastdfs(head);
	return 0;
}