题目描述

题目描述
二叉排序树，也称为二叉查找树。

可以是一颗空树，也可以是一颗具有如下特性的非空二叉树：

若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值；
若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值；
左、右子树本身也是一颗二叉排序树。
现在给你 N 个关键字值各不相同的节点。

要求你将这些节点按顺序插入一个初始为空树的二叉排序树中。

每次成功插入一个节点后，求其相应的父亲节点的关键字值，如果没有父亲节点，则输出 −1。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int l[N],r[N],p[N],v[N],idx;/p[i] 是第i个节点的父节点，v[i]是第i个节点的值
int dfs(int u,int i)//u为待比较的点，i为当前需要存入的节点
{
    if(u == 0)return i;
    if(v[i] < v[u])
    {
        l[u] = dfs(l[u],i);
        p[l[u]] = u;
    }else
    {
        r[u] = dfs(r[u],i);
        p[r[u]] = u;
    }
    return u;
}
int main()
{
    cin >> n;
    v[0] = -1;
    for(int i = 1;i <= n;i++)
    {
        int x;
        cin >> x;
        v[i] = x;
        if(i == 1)p[i] = 0;
        else
        dfs(1,i);
        cout << v[p[i]]<<endl;
    }
}