题解 | #二叉排序树#

#include<iostream>
using namespace std;
int arr[101];
typedef struct BSTNode {
    int data;
    struct BSTNode* left;
    struct BSTNode* right;
}BSTNode, * BSTree;
void Insert_BST(BSTree& t, int k) {
    if (t == NULL) {
        t = (BSTNode*)malloc(sizeof(BSTNode));
        t->data = k;
        t->left = t->right = NULL;
        return;//return不是直接结束的好像，递归结束有问题
    }
    else if (t->data > k) {
        Insert_BST(t->left, k);
    }
    else {
        Insert_BST(t->right, k);
    }

}
void findPar(BSTree t, int k, int &p)//注意father是引用的
{
    
    /*if (t->data == k) {
        return;
    }
    else if (t->data > k) {
        findPar(t->left, k, p);
        p = t->data;

    }
    else {
        findPar(t->right, k, p);
        p = t->data;
    }这里递归我忘记了递归是从底层开始逐层往上返回的，所以最后这样写最后的father都是2
    */
    //用非递归方式，而且找路径而已非递归即可
    while (t->data != k) {
        p = t->data;
        if (t->data > k) {
            t = t->left;
        }
        else {
            t = t->right;
        }
    }




}
int main() {
    int N;
    while (cin >> N && N) {
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }
        BSTree T = NULL;//初始化
        Insert_BST(T, arr[0]);
        cout << -1 << endl;
        for (int i = 1; i < N; i++) {
            Insert_BST(T, arr[i]);
            int father=0;//注意初始化
            findPar(T, arr[i], father);
            cout << father << endl;
        }



    }


}