在 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)
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