在 C++ 中實現二叉搜尋樹的中序遍歷

Jinku Hu 2021年10月2日
在 C++ 中實現二叉搜尋樹的中序遍歷

本文將講解如何在 C++ 中實現二叉搜尋樹的中序遍歷。

使用中序遍歷列印二叉搜尋樹的內容

二叉搜尋樹的構造使得每個節點的鍵必須大於其左子樹中的所有鍵,並且小於右子樹中的所有鍵。

為了簡單起見,我們在這裡只考慮不平衡樹,但在實際場景中,二叉搜尋樹的效率來自平衡性質,其中根的每個子樹具有大致相同的高度。

可以使用三種不同的方法遍歷二叉樹:中序、前序和後序。二叉搜尋樹的中序遍歷產生按非遞減順序排序的元素。這個版本通常從最左邊的節點開始,按照先遍歷左子樹的順序,然後是根節點,最後是右子樹。

請注意以下程式碼片段輸出和整數插入樹時的順序。

#include <iostream>
#include <vector>

using std::cout; using std::vector;
using std::endl; using std::string;

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::vector;
using std::endl; using std::string;

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;
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