首页 > ACM题库 > HDU-杭电 > HDU 3999-The order of a Tree-字典树-[解题报告]HOJ
2015
04-14

HDU 3999-The order of a Tree-字典树-[解题报告]HOJ

The order of a Tree

问题描述 :

As we know,the shape of a binary search tree is greatly related to the order of keys we insert. To be precisely:
1.  insert a key k to a empty tree, then the tree become a tree with
only one node;
2.  insert a key k to a nonempty tree, if k is less than the root ,insert
it to the left sub-tree;else insert k to the right sub-tree.
We call the order of keys we insert “the order of a tree”,your task is,given a oder of a tree, find the order of a tree with the least lexicographic order that generate the same tree.Two trees are the same if and only if they have the same shape.

输入:

There are multiple test cases in an input file. The first line of each testcase is an integer n(n <= 100,000),represent the number of nodes.The second line has n intergers,k1 to kn,represent the order of a tree.To make if more simple, k1 to kn is a sequence of 1 to n.

输出:

There are multiple test cases in an input file. The first line of each testcase is an integer n(n <= 100,000),represent the number of nodes.The second line has n intergers,k1 to kn,represent the order of a tree.To make if more simple, k1 to kn is a sequence of 1 to n.

样例输入:

4

1 3 4 2

样例输出:

1 3 2 4

/*
分析:
    又是一个月黑风高的夜晚,终于。。。又可以刷题了,囧~,
十几分钟就能敲完的代码,白天愣是被打断了3、4次,终于敲完
了。。。
    水~
    其实就是把这个树构成,然后遍历一遍输出,遍历顺序就
是先root、然后左子树、然后右子树。
    我这个建树的思想来自写的字典树,所以就分类到字典树
里面了。囧~~
                                              2013-10-22
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"

int n;
struct Tree
{
	struct Tree *left,*right;
	int num;
};
struct Tree *root;
int ans[100111],k;

void insert(int aim)
{
	struct Tree *now,*next;
	now=root;
	while(now->num)
	{
		if(aim<now->num)
		{
			if(now->left==NULL)
			{
				next=(struct Tree *)malloc(sizeof(struct Tree));
				next->left=next->right=NULL;
				next->num=0;
				now->left=next;
				now=next;
			}
			else	now=now->left;
		}
		else
		{
			if(now->right==NULL)
			{
				next=(struct Tree *)malloc(sizeof(struct Tree));
				next->left=next->right=NULL;
				next->num=0;
				now->right=next;
				now=next;
			}
			else	now=now->right;
		}
	}
	now->num=aim;
}
void solve(struct Tree *now)
{
	ans[k++]=now->num;
	if(now->left!=NULL)	solve(now->left);
	if(now->right!=NULL)solve(now->right);
}
int main()
{
	int i;
	int temp;
	while(scanf("%d",&n)!=-1)
	{
		if(n<=0)	continue;
		root=(struct Tree *)malloc(sizeof(struct Tree));
		root->left=root->right=NULL;
		root->num=0;
		for(i=0;i<n;i++)	{scanf("%d",&temp);insert(temp);}

		k=0;
		solve(root);
		printf("%d",ans[0]);
		for(i=1;i<k;i++)	printf(" %d",ans[i]);
		printf("\n");
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/8531809


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。