本题考察的是二叉树的建立,并且输出父节点的值。所以函数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; }