二叉排序树

1、在递归建树的过程中返回父节点

// 在递归建树的过程中返回父节点
#include <iostream>
using namespace std;
struct node{
    int val;
    node* left, *right;
};
node* newNode(int v){
    node* Node = new node;
    Node->val = v;
    Node->left = Node->right = NULL;
    return Node;
}
node* insert(node*& root, int x, int father){
    if(root == NULL){
        root = newNode(x);
        cout << father << endl;
    }
    if(x < root->val){
        root->left = insert(root->left, x, root->val);
    }else if(x > root->val){
        root->right = insert(root->right, x, root->val);
    }
    return root;
}
int main(){
    int N;
    while(cin >> N){
        node* root = NULL;
        while(N--){
            int x;
            cin >> x;
            insert(root, x, -1);
        }
    }
    return 0;
}

2、插入元素后在树中查找对应元素的父节点再输出

#include <iostream>
using namespace std;
struct node{
    int val;
    node* left, *right;
};
node* newNode(int v){
    node* Node = new node;
    Node->val = v;
    Node->left = Node->right = NULL;
    return Node;
}
void insert(node*& root, int x){
    if(root == NULL){
        root = newNode(x);
        return;
    }
    if(x < root->val){
        insert(root->left, x);
    }else{
        insert(root->right, x);
    }
}
node* SearchFather(node* root, int x){
    if(root == NULL) return root;
    if(root->left != NULL && root->left->val == x) return root;
    if(root->right != NULL && root->right->val == x) return root;
    if(x < root->val){
        return SearchFather(root->left, x);
    }else{
        return SearchFather(root->right, x);
    }
    return root;
}
int main(){
    int N;
    while(cin >> N){
        node* root = NULL;
        while(N--){
            int x;
            cin >> x;
            insert(root, x);
            node* father = SearchFather(root, x);
            father != NULL ? cout << father->val << endl : cout << -1 << endl;
        }
    }
    return 0;
}