21xrx.com
2025-03-27 00:16:48 Thursday
文章检索 我的文章 写文章
C++ STL中的二叉树实现
2023-06-29 10:02:29 深夜i     --     --
C++ STL 二叉树实现

二叉树是一种常见的数据结构，我们可以利用二叉树来存储和操作数据。在C++ STL中，我们可以使用二叉树容器来实现二叉树的功能。

C++ STL提供了两种二叉树容器，一种是set，一种是map。set只能存储关键字，而map则可以存储关键字和对应的值，这两者都是用二叉树实现的。

在使用二叉树容器之前，我们需要先了解二叉树的基本概念：

1. 二叉树是由节点组成的非线性结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

2. 一个节点的子节点可能为空，但它的父节点一定存在，除根节点外，每个节点都有唯一的父节点。

3. 在二叉树中，每个节点的左子树和右子树也分别是二叉树。

在set和map中，每个节点被封装成一个pair类型。pair的第一个元素是关键字，第二个元素是值。通过pair类型，我们可以将二叉树中的关键字和对应的值进行存储和检索。

下面是一段使用set实现二叉树的例子：

#include <iostream>
#include <set>
using namespace std;
int main()
{
  set<int> myset; // 创建一个set对象
  myset.insert(5); // 插入元素
  myset.insert(2);
  myset.insert(7);
  myset.insert(3);
  myset.insert(6);
  // 遍历set
  set<int>::iterator it;
  for (it = myset.begin(); it != myset.end(); it++)
    cout << *it << " ";
  cout << endl;
  // 查找元素
  it = myset.find(3);
  if (it != myset.end())
    cout << "3 is found" << endl;
  // 删除元素
  myset.erase(2);
  return 0;
}

上述代码创建了一个set容器，然后向其中插入5、2、7、3、6这几个元素，之后遍历了set并输出了所有元素。接着利用find函数查找了数字3，最后删除了数字2。

对于map容器的使用与set类似，只不过map可以存储键值对而set只能存储关键字。我们可以使用下面的代码来创建一个map容器：

#include <iostream>
#include <map>
using namespace std;
int main()
{
  map<string, int> mymap; // 创建一个map对象
  mymap.insert(pair<string, int>("Tom", 23)); // 插入键值对
  mymap.insert(pair<string, int>("Sam", 29));
  mymap.insert(pair<string, int>("Peter", 27));
  mymap.insert(pair<string, int>("Mary", 25));
  mymap.insert(pair<string, int>("John", 26));
  // 遍历map
  map<string, int>::iterator it;
  for (it = mymap.begin(); it != mymap.end(); it++)
    cout << it->first << ":" << it->second << endl;
  // 查找键
  it = mymap.find("John");
  if (it != mymap.end())
    cout << "John is " << it->second << " years old" << endl;
  // 删除元素
  mymap.erase("Peter");
  return 0;
}

上述代码创建了一个map容器，然后向其中插入了5个键值对，最后遍历输出了所有键值对。接着使用find函数查找键为"John"的键值对，并输出了John的年龄，最后删除了键为"Peter"的键值对。

总的来说，C++ STL中的二叉树容器为我们操作二叉树提供了方便的工具和接口，简化了我们的编程工作。掌握这些容器的使用方法，可以让我们更加高效地实现功能强大的数据结构和算法。

  
  

评论区