长春大学软件工程：二叉排序树实验报告

实验目的

本次实验旨在深入理解二叉排序树的构建及基本操作，包括插入、查找和删除节点。通过编程实践，掌握递归与非递归算法的应用。

实验内容

以下是本次实验的具体任务：

1. 根据给定序列 (4, 9, 0, 1, 8, 6, 3, 5, 2, 7) 构建一棵二叉排序树，并以中序遍历的形式输出。
2. 验证所构建的树是否为有效的二叉排序树。
3. 采用递归和非递归两种方法查找关键字为6的节点，并输出其查找路径。
4. 分别删除关键字为4和5的节点，并展示删除后的二叉排序树。

代码实现

#include 
#include 

#define num 10 // 定义二叉树的节点数量

typedef struct node {
    int data;
    struct node* lchild;
    struct node* rchild;
} BSTreeOrg, *BSTree;

// 插入节点到二叉排序树中
int InsertBSTree(BSTree *bst, int data) {
    BSTree r = (BSTree)malloc(sizeof(BSTreeOrg));
    r->data = data;
    r->lchild = NULL;
    r->rchild = NULL;

    if (*bst == NULL) {
        *bst = r;
        return 1;
    }

    BSTree pre = NULL, s = *bst;
    while (s) {
        if (s->data == data)
            return 0;
        else if (data > s->data) {
            pre = s;
            s = s->rchild;
        } else {
            pre = s;
            s = s->lchild;
        }
    }

    if (data data)
        pre->lchild = r;
    else
        pre->rchild = r;

    return 1;
}

// 创建二叉排序树
void CreateTree(BSTree *bst, int n) {
    *bst = NULL;
    for (int i = 0; i         int data;
        scanf("%d", &data);
        InsertBSTree(bst, data);
    }
}

// 非递归查找关键字为6的节点
int NFindNode(BSTree bst, int findnumber) {
    BSTree findtree = bst;
    while (findtree) {
        if (findtree->data == findnumber) {
            printf("%d ", findtree->data);
            return 0;
        } else if (findtree->data > findnumber) {
            printf("%d ", findtree->data);
            findtree = findtree->lchild;
        } else {
            printf("%d ", findtree->data);
            findtree = findtree->rchild;
        }
    }
    return -1;
}

// 递归查找关键字为6的节点
int FindNode(BSTree bst, int findnumber) {
    if (!bst)
        return -1;

    if (bst->data == findnumber) {
        printf("%d ", bst->data);
        return 0;
    } else if (bst->data > findnumber) {
        printf("%d ", bst->data);
        return FindNode(bst->lchild, findnumber);
    } else {
        printf("%d ", bst->data);
        return FindNode(bst->rchild, findnumber);
    }
}

// 删除指定节点
int DelTree(BSTree *bst, int n) {
    if (n == (*bst)->data)
        delete(bst);
    else if (n <(*bst)->data)
        return DelTree(&(*bst)->lchild, n);
    else
        return DelTree(&(*bst)->rchild, n);
}

// 中序遍历打印二叉排序树
void PrintBSTree(BSTree bst) {
    if (bst != NULL) {
        PrintBSTree(bst->lchild);
        printf("%d ", bst->data);
        PrintBSTree(bst->rchild);
    }
}

int main() {
    BSTree Tree;
    printf("请输入二叉排序树的节点数据:\n");
    CreateTree(&Tree, num);
    printf("按中序遍历排序结果:\n");
    PrintBSTree(Tree);
    printf("\n");

    int m, choose;
    printf("请输入要查找的数字: ");
    scanf("%d", &m);
    printf("请选择查找方式:\n1. 递归查找\n2. 非递归查找\n您选择的方式是:");
    scanf("%d", &choose);

    if (choose == 1) {
        printf("递归查找路径: ");
        FindNode(Tree, m);
    } else if (choose == 2) {
        printf("非递归查找路径: ");
        NFindNode(Tree, m);
    } else {
        printf("请输入正确的选项\n");
    }

    printf("\n");

    for (int i = 0; i <2; i++) {
        printf("请输入要删除的数字:");
        int n;
        scanf("%d", &n);
        DelTree(&Tree, n);
        printf("删除后的新二叉排序树:\n");
        PrintBSTree(Tree);
        printf("\n");
    }

    return 0;
}

程序运行截图