在 C++ 中實現二叉搜尋樹的中序遍歷
Jinku Hu
2023年10月12日
本文將講解如何在 C++ 中實現二叉搜尋樹的中序遍歷。
使用中序遍歷列印二叉搜尋樹的內容
二叉搜尋樹的構造使得每個節點的鍵必須大於其左子樹中的所有鍵，並且小於右子樹中的所有鍵。
為了簡單起見，我們在這裡只考慮不平衡樹，但在實際場景中，二叉搜尋樹的效率來自平衡性質，其中根的每個子樹具有大致相同的高度。
可以使用三種不同的方法遍歷二叉樹：中序、前序和後序。二叉搜尋樹的中序遍歷產生按非遞減順序排序的元素。這個版本通常從最左邊的節點開始，按照先遍歷左子樹的順序，然後是根節點，最後是右子樹。
請注意以下程式碼片段輸出和整數插入樹時的順序。
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct TreeNode {
int key;
struct TreeNode *left{};
struct TreeNode *right{};
};
void insertNode(TreeNode *&root, const int k) {
if (root == nullptr) {
root = new TreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
void printTreeInorder(TreeNode *n) {
if (n != nullptr) {
printTreeInorder(n->left);
cout << n->key << "; ";
printTreeInorder(n->right);
}
}
int main() {
std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};
TreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printTreeInorder(root);
cout << endl;
return EXIT_SUCCESS;
}
2; 3; 5; 9; 11; 15; 20; 23;
或者，我們可能需要利用前序或後序遍歷來訪問二叉搜尋樹中的節點。我們只需要在 printTree* 函式中移動 cout << n->key << "; " 行來修改遍歷演算法。
前序遍歷從根節點開始列印，然後分別進入左右子樹，而後序遍歷最後訪問根節點。
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct TreeNode {
int key;
struct TreeNode *left{};
struct TreeNode *right{};
};
void insertNode(TreeNode *&root, const int k) {
if (root == nullptr) {
root = new TreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
void printTreePreorder(TreeNode *n) {
if (n != nullptr) {
cout << n->key << "; ";
printTreePreorder(n->left);
printTreePreorder(n->right);
}
}
void printTreePostorder(TreeNode *n) {
if (n != nullptr) {
printTreePostorder(n->left);
printTreePostorder(n->right);
cout << n->key << "; ";
}
}
int main() {
std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};
TreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printTreePostorder(root);
cout << endl;
printTreePreorder(root);
cout << endl;
return EXIT_SUCCESS;
}
2; 9; 5; 3; 20; 15; 23; 11;
11; 3; 2; 5; 9; 23; 15; 20;
作者： Jinku Hu
