数据结构与算法实验题6.1 鼹鼠掘土挑战赛

鼹鼠们排成一列，由第一个开始向下挖洞，并待在洞中。第二只与第一只相比，若能力

值大的胜者，则向右下方挖洞。否则向左下方。接下来的鼹鼠们以此类推，若比洞中所在鼹
鼠能力值高，则向右下方走，否则向左下方。

总经理想知道，经过挑战赛之后，鼹鼠们的位置是怎样的。
位置表达式规则为：“<左子树表达式>根节点<右子树表达式>”,如左子树不存在,则只
输出“根节点<右子树表达式>”，右子树同理。
例如上图，可以表示为<2>3<<4>5<7>>
★数据输入
输入第一行为一个正整数N (2 < N < 1000)，表示有N 个鼹鼠。
第二行为N 个整数bi(0 <bi < 10000)，表示每个鼹鼠的能力值。
★数据输出
输出鼹鼠们的位置表达式
输入示例输出示例
5
3 5 2 7 4
<2>3<<4>5<7>>

此题就是二叉搜索树+中序输出算法的应用，理解算法后，就容易多了

注意题目：若能力值大的胜者，则向右下方挖洞！

19:36:12

#include<stdio.h>
#include<stdlib.h>

typedef struct node *btlink;
struct node
{
    int data;
    btlink left;
    btlink right;
}node;

int o=0,max=-1,n,t=0,key=0;


btlink insert(btlink root,int x)
{
    btlink p;
    p=(btlink)malloc(sizeof(node));
    p->data=x;
    p->left=p->right=NULL;
    if(root==NULL)
    {
        root=p;
    }
    else if(root->data>=x)
    {
        root->left=insert(root->left,x);
    }
    else
    {
        root->right=insert(root->right,x);
    }
    return root;
}

void InOrder(btlink root,int max)
{
    
    if(root!=NULL)
    {
        if(o>0)
        {
            printf("<");
            key++;
        }
        {
            o++;
          InOrder(root->left,max);
          printf("%d",root->data);
          InOrder(root->right,max);
        }
        if(t<key)
        {
            //printf(" t=%d ",t);
            printf(">");
            t++;
        }
    }
}


int main()
{
    int i;
    int x;
    btlink BT;
    BT=(btlink)malloc(sizeof(node));
    BT=NULL;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&x);
        if(x>max)
            max=x;
        BT=insert(BT,x);
    }
    InOrder(BT,max);
    printf("
");
    return 0;
}

        

AC code