Titan笔记

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

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

2020年3月17日 923点热度 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

不为岁月流逝蹉跎,不为潮流的势头去附和

点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论
最新 热点 随机
最新 热点 随机
Docker配置IPv6容器网络支持 什么是Elastic Stack,ELK的发展历程 K8s中Pod的基本概念 Pushkin AI - 基于OpenAI-ChatGPT / GPT3的问答机器人 云原生 - 浅谈容器基础与K8S架构设计 腾讯Serverless体验,使用TypeScript编写并部署云函数
Docker配置IPv6容器网络支持
Spring与Mybatis的整合 [PHP] Laravel框架介绍、安装及配置 Go-Proxy-Checker,一款基于Go编写的高性能代理服务器验证工具 RecyclerView组件的使用 [Web] CSS 中 Display(显示) 与 Visibility(可见性)的区别与用法 Titan商店 - 又一个Web静态项目
分类
  • Android
  • C语言
  • Elasticsearch
  • Hadoop
  • Hive
  • Java
  • JavaWeb
  • Kubernetes
  • Linux运维之道
  • Mybatis学习笔记
  • Python
  • SpringCloud
  • Web
  • Web前端
  • Web后端
  • 云原生
  • 并发编程
  • 开发工具
  • 数据库
  • 数据结构
  • 杂谈
  • 移动开发
  • 移动测试
  • 诗词歌赋
  • 软件测试
  • 逸笔挥墨
  • 随摘
标签聚合
Mybatis学习笔记 JavaWeb 链式存储 数据结构 Python Java Apache-Hive 二叉树

COPYRIGHT © 2013-2021 Titan. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

豫ICP备20001822号-1

豫公网安备 41010502004418号