7-1 建立二叉搜索树并查找父结点(PTA - 数据结构)

按输入顺序建立二叉搜索树，并搜索某一结点，输出其父结点。

输入格式:

输入有三行：
第一行是n值，表示有n个结点；
第二行有n个整数，分别代表n个结点的数据值；
第三行是x，表示要搜索值为x的结点的父结点。

输出格式:

输出值为x的结点的父结点的值。
若值为x的结点不存在，则输出：It does not exist.
若值为x的结点是根结点，则输出：It doesn't have parent.

输入样例:

2
20
30
20

输出样例:

It doesn't have parent.

###输入样例：

2
20
30
30

输出样例:

20

---

提交结果：?

---

思路分析：

? ? ? ? 创建树，查找元素，设置一个指针指向查找的结点的父节点。（这道题我自己写，提交全是段错误，然后喂给文心一言，给我改了一下，过了俩检查点，我自己在文心一言给出结果上面改，最后全过了，离谱！）

---

初始代码（段错误版）：含有老师PPT代码

//
// Created by DDD on 2023/12/20.
//
#include <stdio.h>
#include <malloc.h>

typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode;

void Init(BiTNode *t,int x){
    t->data = x;
    t->rchild = NULL;
    t->lchild = NULL;
}

BiTNode *insertNode(BiTNode *t,BiTNode *s){
    BiTNode *p,*q;
    if(t==NULL)
        return s;
    p = t;
    while (p){
        q = p;
        if(s->data == p->data)
            return t;
        if(s->data < p->data)
            p = p->rchild;
        else p = p->rchild;
    }
    if(s->data<q->data)
        q->lchild = s;
    else q->rchild = s;
    return t;
}

void Search(BiTNode *Head,int x){
    BiTNode *p,*q;
    p = Head;
    if(Head == NULL){
        printf("It does not exist.");
        return;
    }
    if(Head->data == x) {
        printf("It doesn't have parent.");
        return;
    }
    while(p){
        if(x == p->data){
            printf("%d",q->data);
            return;
        }
        q = p;
        if(x>p->data)
            p = p->rchild;
        else p=p->lchild;

    }
    printf("It does not exist.");
}

int main(){
    int n,x;
    scanf("%d",&n);
    BiTNode *SearchTree;
    scanf("%d",&x);
    Init(SearchTree,x);
    for (int i = 0; i < n-1; ++i) {
        scanf("%d",&x);
        BiTNode *insert = (BiTNode *) malloc(sizeof(BiTNode));
        Init(insert,x);
        SearchTree = insertNode(SearchTree,insert);
    }
    scanf("%d",&x);
    Search(SearchTree,x);
}

---

结果版代码：具有人工智能（人工+智能）的美感

#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode;

void Init(BiTNode *t, int x) {
    t->data = x;
    t->lchild = t->rchild = NULL;
}

BiTNode *insertNode(BiTNode *t, BiTNode *s) {
    if (t == NULL) {
        t = (BiTNode *)malloc(sizeof(BiTNode));
        Init(t, s->data);
        return t;
    }
    if (s->data < t->data) {
        t->lchild = insertNode(t->lchild, s);
    } else if (s->data > t->data) {
        t->rchild = insertNode(t->rchild, s);
    }
    else if(s->data == t->data){
        return t;
    }// If data is same, you may choose to insert or not, based on your requirements.
    return t;
}

void Search(BiTNode *Head, int x) {
    BiTNode *q;
    if (Head == NULL) {
        printf("It does not exist.\n");
        return;
    }
    if (Head->data == x) {
        printf("It doesn't have parent.\n");
        return;
    }
    BiTNode *p = Head;
    while (p) {
        if (x == p->data) {
            printf("%d\n", q->data);
            return;
        }
        q = p;
        if (x < p->data) {
            p = p->lchild;
        } else {
            p = p->rchild;
        }
    }
    printf("It does not exist.\n");
}

int main() {
    int n, x;
    scanf("%d", &n);
    BiTNode *root = NULL; // Initialize the root as NULL. This will be our SearchTree.
    scanf("%d", &x);
    root = (BiTNode *)malloc(sizeof(BiTNode)); // Allocate memory for the root node.
    Init(root, x); // Initialize the root node.
    for (int i = 0; i < n - 1; ++i) {
        scanf("%d", &x);
        BiTNode *insert = (BiTNode *)malloc(sizeof(BiTNode)); // Allocate memory for the new node.
        Init(insert, x); // Initialize the new node.
        root = insertNode(root, insert); // Insert the new node into the binary search tree.
    }
    scanf("%d", &x);
    Search(root, x);
    free(root);
    return 0;
}

---

return -1；