1. 建立二叉搜索树并查找父结点

1.1 实验内容

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

1.2 实验目的

掌握二叉树的建立，熟悉二叉树中节点的搜索。

1.3 程序清单

▶

Code

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

/* 节点定义 */
typedef struct node_s {
    int             data;
    struct node_s  *left;
    struct node_s *right;
} node_t;

/**
 * @brief 创建新节点
 * 
 * @param data 节点值
 * @return node_t* 节点指针
 */
node_t* create_node(int data)
{
    node_t *node = (node_t *)malloc(sizeof(node_t));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

/**
 * @brief 向二叉搜索树插入结点, 跳过重复值
 * 
 * @param root     根节点指针
 * @param data 待插入的节点值
 * @return node_t* 根节点指针
 */
node_t* insert(node_t *root, int data)
{
    if (root == NULL) {
        return create_node(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    } else {
        // 跳过重复
    }

    return root;
}

/**
 * @brief 查找值为 x 的结点的父结点
 * 
 * @param root 根节点指针
 * @param x 节点值
 */
void find_parent(node_t *root, int x)
{
    if (root == NULL) {
        printf("It does not exist.\r\n");
        return;
    }

    if (root->data == x) {
        printf("It doesn't have parent.\r\n");
        return;
    }

    node_t *parent = root;
    node_t *current = (x < root->data) ? root->left : root->right;

    while (current != NULL) {
        if (current->data == x) {
            printf("%d\r\n", parent->data);
            return;
        }
        parent = current;

        if (x < current->data) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    printf("It does not exist.\r\n");
}

/**
 * @brief 释放树的内存
 * 
 * @param root 根节点指针
 */
void free_tree(node_t* root)
{
    if (root == NULL) {
        return;
    }

    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main()
{
    int     n;
    int     x;
    int value;

    node_t *root = NULL;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &value);
        root = insert(root, value);
    }

    scanf("%d", &x);
    find_parent(root, x);

    free_tree(root);
    return 0;
}

1.4 调试步骤

1. 输入测试数据

2
20
30
20

2. 程序输出

It doesn't have parent.

1.5 分析与思考

• 空间复杂度：$O(n \log n)$

• 时间复杂度：$O(n)$

2. 二叉搜索树的删除操作

2.1 实验内容

给出一棵二叉搜索树（没有相同元素），请输出其删除部分元素之后的层序遍历序列。删除结点的策略如下：

1. 如果一个结点是叶子结点，则直接删除；

2. 如果一个结点的左子树不为空，则将该结点的值设置为其左子树上各结点中的最大值，并继续删除其左子树上拥有最大值的结点；

3. 如果一个结点的左子树为空但右子树不为空，则将该结点的值设置为其右子树上各结点中的最小值，并继续删除其右子树上拥有最小值的结点；

2.2 实验目的

掌握二叉树的删除操作。

2.3 程序清单

▶

Code

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

#define MAX 100

/* 节点定义 */
typedef struct node_s {
    int             data;
    struct node_s  *left;
    struct node_s *right;
} node_t;

/**
 * @brief 创建新节点
 * 
 * @param data 节点值
 * @return node_t* 节点指针
 */
node_t* create_node(int data)
{
    node_t *node = (node_t *)malloc(sizeof(node_t));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

/**
 * @brief 向二叉搜索树插入结点, 跳过重复值
 * 
 * @param root     根节点指针
 * @param data 待插入的节点值
 * @return node_t* 根节点指针
 */
node_t* insert(node_t *root, int data)
{
    if (root == NULL) {
        return create_node(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    } else {
        // 跳过重复
    }

    return root;
}

/**
 * @brief 查找左子树中的最大值
 * 
 * @param root 根节点指针
 * @return int 最大值
 */
int find_max(node_t *root)
{
    while (root->right != NULL) {
        root = root->right;
    }
    return root->data;
}

/**
 * @brief 查找右子树中的最小值
 * 
 * @param root 根节点指针
 * @return int 最小值
 */
int find_min(node_t *root)
{
    while (root->left != NULL) {
        root = root->left;
    }
    return root->data;
}

/**
 * @brief 策略删除节点
 * 
 * @param root 根节点指针
 * @param data 节点值
 * @return node_t* 根节点指针
 */
node_t* delete_node(node_t *root, int data)
{
    if (root == NULL) {
        return NULL;
    }

    if (data < root->data) {
        root->left = delete_node(root->left, data);
    }
    else if (data > root->data) {
        root->right = delete_node(root->right, data);
    }
    else {
        // 1. 叶子结点
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        // 2. 左子树不为空
        else if (root->left != NULL) {
            int max_val = find_max(root->left);
            root->data = max_val;
            root->left = delete_node(root->left, max_val);
        }
        // 3. 左子树为空但右子树不为空
        else {
            int min_val = find_min(root->right);
            root->data = min_val;
            root->right = delete_node(root->right, min_val);
        }
    }

    return root;
}

/**
 * @brief BFS 层序遍历
 * 
 * @param root 根节点指针
 */
void level_order(node_t *root)
{
    if (root == NULL) {
        return;
    }

    node_t *queue[MAX];
    int      front = 0;
    int       rear = 0;

    queue[rear++] = root;

    int first = 1;  // 控制输出空格

    while (front < rear) {
        node_t *curr = queue[front++];

        if (first) {
            printf("%d", curr->data);
            first = 0;
        } else {
            printf(" %d", curr->data);
        }

        if (curr->left) {
            queue[rear++] = curr->left;
        }

        if (curr->right) {
            queue[rear++] = curr->right;
        }
    }

    printf("\r\n");
}

/**
 * @brief 释放树的内存
 * 
 * @param root 根节点指针
 */
void free_tree(node_t* root)
{
    if (root == NULL) {
        return;
    }

    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main()
{
    int     n;
    int     x;
    int value;

    node_t *root = NULL;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &value);
        root = insert(root, value);
    }
    scanf("%d", &x);

    for (int i = 0; i < x; i++) {
        scanf("%d", &value);
        root = delete_node(root, value);
    }

    level_order(root);

    free_tree(root);
    return 0;
}

2.4 调试步骤

1. 输入测试数据

7
4 2 1 3 6 5 7
2
3 6

2. 程序输出

4 2 5 1 7

2.5 分析与思考

• 空间复杂度：$O(n \log n + x \log n)$

• 时间复杂度：$O(n)$