Gausst松鼠会

这个屌丝很懒，什么也没留下！

热门标签

查找_1、设计一个读入一串整数,然后构造二叉排序树,进行查找。要求:从空的二叉树开始,

作者：Gausst松鼠会 | 2024-03-16 00:57:25

踩

1、设计一个读入一串整数,然后构造二叉排序树,进行查找。要求:从空的二叉树开始,

实验名称 查找

实验目的：

1. 熟练掌握二叉排序树的构造和查找方法。

2. 熟练掌握静态查找表及哈希表查找方法。

二、实验环境：

Visual C++

三、实验内容：

(写出主要的内容)

设计一个读入一串整数，然后构造二叉排序树，进行查找。

四、实验步骤

1. 从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。

2. 在二叉排序树中查找某一结点。

3.用其它查找算法进行排序（课后自己做）。

五、实现操作


#include <stdio.h>
 
#include <stdlib.h>
 
#define TRUE 1
 
#define FALSE 0
 
#define ENDKEY 0
 
 
 
typedef int KeyType;
 
 
 
typedef struct  node
 
{
 
       KeyType  key ; /*关键字的值*/
 
       struct node  *lchild,*rchild;/*左右指针*/
 
}BSTNode, *BSTree;
 
 
 
int InsertBST(BSTree *bst, KeyType key)
 
/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/
 
{
 
       //请完成本函数的功能
 
       BSTree s;
 
       if(* bst == NULL)
 
       {
 
              s = (BSTree)malloc(sizeof(BSTNode));
 
              s->key = key;
 
              s->lchild = NULL;
 
              s->rchild = NULL;
 
              * bst = s;
 
       }
 
       else if(key < (* bst)->key)
 
              InsertBST(&((* bst)->lchild),key);
 
       else if(key > (* bst)->key)
 
              InsertBST(&((* bst)->rchild),key);
 
       return 0;
 
}
 
 
 
void  CreateBST(BSTree  *bst)
 
/*从键盘输入元素的值，创建相应的二叉排序树*/
 
{
 
       //请完成本函数的功能
 
       KeyType key;
 
       * bst = NULL;
 
       scanf("%d",&key);
 
       while(key != ENDKEY)
 
       {
 
              InsertBST(bst,key);
 
              scanf("%d",&key);
 
       }
 
}
 
 
 
void  InOrder(BSTree bst) 
 
/*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/
 
{
 
       if (bst!=NULL)
 
       {
 
              InOrder(bst ->lchild);   /*中序遍历左子树*/
 
              printf("%d->",bst->key);        /*访问根结点*/
 
              InOrder(bst ->rchild);   /*中序遍历右子树*/
 
       }
 
}
 
 
 
BSTree  SearchBST(BSTree bst, KeyType key)
 
/*在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点指针，否则返回空指针*/
 
{
 
       //请完成本函数的功能
 
       if(!bst) return NULL;
 
       else if(bst->key == key)
 
              return bst;
 
       else if(bst->key > key)
 
              return SearchBST(bst->lchild,key);
 
       else
 
              return SearchBST(bst->rchild,key);
 
}
 
int DelBST(BSTree t, KeyType  k) /*在二叉排序树t中删去关键字为k的结点*/
 
{
 
       BSTNode  *p, *f,*s ,*q;
 
       p=t;
 
       f=NULL;
 
       while(p)  /*查找关键字为k的待删结点p*/
 
       {
 
              if(p->key==k )  break;  /*找到则跳出循环*/
 
              f=p;   /*f指向p结点的双亲结点*/
 
              if(p->key>k) 
 
                     p=p->lchild;
 
              else
 
                     p=p->rchild;
 
       }
 
       if(p==NULL)  return 0;  /*若找不到，返回原来的二叉排序树*/
 
       if(p->lchild==NULL)  /*p无左子树*/
 
       {
 
              if(f==NULL)
 
                     t=p->rchild;  /*p是原二叉排序树的根*/
 
              else
 
                     if(f->lchild==p)  /*p是f的左孩子*/
 
                            f->lchild=p->rchild ;  /*将p的右子树链到f的左链上*/
 
                     else  /*p是f的右孩子*/
 
                            f->rchild=p->rchild ;  /*将p的右子树链到f的右链上*/
 
                     free(p);  /*释放被删除的结点p*/
 
       }
 
       else  /*p有左子树*/
 
       {
 
              q=p;
 
              s=p->lchild;
 
              while(s->rchild)  /*在p的左子树中查找最右下结点*/
 
              {
 
                     q=s;
 
                     s=s->rchild;
 
              }
 
              if(q==p)
 
                     q->lchild=s->lchild ;  /*将s的左子树链到q上*/
 
              else
 
                     q->rchild=s->lchild;
 
              p->key=s->key;  /*将s的值赋给p*/
 
              free(s);
 
       }
 
       return 1;
 
}  /*DelBST*/
 
 
 
void main()
 
{
 
       BSTree T,p;
 
       int keyword,temp;
 
       char ch,j='y';
 
       T=NULL;
 
       while(j!='n')
 
    {
 
              printf("1.创建二叉排序树\n");
 
              printf("2.显示排序的数据\n");
 
              printf("3.查找数据\n");
 
              printf("4.在查找树中插入一个数据\n");
 
              printf("5.在查找树中删除一个数据\n");
 
              printf("6.程序结束，退出\n");
 
              scanf(" %c",&ch); //输入操作选项
 
              switch(ch)
 
              {
 
              case '1':
 
                     printf("请输入数据，以0作为数据输入结束。\n");
 
                     CreateBST(&T);
 
                     break;
 
              case '2':
 
                     if(!T) printf("二叉排序树中没有数据。\n");
 
                     else {InOrder(T);printf("\b\b  \n");}
 
                     break;
 
       case '3':
 
                     printf("输入待查找的数据值:\n");
 
                     scanf("%d",&keyword); //输入要查找元素的关键字
 
                     p=SearchBST(T, keyword);
 
                     if(!p) printf("%d 没有找到。\n",keyword); //没有找到
 
                     else printf("%d 查找成功。\n",keyword); //成功找到
 
                     break;
 
       case '4':
 
                     printf("输入待插入的数据:");
 
                     scanf("%d",&keyword); //输入要插入元素的关键字
 
                     temp=InsertBST(&T, keyword);
 
                     if(temp==FALSE)
 
                            printf("%d 已在二叉树中!\n",keyword); //该元素已经存在
 
                     else
 
                            printf("%d 插入成功！\n",keyword);
 
                     break;
 
       case '5':
 
                     printf("输入待删除的数据:");
 
                     scanf("%d",&keyword); //输入要删除元素的关键字
 
                     temp=DelBST(T, keyword);
 
                     if(temp==FALSE) printf("%d 不存在!\n",keyword); //该元素不存在
 
                     else printf("成功删除%d\n",keyword); //成功删除
 
                     break;
 
       default:
 
                     j='n';
 
              }
 
 }
 
 printf("程序结束!\nPress any key to shut off the window!\n");
 
 getchar();
 
 getchar();
 
}

输出样例：

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

请输入数据，以0作为数据输入结束。

2 5 3 4 6 7 8 9 1 0

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

1->2->3->4->5->6->7->8->9

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待查找的数据值:

2 查找成功。

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待插入的数据:10

10 已在二叉树中!

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

1->2->3->4->5->6->7->8->9->10

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:1

成功删除1

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

2->3->4->5->6->7->8->9->10

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

程序结束!

程序出现的bug：

bug1：如果1在第一位不能连续删除

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

请输入数据，以0作为数据输入结束。

1 5 2 3 4 6 7 8 9 0

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

1->2->3->4->5->6->7->8->9

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:1

成功删除1

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:2

Press any key to continue

Bug2：可以连续删除，但在某个删除时不能实现，具有随机性，与创建二叉排序树的先后有关

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

请输入数据，以0作为数据输入结束。

5 6 7 8 9 1 2 3 4 0

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

1->2->3->4->5->6->7->8->9

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:1

成功删除1

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:2

成功删除2

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:3

成功删除3

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:4

成功删除4

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:5

成功删除5

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:6

Press any key to continue

Bug3：可以连续删除，但删除至最后一位时，程序自动结束，不能再显现

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

请输入数据，以0作为数据输入结束。

8 4 5 6 1 7 2 9 3 0

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:1

成功删除1

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:2

成功删除2

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:3

成功删除3

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:4

成功删除4

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:5

成功删除5

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:6

成功删除6

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:7

成功删除7

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:8

成功删除8

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:9

Press any key to continue

Bug4：不可以删除一个后再显示再重复操作

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

请输入数据，以0作为数据输入结束。

5 8 7 9 4 3 2 6 1 0

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

1->2->3->4->5->6->7->8->9

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:1

成功删除1

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

2->3->4->5->6->7->8->9

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:2

成功删除2

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

3->4->5->6->7->8->9

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:3

成功删除3

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

4->5->6->7->8->9

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:4

成功删除4

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

5->6->7->8->9

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

输入待删除的数据:5

成功删除5

1.创建二叉排序树

2.显示排序的数据

3.查找数据

4.在查找树中插入一个数据

5.在查找树中删除一个数据

6.程序结束，退出

Press any key to continue

六、心得体会：

1、普通二叉树中各个分支的高度可能相差悬殊，而平衡二叉排序树中各个分支的高度能够始终保持平衡，从而保证较高的查找效率。

2、结点的平衡因子是结点的左子树深度与右子树深度之差。

3、在平衡二叉树中，任意结点的平衡因子的绝对值小于等于1。

4、在平衡二叉树上插入一个结点时可能导致失衡，有四种失衡类型及对应的调整方法。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/245867