데이터 구조 274: 중간 순서 로 두 갈래 정렬 트 리 를 옮 겨 다 닙 니 다.

문제 설명 은 정수 순 서 를 입력 하고 이 진 트 리 를 만 든 다음 중간 순 서 를 옮 겨 다 닙 니 다.
첫 번 째 행위 정 수 를 입력 하 는 개수 n 을 입력 하 십시오. 두 번 째 줄 은 구체 적 인 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;
}