21xrx.com
2024-11-22 11:53:07 Friday
登录
文章检索 我的文章 写文章
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中的二叉树容器为我们操作二叉树提供了方便的工具和接口，简化了我们的编程工作。掌握这些容器的使用方法，可以让我们更加高效地实现功能强大的数据结构和算法。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复