二叉查找树-插入结点，返回父节点（2012北邮机试）

题目：二叉排序树
现在给你N个关键字值各部相同的节点，要求你按顺序插入一个初始为空的二叉排序树中，
每次插入成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。
输入格式：
第一行：一个数字N（N<=100）,表示带插入的节点数。
第二行：N个互不相同的正整数，表示要顺序插入结点的关键字值，这些值不超过108.
输出格式：
输出共N行,每次插入节点后，该节点对应的父亲节点的关键字值。
Example:
Inputs:
5
2 5 1 3 4
Outputs:
-1
2
2
5
3
【分析】之前写过一个二叉排序的基本操作函数，这里只需要稍作修改即可

代码：

/*
Project: 二叉查找树(又称二叉排序树，简称BST)
Date:    2019/01/29
Author:  Frank Yu
题目：二叉排序树
现在给你N个关键字值各部相同的节点，要求你按顺序插入一个初始为空的二叉排序树中，
每次插入成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。
输入格式：
第一行：一个数字N（N<=100）,表示带插入的节点数。
第二行：N个互不相同的正整数，表示要顺序插入结点的关键字值，这些值不超过108.
输出格式：
输出共N行,每次插入节点后，该节点对应的父亲节点的关键字值。 
Example:
Inputs:
5
2 5 1 3 4
Outputs:
-1
2
2
5
3
【分析】之前写过一个二叉排序的基本操作函数，这里只需要稍作修改即可

BST_Insert(BSTree &T, TElemType data,int par)  参数T，二叉查找树根节点 参数data,节点数据域，参数par，当前结点的父亲节点的数据
                                               作用：插入数据data,返回父节点值 

CreateBSTree(BSTree &T,int N) 参数T，二叉查找树根节点，参数N，二叉查找树结点个数 
                              作用：调用BST_Insert，创建二叉查找树
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<iostream>
#define TElemType char
using namespace std;
//链式二叉查找树数据结构
typedef struct BSTNode
{
    TElemType data;//数据域
    struct BSTNode *lchild, *rchild;//左右孩子
}BSTNode, *BSTree;
//********************************基本操作函数********************************//
//二叉查找树插入 参数T，二叉查找树根节点 作用：插入数据data,返回父节点值 
int BST_Insert(BSTree &T, TElemType data,int par)
{
    if (T == NULL)//树为空
    {
        T = (BSTree)malloc(sizeof(BSTNode));//申请结点空间
        T->data = data;                     //赋值
        T->lchild = NULL;                   //左右孩子为空
        T->rchild = NULL;
        return par;                         //返回父节点关键字值 
    }
    else if (data < T->data)               //比当前节点数据小，插入左子树
    {
        return BST_Insert(T->lchild,data,T->data);
    }
    else                                   //这里规定二叉查找树可以重复，等于及大于当前结点时，插入右子树
    {
        return BST_Insert(T->rchild,data,T->data);
    }
}
//**********************************功能实现函数*****************************//
//调用BST_Insert进行二叉查找树的创建
void CreateBSTree(BSTree &T,int N)
{
    int key=0;int par=0;
    for (int i=0;i<N;i++)
    {
        scanf("%d", &key);
        par=BST_Insert(T,key,-1);//插入key值节点
        printf("%d\n",par); 
    }
}
//主函数
int main()
{
    BSTree T = NULL;
    int N=0;
    scanf("%d", &N);
    CreateBSTree(T,N);
    return 0;
}

结果截图：