二叉树的实现

二叉树的实现

一.二叉排序树的结点类型

typedef int KeyType;
typedef struct node 
{       KeyType key;            	  
       InfoType data;          	  
        struct node *lchild,*rchild; 	  
}  BSTNode;

二.SearchBST(BSTNode *T,KeyType k)

伪代码

BSTNode *SearchBST(T,k)
{ 
      if (T为空 || T->key==k) 	            
            return T;                       //返回T,递归出口
      if (k<T->key)
        return SearchBST(T->lchild,k);   //在左子树中递归查找
      else
        return SearchBST(T->rchild,k);   //在右子树中递归查找
}

代码

BSTNode* SearchBST(BSTNode* T ,KeyType k)
{
    if (T == NULL || T->key == k)
        return T;
    if (k < T->key)
        return SearchBST(T->lchild,k);
    else
        return SearchBST(T->rchild,k);
}

三.InsertBST(BSTNode *&T,KeyType k)

伪代码

int InsertBST(T,k)	
{ 
     if (T为空)	 //原树为空, 新插入的记录为根结点
     {      创建一个新的key域为k的结点;
            return 1;
      }
      else if  (k==T->key) 	//存在相同关键字的结点,返回0
           return 0;
      else if (k<T->key) 
          return InsertBST(T->lchild,k); 	//插入到左子树中
      else  
          return InsertBST(p->rchild,k);  	//插入到右子树中
 }

代码

int InsertBST(BSTNode*& T,KeyType k)
{
    if (T == NULL)
    {
        T = new BSTNode;
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    else if (k == T->key)
        return 0;
    else if (k < T->key)
        return InsertBST(T->lchild,k);
    else
        return InsertBST(T->rchild,k);
}

四.CreatBST(KeyType A[],int n)

伪代码

BSTNode *CreatBST(A[],n) //返回树根指针
{      BSTNode *T;
       T为空树;
       int i=0;
       while (i<n) 
       {    InsertBST(T,A[i]);  //将A[i]插入二叉排序树T中
           i++;
       }
       return T;       	    //返回建立的二叉排序树的根指针
}

代码

BSTNode* CreatBST(KeyType A[],int n)
{
    BSTNode* T = NULL;
    int i = 0;
    while (i < n)
    {
        InsertBST(T,A[i]);
        i++;
    }
    return T;
}

二叉树的实现

五.DeleteBST(BSTNode *&T,KeyType k)

伪代码

int DeleteBST(T,k)  //在bt删除关键字为k的结点
{ 
        if (T为空) return 0;	//空树删除失败
        else 
        {      if (k<T->key) return DeleteBST(T->lchild,k);	
                       //递归在左子树中删除为k的结点
	           else if (k>T->key) return DeleteBST(T->rchild,k);
	                   //递归在右子树中删除为k的结点
               else  
               {       Delete(T);    //调用Delete(T)函数删除*T结点
	                   return 1;
              }
      }
}
void Delete(p)   	 //从二叉排序树中删除*p结点
{     BSTNode *q;
      if (p结点没有右子树)        	
      {    用其左孩子结点替换它
      }
      else if (p结点没有左子树)    	
      {    用其右孩子结点替换它
      }
      else Delete1(p,p->lchild);	
            //*p结点既没有左子树又没有右子树的情况
}
void Delete1(p,r)
  //当被删*p结点有左右子树时的删除过程
  {     BSTNode *q;
         if (r的右孩子不为空)
	   		Delete1(p,r->rchild);	//递归找*r的最右下结点
        else  		              //r指向最右下结点
        {   
        	用r结点替换p;
	   		删除r结点;
       }
  }

代码

int DeleteBST(BSTNode*& T,KeyType k)  
{
    if (T == NULL) return 0;	
    else
    {
        if (k < T->key) 
        	return DeleteBST(T->lchild,k);
        else if (k >T->key) 
        	return DeleteBST(T->rchild,k);
        else   
        {
            Delete(T);    
            return 1;
        }
    }
}
void Delete(BSTNode*& p)   	 
{
    BSTNode* q;
    if (p->rchild == NULL)        	
    {
        q = p; p = p->lchild;		
        free(q);
    }
    else if (p->lchild == NULL)    	
    {
        q = p; p = p->rchild;	
        free(q);
    }
    else Delete1(p,p->lchild);
}
void Delete1(BSTNode* p,BSTNode*& r)
{
    BSTNode* q;
    if (r->rchild != NULL)
        Delete1(p,r->rchild);	
    else  		              
    {
        p->key = r->key;  
        p->data = r->data;   
        q = r; r = r->lchild;          
        free(q); 	              
    }
}

二叉树的实现
二叉树的实现
二叉树的实现
二叉树的实现
二叉树的实现
二叉树的实现

六.

随机生成包含100000个节点的BST,节点的值为证书其范围为[-300000,300000],输出其树的高度。然后随机搜1000个数值,统计每次的ASL。

#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef struct node
{
    KeyType key;            	  //关键字项
    InfoType data;          	  //其他数据域
    struct node* lchild, * rchild; 	  //左右孩子指针
}  BSTNode;
BSTNode* SearchBST(BSTNode* T ,KeyType k,int &count)
{
    if (T == NULL || T->key == k)
    {
        if (T!= NULL)
            count++;
        return T;
    }
        
    if (k < T->key)
    {
        count++;
        return SearchBST(T->lchild, k,count);
    }
    else
    {
        count++;
        return SearchBST(T->rchild, k,count);
    }
 }
        
int InsertBST(BSTNode*& T,KeyType k)
{
    if (T == NULL)
    {
        T = new BSTNode;
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    else if (k == T->key)
        return 0;
    else if (k < T->key)
        return InsertBST(T->lchild,k);
    else
        return InsertBST(T->rchild,k);
}
BSTNode* CreatBST(int n)
{
    BSTNode* T = NULL;
    int i = 0;
    int x;
    srand((unsigned int)time(NULL));
    while (i < n)
    {
        x = rand() * 10 % 300000 - 150000;
        InsertBST(T,x);
        i++;
    }
    return T;
}
void DestroyBST(BSTNode* bt)//销毁树
{
    if (bt != NULL)
    {
        DestroyBST(bt->lchild);
        DestroyBST(bt->rchild);
        delete bt;
    }
}
void InOrder(BSTNode* b)
{
    if (b != NULL)
    {
        InOrder(b->lchild);
        printf("%d ", b->key); 	//访问根结点
        InOrder(b->rchild);
    }
}
int GetHeight(BSTNode* BT)
{
    int lchilddep, rchilddep;
    if (BT == NULL) return(0); 	//空树的高度为0
    else
    {
        lchilddep = GetHeight(BT->lchild);
        //求左子树的高度为lchilddep
        rchilddep = GetHeight(BT->rchild);
        //求右子树的高度为rchilddep
        return(lchilddep > rchilddep) ? (lchilddep + 1) : (rchilddep + 1);
    }
}
int main()
{
    BSTNode* T;
    int n;
    int i;
    int count,sum=0;
    int height;
    cin >> n;
    srand((unsigned int)time(NULL));
    T=CreatBST( n);
    height=GetHeight(T);
    cout << "树的高度"<<height << endl;
    int a[1000];
    for (i = 0; i < 1000; i++)
    {
        a[i] = rand() * 10 % 300000 - 150000;
    }
    for (i = 0; i < 1000; i++)
    {
        count = 0;
        SearchBST(T, a[i], count);
        sum = sum + count;
    }
    cout << "ASL:";
    cout << sum / 1000;
    DestroyBST(T);
    return 0;
}

二叉树的实现
二叉树的实现
二叉树的实现
二叉树的实现

我通过许多次测试,树的平均高度为36,ASL的平均值为18。

七.总结

1.通过伪代码我们可以先理清思路,再写代码就不会卡住,运行错误,也可以更快的找出错误所在。

2.二叉排序树的操作函数中,删除结点函数较难,需要考虑多种情况,编写难度较大。

3.学习了如何随机产生一个随机数,并且产生在一定范围里。

4.二叉排序树的时间复杂度为O(log2(n)),查找成功的平均查找长度为[(n+1)/n]*log2(n+1)-1,最小高度为log2(n)+1。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114450.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ssh配置免密码登录(linux免密登录)

    由于公司的生产环境有很多台Linux的CentOS服务器,为了方便机子(假设两台机子A,B)互相之间免密ssh,scp命令操作,配置如下1.在A、B上分别创建本机的公钥和私钥,输入命令后连续三次回车ssh-keygen-trsa2.查看公私钥的文件生成情况cd~/.ssh/ls看到列表有2个文件:文件说明:id_rsa:生成的私钥文件id_rsa.pub:生成的公钥文件3….

  • docker安装rabbitmq无法进入管理页面

    docker安装rabbitmq无法进入管理页面文章目录1.环境准备2.开始安装2.1解决安装不能打开管理后台的问题1.环境准备腾讯云服务器CENTOS7版本安装docker容器2.开始安装dockerpullrabbitmq:management说明:为什么不直接安装dockerpullrabbitmq这个,因为这个安装后,开启对应端口后是不能直接访问它的管理后台,需要额外的命令开启,后面会将这种情况容器运行,对应的端口开启dockerrun-di–name=mycloud_rabbitm

  • PYCHARAM3.7激活码破解方法

    PYCHARAM3.7激活码破解方法,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • arm服务器测评_ARM:异军突起「建议收藏」

    arm服务器测评_ARM:异军突起「建议收藏」RISC:战火点燃RISC和CISC握手言和,这并非服务器市场竞争结束,而是新一轮战火点燃的信号。双方短暂的和平还因为现在的处理器速度与指令集构架的关系越来越小,指令集构架的影响力早已被CPU微结构,甚至更为贴近底层的设计所超越。而反观服务器市场,在中低档服务器全盘被x86所统治的情况下,高端服务器的竞争形势也很激烈。在高档服务器市场中,Compaq的Alpha、惠普的PA-RISC、MIPS公司…

  • java如何配置环境变量_java如何配置环境变量

    java如何配置环境变量_java如何配置环境变量首先安装jdk,点击打开下图所示窗口。点击上图“下一步“进入下图,下图红色框选位置为安装的路径。点击上图下一步进入下图,点击”完成“即可。下面配置java环境变量,右键计算机图标,如下图所示:点击上图属性后,弹出系统窗口,点击最左边红色箭头所指“高级系统设置”按钮弹出“系统属性”窗口,在系统属性窗口点击中间箭头所指“环境变量”,弹出环境变量窗口。点击下图红色箭头所指新建按钮,弹出“新建系统变量”…

  • vue入门基础教程之经验总结篇(小白入门必备)|建议收藏「建议收藏」

    vue入门基础教程之经验总结篇(小白入门必备)|建议收藏「建议收藏」VUEvue组件的三个API:prop、event、slotprop定义了这个组件有哪些可配置的属性,组件的核心功能也都是它来确定的。组件里定义的prop都是单向数据流,只能通过父级组件对齐进行修改,组件本身不能修改props的值,只能修改定义在data里的数据,非要修改,也是通过后面介绍的自定义事件通知父级,由父级来修改;在子组件定义prop是,使用了camelCase的命名法,由于html特性不区分大小写。camelCase的prop用于特性时,会转为短横线隔开(比如availab

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号