データ構造274:中間順序は、二叉順序のツリーを巡回します.

11631 ワード

問題の説明は整数のシーケンスを入力して、二叉の並べ替えツリーを作成して、中から順に巡回します.
入力説明は、第1の行為の整数の個数nを入力し、第2の行は具体的なn個の整数である.
出力の説明は、二叉の順序付けツリーを作成し、中間巡回の結果を出力します.
入力例5 1 6 5 9 8
出力例1 5 6 8 9
#include
#include
typedef struct node
{
	int key;
	struct node *lchild,*rchild;
}bst;
bst *root;
bst *insert(bst *t,bst *s)
{
	bst *f,*p;
	p=t;
	while(p!=NULL)
	{
		f=p;
		if(s->key==p->key) return t;
		else if(s->key<p->key) p=p->lchild;
		else p=p->rchild;
	}
	if(t==NULL) return s;
	if(s->key<f->key) f->lchild=s;
	else f->rchild=s;
	return t;
}
bst *tree(int k[],int n)
{
	int i;
	bst *t,*s;
	t=NULL;
	for(i=0;i<n;i++)
	{
		s=(bst*)malloc(sizeof(bst));
		s->lchild=NULL;s->rchild=NULL;
		s->key=k[i];
		t=insert(t,s);
	}
	return t;
}
void inorder(bst *p)
{
	bst *stack[100];
	bst *s;
	s=p;
	int top=-1;
	while(top!=-1||s!=NULL)
	{
		while(s!=NULL)
		{
			top++;
			stack[top]=s;
			s=s->lchild;
		}
		s=stack[top];
		top--;
		printf("%d ",s->key);
		s=s->rchild;
	}
}
int main()
{
	root=(bst*)malloc(sizeof(bst));
	int n,i;
	scanf("%d",&n);
	int k[n];
	for(i=0;i<n;i++) scanf("%d",&k[i]);
	root=tree(k,n);
	inorder(root);
	return 0;
}