二叉排序树

本题考察的是二叉树的建立，并且输出父节点的值。所以函数Insert的参数里多了一个int型的变量father，记录的是父节点的值。因为二叉排序树的新增节点都是在叶子处，所以root == NULL时，新建一个结点BTree(x)。

// runtime: 5ms
// space: 504K
#include <iostream>
using namespace std;

struct BTree {
    int data;
    BTree* leftChild;
    BTree* rightChild;
    BTree(int x) : data(x), leftChild(NULL), rightChild(NULL) {}
};

BTree* Insert(BTree* root, int x, int father) {
    if (root == NULL) {
        root =  new BTree(x);
        cout<< father <<endl;
    } else if (root->data > x) {
        root->leftChild = Insert(root->leftChild, x, root->data);
    } else {
        root->rightChild = Insert(root->rightChild, x, root->data);
    }
    return root;
}

int main() {
    int n;
    while (cin>> n) {
        BTree* root = NULL;
        for (int i = 0; i < n; ++i) {
            int x;
            cin>> x;
            root = Insert(root, x, -1); // 每次都从根开始，用-1表示
        }
    }
    return 0;
}