C++怎么把二叉搜索樹轉換累加樹

C++怎么把二叉搜索樹轉換累加樹

在C++中，二叉搜索樹（BST）是一種常見的數據結構，它具有以下性質：對于樹中的每個節點，其左子樹中的所有節點的值都小于該節點的值，而右子樹中的所有節點的值都大于該節點的值。累加樹（Greater Sum Tree）是一種特殊的二叉搜索樹，其中每個節點的值被替換為原始樹中所有大于或等于該節點值的節點值之和。

本文將詳細介紹如何在C++中將二叉搜索樹轉換為累加樹，并提供相應的代碼示例。

1. 理解累加樹

在累加樹中，每個節點的值被替換為原始樹中所有大于或等于該節點值的節點值之和。例如，給定以下二叉搜索樹：

      5
     / \
    2   13

轉換為累加樹后，樹的結構保持不變，但節點的值被更新為：

      18
     / \
    20  13

解釋： - 節點5的值被替換為13 + 5 = 18。 - 節點2的值被替換為18 + 2 = 20。 - 節點13的值保持不變，因為它是樹中最大的節點。

2. 轉換思路

要將二叉搜索樹轉換為累加樹，我們可以利用二叉搜索樹的中序遍歷特性。中序遍歷二叉搜索樹會得到一個升序排列的節點值序列。如果我們反向進行中序遍歷（即右-根-左），我們可以得到一個降序排列的節點值序列。

在反向中序遍歷的過程中，我們可以累加節點的值，并將累加的結果賦值給當前節點。這樣，每個節點的值都會被替換為所有大于或等于它的節點值之和。

3. 實現步驟

以下是實現累加樹轉換的步驟：

1. 定義樹節點結構：首先，我們需要定義一個樹節點的結構，包含節點的值、左子節點和右子節點。

2. 反向中序遍歷：使用遞歸或迭代的方法進行反向中序遍歷（右-根-左）。

3. 累加節點值：在遍歷過程中，維護一個累加器變量，用于存儲當前節點的累加值。

4. 更新節點值：將累加器的值賦值給當前節點，并更新累加器。

4. 代碼實現

以下是C++代碼實現：

#include <iostream>

// 定義樹節點結構
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 反向中序遍歷并累加節點值
void reverseInorder(TreeNode* root, int& sum) {
    if (root == nullptr) {
        return;
    }
    
    // 先遍歷右子樹
    reverseInorder(root->right, sum);
    
    // 累加當前節點的值
    sum += root->val;
    root->val = sum;
    
    // 再遍歷左子樹
    reverseInorder(root->left, sum);
}

// 將二叉搜索樹轉換為累加樹
TreeNode* convertBST(TreeNode* root) {
    int sum = 0;
    reverseInorder(root, sum);
    return root;
}

// 輔助函數：打印樹的中序遍歷結果
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversal(root->left);
    std::cout << root->val << " ";
    inorderTraversal(root->right);
}

int main() {
    // 構建示例二叉搜索樹
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(2);
    root->right = new TreeNode(13);
    
    // 轉換為累加樹
    root = convertBST(root);
    
    // 打印轉換后的樹的中序遍歷結果
    inorderTraversal(root);
    
    return 0;
}

5. 代碼解釋

• TreeNode結構：定義了樹節點的結構，包含節點的值、左子節點和右子節點。
• reverseInorder函數：實現了反向中序遍歷，并在遍歷過程中累加節點值。
• convertBST函數：調用reverseInorder函數，將二叉搜索樹轉換為累加樹。
• inorderTraversal函數：用于打印樹的中序遍歷結果，驗證轉換是否正確。

6. 運行結果

運行上述代碼，輸出結果為：

20 18 13

這表明二叉搜索樹已成功轉換為累加樹。

7. 總結

通過反向中序遍歷二叉搜索樹，并在遍歷過程中累加節點值，我們可以輕松地將二叉搜索樹轉換為累加樹。這種方法的時間復雜度為O(n)，其中n是樹中節點的數量，空間復雜度為O(h)，其中h是樹的高度。

希望本文能幫助你理解如何在C++中將二叉搜索樹轉換為累加樹，并為你在實際編程中提供參考。