在 C++ 中實現二叉樹資料結構
本文將講解如何用 C++ 實現二叉樹資料結構。
在 C++ 中使用 struct 關鍵字實現二叉樹
樹是用於各種基本演算法的抽象資料結構。它們通常是層次結構，其中需要有一個根節點及其子節點形成子樹。此外，還有多種樹結構型別，每種型別都適合特定需求並提供一些權衡。
二叉樹是樹資料結構的子類之一，它被定義為每個節點最多必須有兩個子節點的樹，包括指定為 left 和 right 的子節點。在這種情況下，我們使用 struct 函式實現一個二叉樹，因為它宣告瞭一個成員預設為 public 的類。二叉樹中的一個節點包含兩個指向左/右節點的指標以及需要的資料。請注意，我們宣告瞭一個 int 成員來表示儲存在節點上的資料，僅用於說明目的。
我們定義了一個建構函式，它接受一個整數作為引數並用它的值初始化 data 成員。然後，它用 nullptr 值初始化雙節點指標，這是表示葉子節點的常用方法。示例驅動程式程式碼構建一個示例圖並在每個節點中儲存隨機整數。二叉樹有多種子型別，例如，完整二叉樹是一種結構，其中每個節點都有 0 或 2 個子節點。另一種稱為完美二叉樹，其中所有內部節點都有兩個子節點，並且所有葉子節點具有相同的深度。
#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)
