用 C++ 实现二叉搜索树数据结构

Jinku Hu 2023年10月12日
  1. 在 C++ 中使用 struct 关键字实现二叉搜索树
  2. 用 C++ 实现二叉搜索树的二叉搜索算法
用 C++ 实现二叉搜索树数据结构

本指南将演示如何在 C++ 中实现二叉搜索树数据结构。

在 C++ 中使用 struct 关键字实现二叉搜索树

二叉搜索树(BST)是二叉树数据结构的特例。该数据结构通常用于存储元素的排序列表,以便使用二进制搜索算法进行快速搜索。与常规二叉树相比,BST 在每个节点中都有一个特殊的数据成员,称为,它必须具有唯一的值。

BST 中的每个节点都应满足以下要求:key 值必须大于其左孩子的子树中的所有键,并且小于其右孩子的子树中的所有键。前面的语句暗示具有较小键值的元素将定位在树层次结构的左侧;这导致使用二叉搜索的最佳结构。

在下面的示例代码中,我们定义了一个名为 BSTreeNodestruct,它由两个指向左/右节点的指针和一个表示键的 string 成员组成。请注意,我们只是实现了 BST 的最简单版本,其中键值与节点中存储的数据相同。

一般来说,程序员可以根据具体问题的需要,自由定义一个 BST 节点来存储其他数据成员。这个定义最适合模拟字符串的排序数组,需要搜索给定的字符串(键)。在我们实现二叉搜索功能之前,需要从头开始构建 BST 对象。因此,我们使用预定义的字符串向量来初始化新的二叉搜索树。

insertNode 函数是递归实现,用于在树的根作为参数传递时创建一个新的子 BSTreeNode。如果我们需要自己创建一个根节点,你可以声明一个指向 BSTreeNode 类型的指针,将 nullptr 分配给它,然后将它传递给 insertNode 以及需要存储在那里的相应 string 值。一旦我们使用 v1 内容初始化列表,就可以调用 printTree 函数以按称为 BST 的 inorder 遍历的排序顺序打印所有键值。

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string &k) {
  if (root == nullptr) {
    root = new BSTreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

void printTree(BSTreeNode *n) {
  if (n != nullptr) {
    printTree(n->left);
    cout << n->key << "; ";
    printTree(n->right);
  }
}

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printTree(root);

  return EXIT_SUCCESS;
}

输出:

aim; born; camel; maya; wind; xen; zero;

用 C++ 实现二叉搜索树的二叉搜索算法

由于排序,二进制搜索算法在 BST 结构上是有效的,其中键存储在层次结构中。BST 实现了三个主要操作:插入、删除和查找。

在下面的例子中,我们更多地关注查找。findNode 函数负责在 BST 中查找给定键,该键被传递给使用其根节点的函数。此命令具有递归性质,并返回指向存储密钥的 BSTreeNode 的指针。如果在任何节点中都找不到键值,则返回 nullptr。为了更好地演示,我们还实现了一个 printNode 函数,该函数接受节点指针并将键值输出到 cout 流,以直接在函数中链接 findNode 函数返回值以打印它。

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct BSTreeNode {
  string key;
  struct BSTreeNode *left{};
  struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string &k) {
  if (root == nullptr) {
    root = new BSTreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

BSTreeNode *findNode(BSTreeNode *root, const string &k) {
  if (root == nullptr) return nullptr;

  if (k == root->key) return root;

  if (k < root->key)
    return findNode(root->left, k);
  else
    return findNode(root->right, k);
}

void printNode(BSTreeNode *n) {
  if (n != nullptr) {
    cout << n->key << endl;
  } else {
    cout << "Not a valid node!" << endl;
  }
}

int main() {
  std::vector<string> v1{"camel", "wind", "zero", "maya", "aim", "born", "xen"};

  BSTreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }

  printNode(findNode(root, "zero"));
  printNode(findNode(root, "zeroo"));

  return EXIT_SUCCESS;
}

输出:

zero
Not a valid node!
作者: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

DelftStack.com 创始人。Jinku 在机器人和汽车行业工作了8多年。他在自动测试、远程测试及从耐久性测试中创建报告时磨练了自己的编程技能。他拥有电气/电子工程背景,但他也扩展了自己的兴趣到嵌入式电子、嵌入式编程以及前端和后端编程。

LinkedIn Facebook

相关文章 - C++ Data Structure