第九天-------二叉排序树附源码

偏执的太偏执、 2022-05-21 09:55 114阅读 0赞

**一、 目的**

掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。

**二、内容**

1、内容

随机产生一组关键字，利用二叉排序树的插入算法建立二叉排序树，然后删除某一指定关键字元素。

\* 建立AVL树并实现删除某一指定关键字元素。

\*综合训练： 树种统计

随着卫星成像技术的应用，自然资源研究机构可以识别每一棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。首先输入正整数N（≤105），随后N行，每行给出卫星观测到的一棵树的种类名称。种类名称由不超过30个英文字母和空格组成（不区分大小写）。按字典序递增输出各种树的种类名称及其所占总数的百分比，其间以空格分隔，每种树的信息占一行。

2、主要数据类型与变量

\#define FALSE 0

\#define TURE 1

\#define MAXSIZE 10

typedef struct BiTNode          //构造树的节点类型

int data;                   //数据域

struct BiTNode\*lchild, \*rchild;        //指针域

\} BiTNode, \*BiTree;

3、算法思想描述

二叉树排序，通过给定的数据，新建二叉树，根节点比左孩子的值都大，比右孩子的值都小，左子树和右子树都遵循这个方法进行新建二叉树，当删除或者添加或者查找某个节点的数据域的值时。然后通过与根节点的数据域的值的比较，知道是否相等，或者是去左子树查找还是右子树查找。输出输出二叉树，即是遍历，采用的是中序遍历。通过递归调用，输出中序遍历的排序。

**三、系统测试**

1、测试方案

没有采用用户界面的方式进行交互，而是通过直接的输出，这样可以直观的将所写的各个方法直接显示出来，并且判断出程序的正确错误，如插入数据时，若错误，会直接输出错误语句。

2、测试结果

1.当程序正常执行，并且输入数据也是合理的情况下，程序的执行结果如下：

2.当输入的数据有一定的误差的时候，也能够给出相应的变化。

**附：程序源代码**

** **

**Main.c**

**//二叉排序树**

**//其中有插入、删除、查找操作**

**\#include<stdio.h>**

**\#include<stdlib.h>**

** **

**\#define FALSE 0**

**\#define TURE 1**

**\#define MAXSIZE 10**

** **

**typedef struct BiTNode          //构造树的节点类型**

**\{**

**   int data;                   //数据域**

**   struct BiTNode \*lchild, \*rchild;       //指针域**

**\} BiTNode, \*BiTree;**

** **

**//查找**

**int SearchBST(BiTree T,int key,BiTreef,BiTree \*p)**

**\{**

**   if(!T)                      //不存在时，返回错误**

**   \{**

**        \*p=f;**

**        return FALSE;**

**   \}**

**   else if(key==T->data)       //判断是否相等，**

**   \{**

**        \*p=T;**

**        return TURE;**

**   \}**

**   else if(key < T->data)     //若小于，指向当前节点的左孩子，**

**        return SearchBST(T->lchild,key,T,p);**

**   else                        //若大于，指向当前节点的右孩子**

**        return SearchBST(T->rchild,key,T,p);**

**\}**

** **

**//插入**

**void InsertBST(BiTree \*T,int key)**

**\{**

**   BiTree p,s;**

**   if(!SearchBST(\*T,key,NULL,&p))     //若树中没有相同元素，继续**

**   \{**

**        s=(BiTree)malloc(sizeof(BiTNode));**

**        s->data=key;**

**        s->lchild=s->rchild=NULL;       //设置新元素s**

**        if(!p)      //若树为空，将s设为根节点**

**            \*T=s;**

**        else if(key<p->data)        //否则。。**

**            p->lchild=s;**

**        else**

**            p->rchild=s;**

**   \}**

**   else**

**        printf("对不起，树中已有该元素。 \\n");**

**\}**

** **

**//DeleteBST用到的子函数**

**//删除节点无左子树，则将其右子树补到现在位置，反之亦然**

**//若左右字树都有，则找其左子树，然后右到底，即中序遍历时，删除节点的上一个元素——前驱**

**//以前驱作为新节点**

**void Delete(BiTree \*p)**

**\{**

**   BiTree q,s;**

**   if((\*p)->rchild==NULL)      //无右，以左子树替换**

**   \{**

**        q=\*p;**

**        \*p=(\*p)->lchild;**

**        free(q);**

**   \}**

**   else if((\*p)->lchild==NULL)    //无左**

**   \{**

**        q=\*p;**

**        \*p=(\*p)->rchild;**

**        free(q);**

**   \}**

**   else**

**   \{**

**        q=\*p;**

**        s=(\*p)->lchild;     //左一下**

**        while(s->rchild)    //右到底**

**        \{**

**            q=s;**

**            s=s->rchild;**

**        \}**

**        (\*p)->data=s->data;     //前驱替换删除节点**

**        if(q!=\*p)**

**            q->rchild=s->lchild;**

**        else**

**            q->lchild=s->lchild;**

**        free(s);**

**   \}**

**\}**

** **

**//删除**

**void DeleteBST(BiTree \*T,int key)**

**\{**

**   BiTree p;**

**   if(SearchBST(\*T,key,NULL,&p))      //找与key相等的元素**

**   \{**

**        if(key==(\*T)->data)**

**            Delete(T);**

**        else if(key<(\*T)->data)**

**           DeleteBST(&(\*T)->lchild,key);**

**        else**

**           DeleteBST(&(\*T)->rchild,key);**

**   \}**

**   else**

**        printf("对不起，当前二叉树中没有你要删除的元素。 \\n");**

**\}**

** **

**//中序输出**

**void InOrder(BiTree T)**

**\{**

**   if(T)**

**   \{**

**        InOrder(T->lchild);**

**        printf("%d ",T->data);**

**        InOrder(T->rchild);**

**   \}**

**   else**

**        return;**

**\}**

** **

**int main()**

**\{**

**   int i,num;**

**   BiTree T=NULL;**

** **

**   int a\[9\]= \{33,44,32,65,25,73,41,88,62\};**

**   for(i=0; i<9; i++)**

**   \{**

**        InsertBST(&T,a\[i\]);         //建立二叉树树，通过给定的数据构成二叉树**

**   \}**

**   printf("目前已给定的二叉树为：\\n");**

**   InOrder(T);**

**   printf("\\n");**

** **

**   printf("请输入需要插入的元素：\\n");**

**   scanf("%d",&num);**

**   InsertBST(&T,num);**

**   printf("当前的二叉树为：\\n");**

**   InOrder(T);**

**   printf("\\n");**

** **

**   printf("请输入你要删除的元素：");**

**   scanf("%d",&num);**

**   DeleteBST(&T,num);**

**   printf("当前的二叉树为：");**

**   InOrder(T);**

**   printf("\\n");**

**   return 0;**

**\}**

** **

第九天-------二叉排序树附源码

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关二叉树和排序二叉树

相关树：二叉排序树

相关二叉排序树

相关二叉排序树

相关二叉排序树

相关二叉排序树

相关二叉排序树

相关第九天-------二叉排序树附源码

相关二叉树的基本操作附源码

相关二叉树-详解二叉排序树