HOWTO · C++
在 C++ 中實現二叉樹資料結構
本文演示瞭如何用 C++ 實現二叉樹資料結構。
本頁內容
在 C++ 中，可以用包含一個值與兩個子節點連結的 struct 表示二元樹。以下範例會建立一棵小型樹、計算節點數、以邊數衡量樹高，並透過中序遍歷列印節點值。
使用節點 struct 表示二元樹
二元樹的每個節點最多有兩個子節點，通常稱為 left 和 right。struct 是一種類別型別，其成員預設為公開，因此適合用來表示這種簡單的資料結構。每個節點儲存一個整數，並透過 std::unique_ptr 擁有自己的子節點；空指標表示該子節點連結不存在。空指標本身不代表節點是葉節點：左右兩個子節點連結都不存在的節點，才是葉節點。
滿二元樹的每個節點都恰有零個或兩個子節點。完美二元樹除了符合這項條件，所有葉節點也都位於相同深度。下方範例建立的是滿二元樹，但不是完全二元樹：最後一層有空位，後面才出現其他節點。這些名稱描述不同的樹形，不能互換使用。
建立一棵小型二元樹
程式會建立以下固定形狀的樹，並選用容易追蹤遍歷順序的值：8 (left: 3, right: 10 (left: 9, right: 14))。
std::make_unique 會建立節點並傳回擁有該節點的指標。將指標移入子節點會轉移所有權，因此根節點會擁有整棵樹；根節點離開作用範圍時，所有節點都會自動釋放。這樣就不必像直接以 new 配置記憶體時一樣手動清理。
執行此範例。程式碼區塊保留原始內容，其中的 size =、height = 和 inorder = 標籤仍為英文。
#include <iostream>
#include <memory>
struct BinTreeNode {
int data;
std::unique_ptr<BinTreeNode> left;
std::unique_ptr<BinTreeNode> right;
explicit BinTreeNode(int value) : data(value) {}
};
int treeSize(const BinTreeNode* node) {
if (node == nullptr) {
return 0;
}
return 1 + treeSize(node->left.get()) + treeSize(node->right.get());
}
int treeHeight(const BinTreeNode* node) {
if (node == nullptr) {
return -1;
}
const int leftHeight = treeHeight(node->left.get());
const int rightHeight = treeHeight(node->right.get());
return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}
void printData(const BinTreeNode* node) {
if (node == nullptr) {
return;
}
printData(node->left.get());
std::cout << node->data << ' ';
printData(node->right.get());
}
int main() {
auto root = std::make_unique<BinTreeNode>(8);
root->left = std::make_unique<BinTreeNode>(3);
root->right = std::make_unique<BinTreeNode>(10);
root->right->left = std::make_unique<BinTreeNode>(9);
root->right->right = std::make_unique<BinTreeNode>(14);
std::cout << "size = " << treeSize(root.get()) << '\n';
std::cout << "height = " << treeHeight(root.get()) << '\n';
std::cout << "inorder = ";
printData(root.get());
std::cout << '\n';
}
這些函式接收節點指標，但不取得所有權。以 root.get() 呼叫函式，可讓函式存取這棵樹，同時由擁有它的 unique_ptr 負責管理生命週期。相同的遞迴定義也適用於任何形狀的樹。程式碼區塊維持原樣，因此其中列印的 size =、height = 和 inorder = 標籤仍為英文。
計算節點數與樹高
treeSize 在子樹不存在時傳回零；否則會計入目前節點，再加上左右子樹的節點數。treeHeight 在子樹不存在時傳回 -1，接著將較高子樹的高度加一。依照這個定義，樹高是根節點到葉節點最長路徑上的邊數：葉節點的高度為 0，上方範例中的樹高為 2。有些定義計算的是路徑上的節點數，因此葉節點高度為 1；選定一種定義後，請始終一致使用。
使用中序遍歷列印節點
printData 會先走訪左子樹，再列印目前節點的值，最後走訪右子樹。這就是中序遍歷；對二元搜尋樹而言，這種遍歷會依排序順序列印值；對一般二元樹而言，則只是依照這個走訪順序列印。詳細說明請參閱中序遍歷指南。
若要追蹤遞迴，可觀察函式在每個節點的執行順序：先一路向左，直到沒有子節點；回到父節點時列印其值，接著處理右子樹。因此，範例中的值會依序顯示為 3 8 9 10 14。這棵樹有五個節點，以邊數計算的高度為二。範例是可獨立使用的程式；你可以調整節點值的型別或新增操作，但要妥善管理所有權，並一致採用所選的樹高定義。
