在 C++ 中实现二叉树数据结构

Jinku Hu 2023年1月30日 2021年6月28日
  1. 在 C++ 中使用 struct 关键字实现二叉树
  2. 在 C++ 中实现计算树结构的大小和高度的函数和打印元素的函数
在 C++ 中实现二叉树数据结构

本文将讲解如何用 C++ 实现二叉树数据结构。

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

树是用于各种基本算法的抽象数据结构。它们通常是层次结构,其中需要有一个根节点及其子节点形成子树。此外,还有多种树结构类型,每种类型都适合特定需求并提供一些权衡。

二叉树是树数据结构的子类之一,它被定义为每个节点最多必须有两个子节点的树,包括指定为 leftright 的子节点。在这种情况下,我们使用 struct 函数实现一个二叉树,因为它声明了一个成员默认为 public 的类。二叉树中的一个节点包含两个指向左/右节点的指针以及需要的数据。请注意,我们声明了一个 int 成员来表示存储在节点上的数据,仅用于说明目的。

我们定义了一个构造函数,它接受一个整数作为参数并用它的值初始化 data 成员。然后,它用 nullptr 值初始化双节点指针,这是表示叶子节点的常用方法。示例驱动程序代码构建一个示例图并在每个节点中存储随机整数。二叉树有多种子类型,例如,完整二叉树是一种结构,其中每个节点都有 02 个子节点。另一种称为完美二叉树,其中所有内部节点都有两个子节点,并且所有叶子节点具有相同的深度。

#include <iostream>
#include <random>

using std::cout;
using std::endl;

struct BinTreeNode {
    int data;
    struct BinTreeNode *left;
    struct BinTreeNode *right;

    BinTreeNode() = default;
    explicit BinTreeNode(int d): data(d) {
        left = nullptr;
        right = nullptr;
    }
};

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
    std::random_device rd;
    std::mt19937 eng(rd());
    std::uniform_int_distribution<int> distr(MIN, MAX);

    auto root = new BinTreeNode(distr(eng));
    root->left = new BinTreeNode(distr(eng));
    root->right = new BinTreeNode(distr(eng));
    root->right->left = new BinTreeNode(distr(eng));
    root->right->right = new BinTreeNode(distr(eng));

    return EXIT_SUCCESS;
}

请注意,上面的代码产生了一个完整的二叉树结构,如下图所示。我们使用 new 运算符分配每个节点,并使用伪随机数生成器传递初始化值。

             root
          /        \
      left          right
      / \          /     \
nullptr nullptr left      right
               /   \      /    \
        nullptr nullptr nullptr nullptr

在 C++ 中实现计算树结构的大小和高度的函数和打印元素的函数

由于树结构是分治算法执行的形式,后一种方法通常用于实现操作其元素的功能。treeSize 函数检索表示所有节点数量的树的大小,包括根。请注意,我们只需要使用简单的递归并返回 root 值的大小(即 1)加上左/右节点的大小。

下一个函数是 treeHeight,它检索树的高度,通常称为从根到叶的最长路径中的节点数量。该函数还通过在两个子节点上调用自身并返回 root 值(即 1)的高度加上先前调用中的较大值来利用递归。

另一方面,printData 函数将每个节点的 data 成员输出到 cout 流。二叉树结构有多种遍历方式:中序遍历、前序遍历和后序遍历。

在下面的例子中,使用了中序遍历方式。该过程首先打印从最左边的叶子节点到右边相同深度的数据,然后移动到上层。下一个代码片段构造一个部分随机的二叉树,然后在其上调用上述每个函数。如果这些函数的递归性质乍一看似乎令人困惑,你应该尝试在较小的树对象上逐步调试它们,并观察每个递归函数调用的行为。

#include <iostream>
#include <random>

using std::cout; using std::endl;

struct BinTreeNode {
    int data;
    struct BinTreeNode *left;
    struct BinTreeNode *right;

    BinTreeNode() = default;
    explicit BinTreeNode(int d): data(d) {
        left = nullptr;
        right = nullptr;
    }
};

int treeSize(BinTreeNode *n) {
    if (n == nullptr)
        return 0;
    else
        return 1 + treeSize(n->left) + treeSize(n->right);
}

int treeHeight(BinTreeNode *n) {
    int lh, rh;

    if (n == nullptr)
        return -1;
    else {
        lh = treeHeight(n->left);
        rh = treeHeight(n->right);
        return 1 + (lh > rh ? lh : rh);
    }
}

void printData(BinTreeNode *n) {
    if (n != nullptr) {
        printData(n->left);
        cout << n->data << "; ";
        printData(n->right);
    }
}

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
    std::random_device rd;
    std::mt19937 eng(rd());
    std::uniform_int_distribution<int> distr(MIN, MAX);

    auto root = new BinTreeNode(distr(eng));
    auto tmp = root;

    auto iter = 100;
    while (iter > 0) {
        auto val = distr(eng);
        if (val % 5 == 0) {
            tmp->left = new BinTreeNode(distr(eng));
            tmp = tmp->left;
        } else if (val % 4 == 0) {
            tmp->right = new BinTreeNode(distr(eng));
            tmp = tmp->right;
        } else if (val % 6 == 0) {
            tmp->left = new BinTreeNode(distr(eng));
        } else if (val % 100 == 0) {
            tmp = root;
        } else if (val % 2 == 0) {
            tmp->right = new BinTreeNode(distr(eng));
        }
        iter -= 1;
    }

    cout << "size of tree = " << treeSize(root) << endl;
    cout << "height of tree = " << treeHeight(root) << endl;
    printData(root);

    return EXIT_SUCCESS;
}

输出:

size of tree = 45
height of tree = 37
...(elements in the tree)
Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn

相关文章 - C++ Data Structure