九度Online Judge 1467-二叉排序树【基于一维数组建树】

￡神魔★判官ぃ 2022-09-28 13:05 88阅读 0赞

题目1467：二叉排序树

时间限制：1 秒

内存限制：128 兆

特殊判题：否

提交：4279

解决：1732

**题目描述：**

二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树：

1. 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值；  
2. 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值；  
3. 左、右子树本身也是一颗二叉排序树。

现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。

**输入：**

输入包含多组测试数据，每组测试数据两行。  
第一行，一个数字N（N<=100），表示待插入的节点数。  
第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10^8。

**输出：**

输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值。

**样例输入：**

5
    2 5 1 3 4

**样例输出：**

-1
    2
    2
    5
    3

**来源：**

[2012年北京邮电大学计算机研究生机试真题][2012]

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    struct node
    {
    	int key;
    	int left, right ;
     } a[110];
     
     int shu[110];
    int main()
    {
    	int n;
    	while(scanf("%d",&n)!=EOF){
    		for(int i=0;i<n;i++){
    			scanf("%d",&shu[i]);
    		}
    		a[0].key=shu[0];
    		a[0].left=-1;
    		a[0].right=-1;
    		printf("-1\n");
    		for(int i=1;i<n;i++){
    			a[i].key=shu[i];
    			a[i].left=-1;
    			a[i].right=-1;
    			int size=-1;//¸¸½áµãµÄÏÂ±ê 
    			int temp=0;//µ±Ç°ËÑË÷µ½µÄ½Úµã 
    			
    			bool flag=false;
    			while(temp!=-1){
    				if(shu[i]<a[temp].key)
    				{
    					size=temp;
    					temp=a[temp].left;
    					flag=false;
    				}
    				else
    				{
    					size=temp;
    					temp=a[temp].right;
    					flag=true;
    				}
    			}
    			
    			if(flag==false)
    			{
    				a[size].left=i;
    			}
    			else
    			{
    				a[size].right=i;
    			}
    			
    			printf("%d\n",a[size].key); 
    			
    		}
    	}
    	return 0;
    }

[2012]: http://ac.jobdu.com/problemset.php?search=2012%E5%B9%B4%E5%8C%97%E4%BA%AC%E9%82%AE%E7%94%B5%E5%A4%A7%E5%AD%A6%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A0%94%E7%A9%B6%E7%94%9F%E6%9C%BA%E8%AF%95%E7%9C%9F%E9%A2%98