二叉排序树——寻找父节点

【问题描述】二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1. 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值； 2. 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值； 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。
【输入形式】输入包含多组测试数据，每组测试数据两行。第一行，一个数字N（N<=100），表示待插入的节点数。第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10^8。
【输出形式】输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值。
【样例输入】
5
2 5 1 3 4
【样例输出】
-1
2
2
5
3

分析：
1 . 首先第一个数据作为根结点
2 .然后根据左小右大的关系存放输入的数据 以此构建一棵树
3.找到每个结点的父结点 打印输出该结点的值

实现：
利用结构体构建结点 利用类构建树

struct BiNode
{
    int data;//如果怕超出范围 就用long int
    struct BiNode*lchild,*rchild;
};
class BiSortTree
{
public:
    BiSortTree(int a[],int n);
    BiNode*InsertBST(int x)//用来构建树的函数
    {
        return InsertBST(root,x);
    }
private:
    BiNode*InsertBST(BiNode*bt,int x);//利用同名的私有函数进行递归调用
    BiNode*root;
};

构建树

BiNode*BiSortTree::InsertBST(BiNode*bt,int x)
{
    if(bt==NULL)//如果为空 添加该结点
    {
        BiNode*s=new BiNode;
        s->data=x;
        s->lchild=NULL;
        s->rchild=NULL;
        bt=s;
        return bt;
    }
    else if(bt->data>x)//把小的存到左子树上
    {
        if(bt->lchild==NULL)//这里有个小技巧 如果该结点的子结点为空 
            cout<<bt->data<<endl;//那么该结点bt就为要插入的子结点的父节点 直接打印输出就好了
        bt->lchild=InsertBST(bt->lchild,x);//添加子结点
    }
    else
    {
        if(bt->rchild==NULL)//做法同上 这里是存到右子树
            cout<<bt->data<<endl;
        bt->rchild=InsertBST(bt->rchild,x);
    }
    return bt;
}

利用公有函数 BiSortTree 传递数据

BiSortTree::BiSortTree(int a[],int n)
{
    root=NULL;
    cout<<-1<<endl;
    for(int i=0;i<n;i++)
    {
        root=InsertBST(root,a[i]);//循环输入x
    }
}

主函数

int main()
{
    int n;
    cin>>n;
    int data[n];
    for(int i=0;i<n;i++)
        cin>>data[i];
    BiSortTree bst(data,n);
}

在下是一名小白 如果有不恰当的地方 欢迎指正