AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构 动态查找与二叉排序树

2022-12-04 123
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构 动态查找与二叉排序树

1. DS二叉排序树之创建和插入


题目描述


给出一个数据序列，建立二叉排序树，并实现插入功能


对二叉排序树进行中序遍历，可以得到有序的数据序列


输入


第一行输入t，表示有t个数据序列


第二行输入n，表示首个序列包含n个数据


第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开


第四行输入m，表示要插入m个数据


从第五行起，输入m行，每行一个要插入的数据，都是自然数且和前面的数据不等


以此类推输入下一个示例


输出


第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到


从第二行起，输出插入第m个数据后的有序序列，输出m行


以此类推输出下一个示例的结果


输入样例


1

6

22 33 55 66 11 44

3

77

50

10


输出样例


11 22 33 44 55 66

11 22 33 44 55 66 77

11 22 33 44 50 55 66 77

10 11 22 33 44 50 55 66 77


参考代码

#include<iostream>
using namespace std;
struct Node
{
  int data;
  struct Node* leftTree;
  struct Node* rightTree;
};
class BSTree
{
private:
  Node* head = new Node();
  Node* p = new Node();
public:
  BSTree()
  {
    head->data = -1;
    head->leftTree = head->rightTree = NULL;
  }
  void Create();
  void Insert(Node* p,int e);
  void InOrderTraverse(Node* p);
};
void BSTree::Create()
{
  int t;
  int n,e;
  cin >> t;
  while (t--)
  {
    cin >> n;
    while (n--)
    {
      cin >> e;
      if (head->data == -1)head->data = e;
      else
      {
        Insert(head,e);
      }
    }
    InOrderTraverse(head);
    cout << endl;
    cin >> n;
    while (n--)
    {
      cin >> e;
      Insert(head, e);
      InOrderTraverse(head);
      cout << endl;
    }
  }
}
void BSTree::Insert(Node *p,int e)
{
  if (e > p->data&&p->rightTree==NULL) 
  {
    Node* s = new Node();
    s->data = e;
    s->leftTree = s->rightTree = NULL;
    p->rightTree = s;
  }
  else if (e < p->data && p->leftTree == NULL)
  {
    Node* s = new Node();
    s->data = e;
    s->leftTree = s->rightTree = NULL;
    p->leftTree = s;
  }
  else if (e > p->data && p->rightTree != NULL)
  {
    Insert(p->rightTree, e);
  }
  else if (e < p->data && p->leftTree != NULL)
  {
    Insert(p->leftTree, e);
  }
}
void BSTree::InOrderTraverse(Node *p)
{
  if(p->leftTree!=NULL)InOrderTraverse(p->leftTree);
  cout << p->data << " ";
  if(p->rightTree!=NULL)InOrderTraverse(p->rightTree);
}
int main()
{
  BSTree bst;
  bst.Create();
  return 0;
}


2. DS二叉排序树之查找


题目描述


给出一个数据序列，建立二叉排序树，并实现查找功能


对二叉排序树进行中序遍历，可以得到有序的数据序列


输入

第一行输入t，表示有t个数据序列


第二行输入n，表示首个序列包含n个数据


第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开


第四行输入m，表示要查找m个数据


从第五行起，输入m行，每行一个要查找的数据，都是自然数


以此类推输入下一个示例


输出


第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到


从第二行起，输出查找结果，如果查找成功输出查找次数，如果查找失败输出-1


以此类推输出下一个示例的结果


输入样例


1

6

22 33 55 66 11 44

7

11

22

33

44

55

66

77


输出样例


11 22 33 44 55 66

2

1

2

4

3

4

-1


参考代码

#include<iostream>
using namespace std;
struct Node
{
  int data;
  struct Node* leftTree;
  struct Node* rightTree;
};
class BSTree
{
private:
  Node* head = new Node();
  int count = 0;
  //Node* p = new Node();
public:
  BSTree()
  {
    head->data = -1;
    head->leftTree = head->rightTree = NULL;
  }
  void Create();
  void Insert(Node* p, int e);
  void InOrderTraverse(Node* p);
  int Check(Node *p,int e);
};
void BSTree::Create()
{
  int t;
  int n, e;
  cin >> t;
  while (t--)
  {
    cin >> n;
    while (n--)
    {
      cin >> e;
      if (head->data == -1)head->data = e;
      else
      {
        Insert(head, e);
      }
    }
    InOrderTraverse(head);
    cout << endl;
    cin >> n;
    while (n--)
    {
      cin >> e;
      count = 0;
      int flag=Check(head,e);
      if (flag==1)cout << count << endl;
      else cout <<"-1" <<endl;
    }
  }
}
void BSTree::Insert(Node* p, int e)
{
  if (e > p->data && p->rightTree == NULL)
  {
    Node* s = new Node();
    s->data = e;
    s->leftTree = s->rightTree = NULL;
    p->rightTree = s;
  }
  else if (e < p->data && p->leftTree == NULL)
  {
    Node* s = new Node();
    s->data = e;
    s->leftTree = s->rightTree = NULL;
    p->leftTree = s;
  }
  else if (e > p->data && p->rightTree != NULL)
  {
    Insert(p->rightTree, e);
  }
  else if (e < p->data && p->leftTree != NULL)
  {
    Insert(p->leftTree, e);
  }
}
int BSTree::Check(Node* p,int e)
{
  count++;
  if (e > p->data)
  {
    if (p->rightTree == NULL)return -1;
    Check(p->rightTree, e);
  }
  else if (e == p->data)return 1;
  else if (e < p->data)
  {
    if (p->leftTree == NULL)return -1;
    Check(p->leftTree, e);
  }
}
void BSTree::InOrderTraverse(Node* p)
{
  if (p->leftTree != NULL)InOrderTraverse(p->leftTree);
  cout << p->data << " ";
  if (p->rightTree != NULL)InOrderTraverse(p->rightTree);
}
int main()
{
  BSTree bst;
  bst.Create();
  return 0;
}


3. DS二叉排序树之删除


题目描述


给出一个数据序列，建立二叉排序树，并实现删除功能


对二叉排序树进行中序遍历，可以得到有序的数据序列


输入


第一行输入t，表示有t个数据序列


第二行输入n，表示首个序列包含n个数据


第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开


第四行输入m，表示要删除m个数据


从第五行起，输入m行，每行一个要删除的数据，都是自然数


以此类推输入下一个示例


输出


第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到


从第二行起，输出删除第m个数据后的有序序列，输出m行


以此类推输出下一个示例的结果


输入样例


1

6

22 33 55 66 11 44

3

66

22

77


输出样例


11 22 33 44 55 66

11 22 33 44 55

11 33 44 55

11 33 44 55


参考代码

#include<iostream>
using namespace std;
struct Node
{
  int data;
  struct Node* leftTree;
  struct Node* rightTree;
};
class BSTree
{
private:
  Node* head = new Node();
  Node* temp = new Node();
  Node* pre = new Node();
public:
  BSTree()
  {
    head->data = -1;
    head->leftTree = head->rightTree = NULL;
  }
  void Create();
  void Insert(Node* p, int e);
  void InOrderTraverse(Node* p);
  int Check(Node* p,int e);
  int Delete(Node* p, int e);
};
void BSTree::Create()
{
  int t;
  int n, e;
  cin >> t;
  while (t--)
  {
    cin >> n;
    while (n--)
    {
      cin >> e;
      if (head->data == -1)head->data = e;
      else
      {
        Insert(head, e);
      }
    }
    InOrderTraverse(head);
    cout << endl;
    cin >> n;
    while (n--)
    {
      cin >> e;
      int flag = Check(head, e);
      if(flag==1)Delete(temp, e);
      InOrderTraverse(head);
      cout << endl;
    }
  }
}
void BSTree::Insert(Node* p, int e)
{
  if (e > p->data && p->rightTree == NULL)
  {
    Node* s = new Node();
    s->data = e;
    s->leftTree = s->rightTree = NULL;
    p->rightTree = s;
  }
  else if (e < p->data && p->leftTree == NULL)
  {
    Node* s = new Node();
    s->data = e;
    s->leftTree = s->rightTree = NULL;
    p->leftTree = s;
  }
  else if (e > p->data && p->rightTree != NULL)
  {
    Insert(p->rightTree, e);
  }
  else if (e < p->data && p->leftTree != NULL)
  {
    Insert(p->leftTree, e);
  }
}
int BSTree::Check(Node* p, int e)
{
  if (e > p->data)
  {
    if (p->rightTree == NULL)return -1;
    if (p->rightTree->data == e)
    {
      if (p->rightTree->leftTree == NULL && p->rightTree->rightTree == NULL)pre = p;
    }
    Check(p->rightTree, e);
  }
  else if (e == p->data)
  {
    temp = p;
    return 1;
  }
  else if (e < p->data)
  {
    if (p->leftTree == NULL)return -1;
    if (p->leftTree->data == e)
    {
      if (p->leftTree->leftTree == NULL && p->leftTree->rightTree == NULL)pre = p;
    }
    Check(p->leftTree, e);
  }
}
int BSTree::Delete(Node* p, int e)
{
  if (!p->rightTree&&p->leftTree!=NULL)
  {
    Node* q = new Node();
    q = p;
    p = p->leftTree;
    delete q;
  }
  else if (!p->leftTree&&p->rightTree!=NULL)
  {
    Node* q = new Node();
    q = p;
    p = p->leftTree;
    delete q;
  }
  else if (p->leftTree==NULL && p->rightTree==NULL)
  {
    if (pre->leftTree->data == e)pre->leftTree = NULL;
    else pre->rightTree = NULL;
    Node* q = new Node();
    q = p;
    delete q;
  }
  else
  {
    Node* q = new Node();
    Node* s = new Node();
    q = p;
    s = p->leftTree;
    while (s->rightTree)
    {
      q = s;
      s = s->rightTree;
    }
    p->data = s->data;
    if (q != p)q->rightTree = s->leftTree;
    else q->leftTree = s->leftTree;
    delete s;
  }
  return 0;
}
void BSTree::InOrderTraverse(Node* p)
{
  if (p->leftTree != NULL)InOrderTraverse(p->leftTree);
  cout << p->data << " ";
  if (p->rightTree != NULL)InOrderTraverse(p->rightTree);
}
int main()
{
  BSTree bst;
  bst.Create();
  return 0;
}


4. DS查找—二叉树平衡因子


题目描述


二叉树用数组存储，将二叉树的结点数据依次自上而下,自左至右存储到数组中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点在数组中用0来表示。


计算二叉树每个结点的平衡因子，并按后序遍历的顺序输出结点的平衡因子。


–程序要求–

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求


输入


测试次数t


每组测试数据一行，数组元素个数n，后跟n个字符，二叉树的数组存储。


输出


对每组测试数据，按后序遍历的顺序输出树中结点的平衡因子（测试数据没有空树）


输入样例


2

6 ABC00D

24 ABCD0EF0000H00000000000I


输出样例


B 0

D 0

C 1

A -1

D 0

B 1

I 0

H 1

E 2

F 0

C 2

A -2


参考代码

#include<iostream>
using namespace std;
int getheight(char* bst, int i, int n)
{
  if (bst[i] == '0' || i >= n)
    return 0;
  else
  {
    int l = getheight(bst, 2 * i + 1, n)+1;
    int r = getheight(bst, 2 * i + 2, n)+1;
    return l > r ? l : r;
  }
}
void func(char *bst,int n,int i)
{
  if (i < n)
  {
    if (bst[i] != '0')
    {
      func(bst, n, 2 * i + 1);
      func(bst, n, 2 * i + 2);
      cout << bst[i] << " ";
      int height = getheight(bst, 2 * i + 1, n) - getheight(bst, 2 * i + 2, n);
      cout << height << endl;
    }
  }
}
int main()
{
  int t;
  cin >> t;
  while (t--)
  {
    int n;
    cin >> n;
    char* bst;
    bst = new char[n];
    for (int i = 0;i < n;i++)
      cin >> bst[i];
    func(bst, n, 0);
  }
  return 0;
}


文章标签：
C++
C语言
存储
关键词：
数据结构二叉排序树
数据结构动态
数据结构查找
数据结构动态查找
wstqfqdpnmll4
目录
相关文章
技术蜜糖罐
|
存储 Go iOS开发
掌握Go语言：探索Go语言指针，解锁高效内存操作与动态数据结构的奥秘（19）
掌握Go语言：探索Go语言指针，解锁高效内存操作与动态数据结构的奥秘（19）
技术蜜糖罐
149 0
柠檬叶子C
|
存储 算法 编译器
【霍洛维兹数据结构】栈和队列 | 动态循环队列 | 迷宫问题 | 表达式 | 多重栈&多重队列
【霍洛维兹数据结构】栈和队列 | 动态循环队列 | 迷宫问题 | 表达式 | 多重栈&多重队列
柠檬叶子C
221 0
ephemerals__
|
7月前
|
C语言 C++ 容器
【数据结构】二叉搜索树（二叉排序树）
本文介绍了二叉搜索树（Binary Search Tree, BST）的定义、实现及其性能分析。二叉搜索树是一种特殊的二叉树，其特点是左子树所有节点值小于根节点值，右子树所有节点值大于根节点值，且每个子树也满足此特性。文中详细讲解了BST的节点结构、插入、查找、删除等操作的实现，并通过C++代码展示了这些功能。此外，还讨论了BST的性能：在理想情况下，时间复杂度接近O(logN)，但在最坏情况下可能退化为O(N)。为了提高效率，后续将学习自平衡二叉搜索树如AVL树和红黑树。掌握BST有助于理解STL中的set和map容器。感谢阅读，欢迎点赞支持。
ephemerals__
558 9
RossyYan
|
9月前
|
算法 C++
【C++数据结构——查找】二叉排序树（头歌实践教学平台习题）【合集】
【数据结构——查找】二叉排序树（头歌实践教学平台习题）【合集】 目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果： 任务描述 本关任务：实现二叉排序树的基本算法。 相关知识 为了完成本关任务，你需要掌握：二叉树的创建、查找和删除算法。具体如下： (1)由关键字序列(4,9,0,1,8,6,3,5,2,7)创建一棵二叉排序树bt并以括号表示法输出。 (2)判断bt是否为一棵二叉排序树。 (3)采用递归方法查找关键字为6的结点,并输出其查找路径。 (4)分别删除bt中关键
RossyYan
230 11
【C++数据结构——查找】二叉排序树（头歌实践教学平台习题）【合集】
码农阿豪
|
存储 NoSQL Redis
Redis系列学习文章分享---第十六篇（Redis原理1篇--Redis数据结构-动态字符串，insert，Dict,ZipList,QuickList,SkipList,RedisObject）
Redis系列学习文章分享---第十六篇（Redis原理1篇--Redis数据结构-动态字符串，insert，Dict,ZipList,QuickList,SkipList,RedisObject）
码农阿豪
173 1
java冯坚持
|
存储 算法 数据管理
数据结构与算法学习二零：二叉排序树（BST）、平衡二叉树（AVL）
这篇文章通过需求分析、代码实现和测试验证，详细介绍了二叉排序树的创建、遍历和删除操作，以及二叉平衡树（AVL）的自平衡特性和单旋转操作，旨在提高树结构在数据管理中的效率和性能。
java冯坚持
290 0
数据结构与算法学习二零：二叉排序树（BST）、平衡二叉树（AVL）
小徐在进步
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
328 2
冰点.
|
存储 缓存 NoSQL
Redis从入门到精通之底层数据结构简单动态字符串(SDS)详解
SDS是Redis中的一种字符串类型，它是一种二进制安全的字符串，由简单动态字符串（SDS）实现。SDS支持多种数据结构，其中字符串（String）是最常用的一种数据结构之一。SDS的优点在于它可以避免C字符串常见的问题，比如缓冲区溢出和内存泄露等。SDS的常数复杂度获取字符串长度和杜绝缓冲区溢出可以避免使用strlen和strcat函数时的一些问题。同时，SDS的空间预分配和惰性空间释放两种策略可以减少修改字符串的内存重新分配次数。SDS也是二进制安全的，因为它不是以空字符串来判断字符串是否结束，而是以len属性表示的长度来判断字符串是否结束。SDS还兼容部分C字符串函数
冰点.
921 86
Redis从入门到精通之底层数据结构简单动态字符串(SDS)详解
sunrr
|
弹性计算 负载均衡 NoSQL
NoSQL数据库如何支持动态数据结构？
【6月更文挑战第11天】NoSQL数据库如何支持动态数据结构？
sunrr
150 2
天玑y
|
C++
数据结构（顺序表 动态定义
数据结构（顺序表 动态定义
天玑y
93 2

热门文章

最新文章

  • 1
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
  • 2
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
  • 3
    软考中级软件设计师专项-数据结构与算法上篇
  • 4
    【Redis】常用数据结构之List篇：从常用命令到典型使用场景
  • 5
    Redis数据结构：别小看这5把“瑞士军刀”，用好了性能飙升！
  • 6
    Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
  • 7
    【Redis】 常用数据结构之String篇：从SET/GET到INCR的超全教程
  • 8
    Redis基础命令与数据结构概览
  • 9
    GPS北斗双模技术应用开发研究—数据结构扩展
  • 10
    堆和栈的区别 【转】
  • 1
    232.用栈实现队列，225. 用队列实现栈
    90
  • 2
    栈区的非法访问导致的死循环(x64)
    78
  • 3
    Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
    220
  • 4
    Redis设计与实现——数据结构与对象
    220
  • 5
    快速排序-数据结构与算法
    435
  • 6
    16.1k star! 只需要DDL就能一键生成数据库关系图！开源神器ChartDB让你的数据结构"看得见"
    1318
  • 7
    java实现队列数据结构代码详解
    181
  • 8
    Java 中 .length 的使用方法：深入理解 Java 数据结构中的长度获取机制
    568
  • 9
    线性数据结构详解
    176
  • 10
    为什么要学习数据结构与算法
    126

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    一文了解：阿里云对象存储OSS是什么？