数据结构 实验报告-5

第一题 建立二叉搜索树并查找父结点：

一、实验内容：

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

二、实验目的：

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

三、程序清单：

▶

Code

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

typedef struct BSTNode* Position;
typedef Position BSTree;
struct BSTNode {
    int Data;
    BSTree Left;
    BSTree Right;
};

void InsertBST(BSTree* T, int val) {
    if (!*T) {
        *T = (BSTree)malloc(sizeof(struct BSTNode));
        (*T)->Data = val;
        (*T)->Left = NULL;
        (*T)->Right = NULL;
    }
    else if (val < (*T)->Data)
        InsertBST(&(*T)->Left, val);
    else if (val > (*T)->Data)
        InsertBST(&(*T)->Right, val);
}

void CreateBST(BSTree* T) {
    int i = 1, n;
    scanf("%d", &n);
    *T = NULL;
    int val;
    for (i = 1; i <= n; i++) {
        scanf("%d", &val);
        InsertBST(&*T, val);
    }
}

int flag = 0;
void SearchBST(BSTree P, const BSTree* T, int find) {
    if ((*T)->Data == find) {
        printf("%d", P->Data);
        flag = 1;
        return;
    }
    else if (find < (*T)->Data && (*T)->Left != NULL) {
        SearchBST(*T, &(*T)->Left, find);
        return;
    }
    else if (find > (*T)->Data && (*T)->Right != NULL) {
        SearchBST(*T, &(*T)->Right, find);
        return;
    }
}

int main() {
    int find;
    BSTree T;
    CreateBST(&T);
    scanf("%d", &find);
    if (T->Data == find) {
        printf("It doesn't have parent.\n");
        return 0;
    }
    SearchBST(NULL, &T, find);
    if (flag == 0)
        printf("It does not exist.\n");
    return 0;
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；

第二题 二叉搜索树的删除操作：

一、实验内容：

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

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

二、实验目的：

掌握二叉树的删除操作;

三、程序清单：

▶

Code

#include <stdio.h>
#include <stdlib.h>
 
typedef struct tree {
    struct tree* left, * right;
    int data;
} *Tree, tree;
 
Tree In(Tree gen, Tree parent, int x);
Tree Out(Tree gen, int x);
void bl(Tree root);
 
int main() {
    int p;
    int q;
    int m;
 
    Tree gen = NULL;
 
    scanf("%d", &p);
    for (; p != 0; p--) {
        scanf("%d", &q);
        gen = In(gen, gen, q);
    }
 
    scanf("%d", &m);
    for (;m!=0;m--) {
        scanf("%d", &q);
        gen = Out(gen, q);
    }
    bl(gen);
}
 
Tree In(Tree gen, Tree parent, int x) {
    if (!gen) {
        Tree mid = (Tree)malloc(sizeof(tree));
        mid->data = x;
        mid->left = mid->right = NULL;
        return mid;
    }
    if (x < gen->data)
        gen->left = In(gen->left, gen, x);
    else
        gen->right = In(gen->right, gen, x);
    return gen;
}
 
Tree Out(Tree gen, int x) {
 
    if (x < gen->data)
        gen->left = Out(gen->left, x);
    else if (x > gen->data)
        gen->right = Out(gen->right, x);
 
    if (gen->data == x)
 
        if (!gen->left && !gen->right)return NULL;
 
        else if (gen->left) {
            Tree t = gen->left;
            while (t->right)t = t->right;
            gen->data = t->data;
            gen->left = Out(gen->left, t->data);
        }
        else {
 
            Tree t = gen->right;
            while (t->left)t = t->left;
            gen->data = t->data;
            gen->right = Out(gen->right, t->data);
        }
    return gen;
}
 
 
void bl(Tree gen) {
    Tree queue[110];
    int fr = 0, re = 0;
    queue[re++] = gen;
    while (fr != re) {
        Tree t = queue[fr++];
        if (t->left)queue[re++] = t->left;
        if (t->right)queue[re++] = t->right;
        printf("%d", t->data);
        if (fr != re)printf(" ");
    }
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；