データ構造274:中間順序は、二叉順序のツリーを巡回します.
11631 ワード
問題の説明は整数のシーケンスを入力して、二叉の並べ替えツリーを作成して、中から順に巡回します.
入力説明は、第1の行為の整数の個数nを入力し、第2の行は具体的なn個の整数である.
出力の説明は、二叉の順序付けツリーを作成し、中間巡回の結果を出力します.
入力例5 1 6 5 9 8
出力例1 5 6 8 9
入力説明は、第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;
}