V1EERIE
个人学习笔记
实验十四 二叉排序树

access_time
brush 359个字
whatshot 430 ℃
百度收录:无法查询

一、 实验目的

  1. 能够用高级语言描述二叉排序树的存储结构
  2. 能够用高级语言编写二叉排序树的插入算法在计算机中的实现。
  3. 能够用高级语言编写二叉排序树的查找算法在计算机中的实现。

二、 实验内容

1.创建一棵二叉排序树。
2.在二叉排序树上完成查找操作。

三、 实验要求

编程实现如下功能:
(1)从一棵空二叉排序树开始,根据输入的记录关键字值序列,按照二叉树插入方法将关键字记录逐个插入到二叉排序树中,从而创建一棵二叉树;
(2)输入一个指定的关键字值key, 在上述创建的二棵排序树中查找关键字值与key相等的记录,如果找到,则输出“查找成功”,否则输出“查找失败”。

四、 源程序代码

#include <iostream>
#include <stdlib.h>
using namespace std;
#define TRUE 1
#define FALSE 0
#define ElemType int
typedef int KeyType;
typedef struct
{
    KeyType key;
} TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

int SearchBST(BiTree T, KeyType key, BiTree f, BiTree *p)
{
    if (!T)
    {
        *p = f;
        return FALSE;
    }
    else if (key == T->data.key)
    {
        *p = T;
        return TRUE;
    }
    else if (key < T->data.key)
    {
        return SearchBST(T->lchild, key, T, p);
    }
    else
    {
        return SearchBST(T->rchild, key, T, p);
    }
}
int InsertBST(BiTree *T, ElemType e)
{
    BiTree p = NULL;
    if (!SearchBST((*T), e, NULL, &p))
    {
        BiTree s = (BiTree)malloc(sizeof(BiTNode));
        s->data.key = e;
        s->lchild = s->rchild = NULL;
        if (!p)
        {
            *T = s;
        }
        else if (e < p->data.key)
        {
            p->lchild = s;
        }
        else
        {
            p->rchild = s;
        }
        return TRUE;
    }
    return FALSE;
}
int Delete(BiTree *p)
{
    BiTree q, s;
    if (!(*p)->lchild && !(*p)->rchild)
    {
        *p = NULL;
    }
    else if (!(*p)->lchild)
    {
        q = *p;
        *p = (*p)->rchild;
        free(q);
    }
    else if (!(*p)->rchild)
    {
        q = *p;
        *p = (*p)->lchild;
        free(q);
    }
    else
    {
        q = *p;
        s = (*p)->lchild;
        while (s->rchild)
        {
            q = s;
            s = s->rchild;
        }
        (*p)->data.key = s->data.key;
        if (q != *p)
        {
            q->rchild = s->lchild;
        }
        else
        {
            q->lchild = s->lchild;
        }
        free(s);
    }
    return TRUE;
}
int DeleteBST(BiTree *T, int key)
{
    if (!(*T))
    {
        return FALSE;
    }
    else
    {
        if (key == (*T)->data.key)
        {
            Delete(T);
            return TRUE;
        }
        else if (key < (*T)->data.key)
        {
            return DeleteBST(&(*T)->lchild, key);
        }
        else
        {
            return DeleteBST(&(*T)->rchild, key);
        }
    }
}
void order(BiTree t)
{
    if (t == NULL)
    {
        return;
    }
    order(t->lchild);
    printf("%d ", t->data.key);
    order(t->rchild);
}
void views()
{
    cout << endl
         << "1.初始化二叉排序树" << endl
         << "2.插入节点" << endl
         << "3.删除节点" << endl
         << "4.查找节点" << endl
         << "5.中序遍历(显示)二叉排序树" << endl
         << "6.退出" << endl
         << endl;
}
int main()
{
    int i, t, n, x = -1;
    BiTree T = NULL;
    while (x != 6)
    {
        views();
        cin >> x;
        switch (x)
        {
        case 1:
            printf("输入个数:");
            cin >> n;
            printf("输入节点:\n");
            for (i = 0; i < n; i++)
            {
                InsertBST(&T, (cin >> t, t));
            }
            order(T);
            break;
        case 2:
            printf("输入节点:\n");
            cin >> t;
            InsertBST(&T, t);
            break;
        case 3:
            printf("输入节点:\n");
            cin >> t;
            if (DeleteBST(&T, t))
                cout << "删除成功" << endl;
            else
                cout << "删除失败" << endl;
            break;
        case 4:
            printf("输入节点:\n");
            cin >> t;
            BiTree *p;
            if (SearchBST(T, t, NULL, p))
                cout << "查找成功" << endl;
            else
                cout << "查找失败" << endl;
            break;
        case 5:
            order(T);
            break;
        default:
            break;
        }
    }
}

五、 运行结果

TNVvs1.png
TNVjMR.png
TNVOz9.png
TNVLRJ.png

六、 实验总结与体会

  1. 掌握二叉排序树的基本算法
  2. 实现通过二叉排序树查找元素
  3. 学习二叉排序树的时间复杂度计算

#如无特别声明,该文章均为 V1EERIE 原创,转载请遵循 署名-非商业性使用 4.0 国际(CC BY-NC 4.0) 协议,即转载请注明文章来源。
#最后编辑时间为: 2021 年 12 月 25 日


create 添加新评论


account_circle
email
language
textsms





关于 DreamCat

主题名称:DreamCat | 版本:X2.6.220211

主题开发:HanFengA7 | TeddyNight | Dev-Leo | CornWorld | WhiteBearcn | DFFZMXJ

Designed by HanFengA7 Power by Typecho

Copyright © 2015-2022 by LychApe All rights reserved!

加我的QQ
加我的微博
加我的支付宝
加我的微信