hdu 3999The order of a Tree

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=3999

本题为简单二叉排序树，先按排序树创建树，然后先序遍历二叉树，输出的时候最后一个数字后面没有空格。

数组实现：

#include<stdio.h>
#include<string.h>
#define N 100005
int tree[N],left[N],right[N],a[N],num,flg;//tree数组用来保存树节点的值，left，right数组用来保存结点的左右子树，
void insert(int index,int x)
{
	if( x <= tree[index] )//当根结点比x的值大 的时候。
	{
		if(left[index] == -1)//当根结点左子树为空的时候。
			left[index] = flg;
		else
			insert(left[index],x);//左子树不为空时继续遍历左子树
	}
	else
		{
			if(right[index] == -1)//当右子树为空时
				right[index] = flg;
			else
				insert(right[index],x);//当右子树不为空的时候
		}
}
void PreOrderTraverse(int index)//先序遍历二叉排序树
{
	a[num++] = tree[index];
	if(left[index] != -1)
		PreOrderTraverse(left[index]);
	if(right[index] != -1)
		PreOrderTraverse(right[index]);
}
int main()
{
	int n,i,x,root;
	while(~scanf("%d",&n))
	{
		//初始化树的所有结点都为空。
		memset(left,-1,sizeof(left));
		memset(right,-1,sizeof(right));
		root = -1;
		flg = 0;
		for(i = 0; i< n; i++)
		{
			scanf("%d",&x);
			if(root == -1)
				tree[++root] = x;
			else
			{
				tree[++flg] = x;
				insert(root,x);
			}
		}
		num = 0;
		PreOrderTraverse(root);
		printf("%d",a[0]);
		for(i = 1; i <= n -1; i++)
			printf(" %d",a[i]);
		printf("\n");
	}
	return 0;
}

 

动态创建二叉树排序树

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int data;
	struct node *left;
	struct node *right;
};
int b[100005],num,n;
void delete_tree(node *t)
{
	if(t->left)
		delete_tree(t->left);
	if(t->right)
		delete_tree(t->left);
	free(t);
}
node* insert(node *t,int x)
{
	if(t)
	{
		if(x < t->data)
			t->left = insert(t->left,x);
		else
			t->right = insert(t->right,x);
	}
	else
	{
		t = (node*)malloc(sizeof(node));
		t->data = x;
		t->left = t->right = NULL;
	}
	return t;
}
void PreOrderTraverse(node *t)
{
	if(t == NULL)
		return ;
	b[num++] = t->data;
	PreOrderTraverse(t->left);
	PreOrderTraverse(t->right);
	free(t);
}
node *create(node *t)
{
	int i,x;
	for(i = 0; i < n; i++)
	{
		scanf("%d",&x);
		t = insert(t,x);
	}
	return t;
}
int main()
{
	int i;
	node *root;
	while(~scanf("%d",&n))
	{
		root = NULL;
		root = create(root);
		num = 0;
		PreOrderTraverse(root);
		printf("%d",b[0]);
		for(i = 1; i < n; i++)
			printf(" %d",b[i]);
		printf("\n");
	}
	return 0;
}