在 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