Titan笔记

  • 首页
  • Java
  • 数据结构
  • Web
  • C语言
  • Python
  • 杂谈
  • 逸笔挥墨
Titan笔记
分享学习、研究与开发过程中的点滴记忆
  1. 首页
  2. 数据结构
  3. 正文

[数据结构] 二叉搜索树的CURD(增删改查)操作

2020年3月17日 312点热度 2人点赞 0条评论

介绍

对于二叉搜索树的查找指定元素、查找最大元素、查找最小元素、删除指定元素、插入元素等基础操作。除了删除操作外,基本上都是使用的非递归函数解决。

Code

#include<stdio.h>
#include<stdlib.h>
// 二叉搜索树的各种操作 By Titan

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode {
  int Data;
  Position Left;
  Position Right;
};

//插入操作
BinTree Insert(BinTree BST,int X) {
  if(!BST) {
    BST = (BinTree)malloc(sizeof(struct TNode));
    BST->Data=X;
    BST->Left=BST->Right=NULL;
  } else {
    BinTree Parent,Cur=BST;
    while(Cur) {
      Parent=Cur;
      if(Cur->Data > X) {
        Cur=Cur->Left;
      } else if(Cur->Data < X) {
        Cur=Cur->Right;
      } else {
        return BST;
      }
    }
    BinTree TempNode = (BinTree)malloc(sizeof(struct TNode));
    TempNode->Data=X;
    TempNode->Left=TempNode->Right=NULL;
    if(Parent->Data>X) {
      Parent->Left=TempNode;
    } else {
      Parent->Right=TempNode;
    }
  }
  return BST;
}
//查找操作
//基础查找
BinTree Find(BinTree BST,int X) {
  if(!BST) {
    return NULL;
  }
  BinTree Found=NULL;
  while(BST) {
    if(BST->Data > X ) {
      BST=BST->Left;
    } else if(BST->Data < X) {
      BST=BST->Right;
    } else if(BST->Data == X) {
      Found=BST;
      break;
    }
  }
  return Found;
}
//找最小值
BinTree FindMin(BinTree BST) {
  if(!BST) {
    return NULL;
  }
  while(BST->Left) {
    BST=BST->Left;
  }
  return BST;
}
//找最大值
BinTree FindMax(BinTree BST) {
  if(!BST) {
    return NULL;
  }
  while(BST->Right) {
    BST=BST->Right;
  }
  return BST;
}

// 删除操作
BinTree Delete(BinTree BST,int X) {
  Position Tmp;
  if( !BST ) {
    printf("Not Found\n");
  } else {
    if( X < BST->Data ) {
      BST->Left = Delete( BST->Left, X );
    } else if( X > BST->Data ) {
      BST->Right = Delete( BST->Right, X );
    } else {
      if( BST->Left && BST->Right ) {
        Tmp = FindMin( BST->Right );
        BST->Data = Tmp->Data;
        BST->Right = Delete( BST->Right, BST->Data );
      } else {
        if( !BST->Left ) {
          BST = BST->Right;
        } else {
          BST = BST->Left;
        }
      }
    }
  }
  return BST;
}

//先序遍历
void preOrder(BinTree BST) {
  if(BST) {
    printf("%d ",BST->Data);
    preOrder(BST->Left);
    preOrder(BST->Right);
  }
}


int main(void) {
  int n,tempX;
  BinTree BST=NULL;
  // 数据读入,建立二叉树
  scanf("%d",&n);
  for(int i=0; i<n; i++) {
    scanf("%d",&tempX);
    BST = Insert(BST,tempX);
  }
  // 先序遍历
  preOrder(BST);
  printf("\n");
  // 寻找某个元素
  int toFind;
  printf("请输入要查找的元素:");
  scanf("%d",&toFind);
  BinTree FoundNode = Find(BST,toFind);
  if(FoundNode) {
    printf("%d is Found.\n",toFind,FoundNode);
  } else {
    printf("%d Not Found!\n",toFind);
  }
  // 寻找最大值
  BinTree FoundMax=FindMax(BST);
  if(FoundMax) {
    printf("Max: %d.\n",FoundMax->Data,FoundMax);
  } else {
    printf("Find Max ERROR!\n");
  }
  // 寻找最小值
  BinTree FoundMin=FindMin(BST);
  if(FoundMin) {
    printf("Min: %d.\n",FoundMin->Data,FoundMin);
  } else {
    printf("Find Min ERROR!\n");
  }
  // 删除元素
  int target;
  printf("请输入要删除的元素: ");
  scanf("%d",&target);
  BST = Delete(BST,target);
  preOrder(BST);


}

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: 二叉搜索树 二叉树
最后更新:2020年3月17日

Titan

兴趣广泛而无一精擅
想到什么,我总是渴望以代码的方式去呈现
永远年轻,永远热泪盈眶
Stay Hungry, Stay Foolish

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Titan

兴趣广泛而无一精擅
想到什么,我总是渴望以代码的方式去呈现
永远年轻,永远热泪盈眶
Stay Hungry, Stay Foolish

逸笔挥墨 - Titan的文学天地
文章分类
  • C语言 (4)
  • Hadoop (1)
  • Hive (3)
  • Java (19)
  • JavaWeb (4)
  • Linux运维之道 (1)
  • Mybatis学习笔记 (3)
  • Python (3)
  • SpringCloud (4)
  • Web (5)
  • Web前端 (4)
  • Web后端 (5)
  • 数据库 (1)
  • 数据结构 (10)
  • 杂谈 (3)
  • 诗词歌赋 (1)
  • 随摘 (2)
最新 热点 随机
最新 热点 随机
Spring Cloud 微服务学习笔记 - 负载均衡服务调用 Spring Cloud 微服务学习笔记 - Eureka 服务注册与发现 Spring Cloud 微服务学习笔记 - IDEA工程搭建 关于我和Titan笔记 Spring Cloud 微服务学习笔记 - 开篇 TitanEMS - Titan企业员工管理系统 - JavaWeb期末实践项目
Spring Cloud 微服务学习笔记 - 开篇TitanEMS - Titan企业员工管理系统 - JavaWeb期末实践项目2021年1月随摘2021年1月诗摘关于我和Titan笔记《梦之浮桥》中的几句
[Java] 日期与时间的一些操作 Spring Cloud 微服务学习笔记 - Eureka 服务注册与发现 关于我和Titan笔记 [PHP框架] ThinkPHP6 介绍、安装及配置 [数据结构] 队列的链式存储实现 [Python]随机生成大量的虚拟信息测试数据(姓名,手机号,ID,家庭住址等)
标签聚合
链式存储 Java 二叉树 Python Mybatis学习笔记 Apache-Hive 数据结构 JavaWeb
友情链接
  • Mttblog

COPYRIGHT © 2016 - 2021 Titan笔记. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

豫ICP备20001822号-1

豫公网安备 41010502004418号