程序员经验分享-hwhale

二叉搜索树详解链式与数组式实现

2023-05-16

前沿：

首先让我们认识下什么是二叉搜索树，二叉搜索树是十分高效的一种搜索算法，定义为：它的每个节点都有以下性质（在左右子树都不为空的情况下）自己本身的权值比它的左子树大，自己本身的权值比它的右子树小。简单的说比它小的在左边，比它大的在右边。如下图所示：

这里写图片描述

相信聪明的你已经猜到规则了。

主要操作：

插入

第 一，就是插入了，其实初始化就是通过插入实现的，都一样。
自己在纸上画画就会发现其实插入的位置肯定是某个叶子节点的位置，这样就很好理解了，首先从根节点开始找，要是比此节点小就搜节点的左子树，比节点大就搜节点的右子树，直到搜到某个节点为空（就是某个叶子节点），再将这个节点赋值key，就OK了。
现在让我们画画图吧：
这里写图片描述
代码范式：

void insert(node **T,int n)//插入
{
    if((*T)==NULL)
    {
        (*T)=new(node);
        (*T)->lchild=NULL;
        (*T)->rchild=NULL;
        (*T)->key=n;
        return ;
    }
    if((*T)->key>n)
       insert(&((*T)->lchild),n);
    else
      insert(&((*T)->rchild),n);
}

搜索

第二，就是搜索操作了
搜索跟插入是类似的，首先从根节点开始找，要是比此节点小就搜节点的左子树，比节点大就搜节点的右子树，直到搜到某个节点为空还没找到就是不存在咯，否则就是存在。

 node * search(node *T,int n)//搜索
{
    if(T==NULL||T->key==n)
      {
          return T;
      }
    if(T->key>n)
      {cout<<'W';search(T->lchild,n);}
    else
      {cout<<'E';search(T->rchild,n);}
}

删除

第三，就是删除操作了

这是这里最难的一个了，因为得考虑三个方面：
1）当要删除的节点没有左右孩子;；
2）当要删除的节点只有一个左右孩子；
3）当要删除的节点有两个左右孩子；

情况一：最简单了，因为这节点肯定是叶子节点，直接将这个节点置空，再直接free（）这个节点，就OK了。

情况二： 只要改变要删除的节点T的父节点的孩子就好了，只要将T的孩子替换T，再free（）T节点就OK了。
这里写图片描述

情况三：这个情况比较难，我就难于用文字描述了，简单的说先要将T右子树最小值去覆盖T的值，再转变为删除这个最小值的操作，为什么要找T右子树的最小值？因为根据二叉搜索树的性质：节点T左边的子树所有节点都小于节点T，节点右边的子树都大于节点T，所以要删除两个孩子的节点就要找节点T右子树最小的节点值代替它，这样就能保持二叉搜索树的性质。
这里写图片描述

代码范式：

node *minimum(node *t)//最小结点
{
    if(t->lchild!=NULL)
      return minimum(t->lchild);
    return t;
}

void Delete(node **T,int x)//删除结点
{
    if((*T)->key>x)
      Delete(&((*T)->lchild),x);
    else if((*T)->key<x)
      Delete(&((*T)->rchild),x);
    else if((*T)->lchild&&(*T)->rchild)//两个节点情况
     {
         node *p=minimum((*T)->rchild);
         (*T)->key=p->key;
         Delete(&((*T)->rchild),(*T)->key);
     }
    else //叶子节点或有一个叶子节点情况
    {
        node *p=(*T);
        if((*T)->lchild==NULL)
           (*T)=(*T)->rchild;
        else if((*T)->rchild==NULL)
           (*T)=(*T)->lchild;
        free(p);
    }
}

代码实现

下面就贴代码吧：

二叉搜索树链式：

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;//二叉搜索树
typedef struct node
{
    int key;
    struct node *lchild;
    struct node *rchild;
} node;
void creat(node **T)//初始化
{
   *T=NULL;
}
void insert(node **T,int n)//插入
{
    if((*T)==NULL)
    {
        (*T)=new(node);
        (*T)->lchild=NULL;
        (*T)->rchild=NULL;
        (*T)->key=n;
        return ;
    }
    if((*T)->key>n)
       insert(&((*T)->lchild),n);
    else
      insert(&((*T)->rchild),n);
}
void inordor (node *T)//中序遍历
{
    if(T!=NULL)
    {
        inordor(T->lchild);
        printf("%-3d",T->key);
        inordor(T->rchild);
    }
}
node * search(node *T,int n)//搜索
{
    if(T==NULL||T->key==n)
      {
          return T;
      }
    if(T->key>n)
      {cout<<'W';search(T->lchild,n);}
    else
      {cout<<'E';search(T->rchild,n);}
}
node *minimum(node *t)//最小结点
{
    if(t->lchild!=NULL)
      return minimum(t->lchild);
    return t;
}
node *maxmum(node *t)//最大结点
{
    if(t->rchild!=NULL)
      return maxmum(t->rchild);
}

void Delete(node **T,int x)//删除结点
{
    if((*T)->key>x)
      Delete(&((*T)->lchild),x);
    else if((*T)->key<x)
      Delete(&((*T)->rchild),x);
    else if((*T)->lchild&&(*T)->rchild)
     {
         node *p=minimum((*T)->rchild);
         (*T)->key=p->key;
         Delete(&((*T)->rchild),(*T)->key);
     }
    else
    {
        node *p=(*T);
        if((*T)->lchild==NULL)
           (*T)=(*T)->rchild;
        else if((*T)->rchild==NULL)
           (*T)=(*T)->lchild;
        free(p);
    }
}
int main()
{
    int n;
    node *T;
    creat(&T);
    printf("初始化二叉搜索树个数：");
    scanf("%d",&n);
   for(int i=0; i<n; ++i)
    {
        int a;
        scanf("%d",&a);
        insert(&T,a);
    }
    int m;
       inordor(T);
    printf("\n");
    scanf("%d",&m);
  //  if(search(T,m)==NULL)
   //  printf("NO\n");
  //  printf("\n");
    Delete(&T,m);
     //node *p=minimum(T);
    // printf("%d\n",p->key);
    inordor(T);
    free(T);
    return 0;
}

这里写图片描述

二叉搜索树数组式：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX=10000;
const int NIL=-1;//定义-1为空
int tree[MAX];

void Insert(int root,int x)//插入操作
{
    if(tree[root]==NIL)
    {
        tree[root]=x;
        return ;
    }
    if(tree[root]>=x)
        Insert(root*2,x);
    else
        Insert(root*2+1,x);
}
bool Search(int root,int x)
{
    while(tree[root]!=NIL)
    {
        if(tree[root]==x)
            return true;
        if(tree[root]>x)
            root*=2;
        else
            root=root*2+1;
    }
    return false;
}
void bianli(int root)//中序遍历
{
    if(tree[root]==NIL)
        return ;
    else
    {
        bianli(root*2);
        printf("%-3d",tree[root]);
        bianli(root*2+1);
    }
}

int TRmin(int root)//返回最小值
{
    if(tree[root*2]==NIL)
        return tree[root];
    return TRmin(root*2);
}
void Delete(int root,int x)
{
    if(tree[root]>x)
        Delete(root*2,x);
    else if(tree[root]<x)
        Delete(root*2+1,x);
    else if(tree[root*2]!=NIL&&tree[root*2+1]!=NIL)
    {
        int key=TRmin(root*2+1);
        tree[root]=key;
        Delete(root*2+1,key);
    }
    else if(tree[root*2]==NIL&&tree[root*2+1]==NIL)
    {
        tree[root]=-1;

    }
    else
    {
        if(tree[root*2]==NIL)
        {
            tree[root]=tree[root*2+1];
            Delete(root*2+1,tree[root*2+1]);
        }
        else
        {
            tree[root]=tree[root*2];
            Delete(root*2,tree[root*2]);
        }
    }
}
int main()
{
    int n;
    printf("初始化节点数n:");
    while(scanf("%d",&n)!=EOF)
    {
        int a;
        memset(tree,-1,sizeof(tree));
        printf("输入数据：");
        for(int i=0;i<n;++i)
        {
            scanf("%d",&a);
            Insert(1,a);
        }
        printf("中序遍历结果为：");
        bianli(1);
        cout<<endl;
        if(Search(1,9))
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
//        while(1)
//        {
//            int b;
//            scanf("%d",&b);
//            Delete(1,b);
//            bianli(1);
//        }
     //   printf("%d\n",TRmin(1));

    }
    return 0;
}

这里写图片描述

二叉搜索树的缺点

在一般情况下二叉搜索树的插入，搜索，删除时间复杂度是O(logn),但是如果插入的数都是递增的话 如：（1,2,3,4,5,6,7,…）
如图所示：

这里写图片描述

这时插入，搜索，删除时间复杂度是O(n)

那么怎么解决这个问题呢：这问题的主要原因是数据偏向单边，使树的高度线性增长，为了能做到插入的数据不偏向单边，如果个节点的左子树高度与右子树高度相差<=1,那么就能做到插入，搜索，删除时间复杂度是O(logn)，于是就有了平衡的概念，二叉平衡搜索树（AVL树）就出来了，这里的主题就不讲二叉平衡搜索树（AVL树）了，到时专门写一个二叉平衡搜索树的。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

二叉搜索树详解链式与数组式实现

二叉搜索树详解链式与数组式实现 的相关文章

  • mysql的视图、存储过程、游标、事务、引擎、索引的认识和使用

    视图 一 视图概念 xff1a 视图是虚拟表 xff0c 并不存在真正的表 xff0c 可以重用sql语句 xff0c 利用实际存在的一个或几个表链接查询数据 xff0c 只展示部分数据 xff0c 可以保护数据库中数据 只有部分表的权限

  • win10下mysql5忘记root用户密码如何修改密码并登录

    步骤 xff1a 1 关闭mysql服务 xff1a net stop mysql 2 进入mysql安装目录 xff1a 如 3 此时可以免密登录 xff1a 另外开启cmd命令窗口 xff1a 一定要记住刷新权限 xff0c 否则可能拒

  • 虚拟机中三种网卡模式详细介绍

    虚拟机中三种网卡模式 vmware为我们提供了三种网络工作模式 xff0c 它们分别是 xff1a Bridged xff08 桥接模式 xff09 NAT xff08 网络地址转换模式 xff09 Host Only xff08 仅主机模

  • centos7 xfce轻量桌面环境和vnc安装

    一 centos7安装xfce轻量桌面环境 Linux的桌面环境gnome kde xfce lxde 等等使用比较https www cnblogs com chenmingjun p 8506995 html 1 安装额外yum源 yu

  • R语言学习笔记——空间自相关：全局Moran’I/局部Moran’I /Geary’c/Moran散点图

    data ChinaRD2 span class token operator lt span readRDS span class token punctuation span span class token string 34 gad

  • FIFO深度计算问题

    FIFO深度计算公式 xff1a fifo depth 61 burst length burst length X Y r clk w clk burst length xff1a 突发数据个数 X Y xff1a 读时钟周期里 xff0

  • 【游戏开发】游戏开发书籍汇总

    1 游戏设计的艺术 2 游戏设计的100个原理 3 我在美国学游戏设计 4 游戏新手村 xff1a 从零开始做游戏 5 Directx游戏开发终极指南 6 Windows游戏编程大师技巧 7 快乐之道 xff1a 游戏设计的黄金法则 人类的

  • Java~String类型空字符串和Null的区别以及判断方法

    一 区别 null表示的是一个对象的值 xff0c 而不是一个字符串 如声明一个对象的引用 xff0c String a 61 null 表示的是一个空字符串 xff0c 也就是说它的长度为0 如声明一个字符串String s 61 Str

  • 解读官方Android MediaPlayer API（1）

    public class MediaPlayerextends ObjectMediaPlayer class 能够用来使用来控制vudio video xff08 音频或视频 xff09 文件和流文件的播放 举个例子可以在 a targe

  • ACM 几何基础（1）

    点 point 定义 xff1a struct point double x y 线 line 定义 xff1a Struct line Point s e 精度差 Const double eps 61 1e 8 Int sgn doub

  • ACM 几何基础（2）

    判断两条线段是否相交 xff1a 矢量 如果一条线段的端点是有次序之分的话 xff0c 那么这种线段就称为 有向线段 xff0c 如果有向线段 p1p2 的起点 p1 在坐标的原点 xff0c 则可以把它称为矢量 p2 矢量的加减 设二维矢

  • ACM 几何基础（3）

    几何基础 xff08 3 xff09 求线段交点 xff1a 前面已经讲了如何判断两条线段是否相交 xff0c 现在我们来学下如何求线段的交点坐标 首先先了解下 xff1a 定比分点公式 公式介绍 数学中常用的重要公式之一 xff01 在

  • ACM 几何基础（4）

    几何基础 xff08 4 xff09 点到线段最短距离 xff1a 主要学下矢量的方法求解 xff1a 点到线段最短距离的运算与点到直线的最短距离的运算二者之间存在一定的差别 xff0c 即求点到线段最短距离时需要考虑参考点在沿线段方向的投

  • ACM 几何基础（5）

    几何基础 xff08 5 xff09 凸包 xff1a 在学凸包之前 xff0c 最好把叉积弄熟 xff01 定义 xff1a 对一个简单多边形来说 xff0c 如果给定其边界上或内部的任意两个点 xff0c 连接这两个点的线段上的所有点都

  • 【奇技淫巧】薅公司服务器羊毛，IntelliJ IDEA的远程开发

    前言 作为一个程序员 xff0c 在平时工作的时候 xff0c 你觉得电脑的内存多大才够用 xff0c 8G 16G 32G 其实内存对于程序员来说 xff0c 只能说是多多益善 xff0c 像我平时电脑可能一周重启一次 xff0c 开的东

  • ACM 几何基础（6）

    几何基础 xff08 6 xff09 求多边形面积 xff1a 要想计算多边形的面积我们可以转化为求多个三角形的面积之和得到 在解析几何里 xff0c ABC的面积可以通过如下方法求得 xff1a 点坐标 61 gt 边长 61 gt 海伦

  • 解读官方Android MediaPlayer API（2）

    有效和无效状态 xff1a 方法名有效状态无效状态注释getCurrentPosition Idle Initialized Prepared Started Paused Stopped PlaybackCompleted Error 成

  • 解读官方Android MediaPlayer API（3）

    权限 One may need to declare a corresponding WAKE LOCK permission lt uses permission gt element 嵌套类摘要 static interface str

  • Android开发艺术探索(连载)之View 的事件体系(一)view的基本知识

    一 xff0c View的位置参数关系 xff1a 1 view 的基础概念 xff08 略 xff09 xff1b 2 View中的 top bottom left right 的表示内容 xff1a 所以 view的宽高 xff1a W

随机推荐

热门标签