题解 | #二叉排序树#

#include <iostream>
using namespace std;
struct Bitree {
    Bitree* left;
    Bitree* right;
    int val;//节点的值
};
Bitree* creatnode(int data) { //创建二叉树节点
    Bitree* node = (Bitree*)malloc(sizeof(Bitree));
    node->val = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}
Bitree* paixuCreat(Bitree* root, int value,int* parent) //用parent记录父亲节点的值
{ 
    if (root == NULL) { //当前节点为空
        return creatnode(value);
    }
    if (value < root->val) {
        *parent = root->val;
        root->left = paixuCreat(root->left, value, parent);
    } else {
        *parent = root->val;
        root->right = paixuCreat(root->right, value, parent);
    }
    return root;
}
int main() 
{
    Bitree* root = NULL;
    int N, value;
    cin >> N;
    int* parentNodes = (int*)malloc(N * sizeof(int));//创建数组以保存父亲节点的值
    parentNodes[0] = -1;//第一个值默认为-1
    for (int i = 0; i < N; i++) {
        cin >> value;
        int parent = -1;
        root = paixuCreat(root, value, &parent);
        parentNodes[i] = parent;//记录父亲节点
    }
    for (int i = 0; i < N; i++) {
        cout << parentNodes[i] << endl; //输出父亲节点
    }
}
// 64 位输出请用 printf("%lld")

创建排序二叉树的同时用parent变量记录其父节点然后保存在数组里，最后再输出