本文章沒有找到對應的語言版本

發現新版本

網站好像有新內容，是否更新？

實現哈夫曼樹的編碼和解碼

a. 問題分析

目標：

實現排序二叉樹的構建和節點刪除。

問題：
  1. 構建排序二叉樹的過程是否正確？
  2. 是否正確實現了節點的插入和刪除？
  3. 是否能夠處理重複值的節點？
  4. 是否能夠正確處理樹的平衡性？

b. 算法設計

1. 構建排序二叉樹：
  • 根據輸入的數據，依次插入節點到排序二叉樹中。

輸入： 一組數據值。 輸出： 排序二叉樹的根節點 root。

TreeNode* buildBST(vector<int>& values) {
    TreeNode* root = nullptr;
    for (int val : values) {
        root = insertNode(root, val);
    }
    return root;
}
2. 插入節點：
  • 遞歸地找到合適的位置插入新節點。

輸入： 當前子樹的根節點 node，要插入的值 val。 輸出： 插入後的子樹根節點。

TreeNode* insertNode(TreeNode* node, int val) {
    if (node == nullptr) {
        return new TreeNode(val);
    }
    if (val < node->val) {
        node->left = insertNode(node->left, val);
    } else if (val > node->val) {
        node->right = insertNode(node->right, val);
    }
    return node;
}
3. 刪除節點：
  • 找到要刪除的節點，並根據其子節點的情況進行刪除操作。

輸入： 當前子樹的根節點 node，要刪除的值 val。 輸出： 刪除後的子樹根節點。

TreeNode* deleteNode(TreeNode* node, int val) {
    if (node == nullptr) {
        return nullptr;
    }
    if (val < node->val) {
        node->left = deleteNode(node->left, val);
    } else if (val > node->val) {
        node->right = deleteNode(node->right, val);
    } else {
        if (node->left == nullptr) {
            TreeNode* temp = node->right;
            delete node;
            return temp;
        } else if (node->right == nullptr) {
            TreeNode* temp = node->left;
            delete node;
            return temp;
        }
        TreeNode* temp = findMin(node->right);
        node->val = temp->val;
        node->right = deleteNode(node->right, temp->val);
    }
    return node;
}
4. 查找最小節點：
  • 在右子樹中找到最小的節點（用於刪除節點時替換）。

輸入： 當前子樹的根節點 node。 輸出： 最小節點的指針。

TreeNode* findMin(TreeNode* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

c. 數據結構設計

  • TreeNode 結構體：
    • 存儲節點值 val，以及左右子節點指針 left 和 right。
  • std::vector：
    • 用於存儲輸入的數據值。
  • 遞歸函數：
    • 用於實現節點的插入和刪除操作。

d. 調試過程

  1. 構建排序二叉樹：

    • 檢查節點是否按照排序二叉樹的規則正確插入。
    • 檢查重複值的處理是否正確。

  2. 刪除節點：

    • 測試刪除葉子節點、只有一個子節點的節點和兩個子節點的節點。
    • 檢查刪除後樹的結構是否仍然符合排序二叉樹的規則。

  3. 平衡性檢查：

    • 雖然排序二叉樹不保證平衡，但檢查極端情況下（如完全升序或降序輸入）樹的深度是否過大。

e. 輸出結果

運行程序並使用測試用例（例如輸入 [5,3,6,2,4,7] 並刪除節點 3）檢查輸出結果。確保輸出包括構建後的樹結構和刪除節點後的樹結構，並驗證其正確性。

Original BST:
    5
   / \
  3   6
 / \   \
2   4   7

After deleting node 3:
    5
   / \
  4   6
 /     \
2       7

f. 源代碼

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

// 插入節點到排序二叉樹
TreeNode* insertNode(TreeNode* node, int val) {
    if (node == nullptr) {
        return new TreeNode(val);
    }
    if (val < node->val) {
        node->left = insertNode(node->left, val);
    } else if (val > node->val) {
        node->right = insertNode(node->right, val);
    }
    return node;
}

// 構建排序二叉樹
TreeNode* buildBST(vector<int>& values) {
    TreeNode* root = nullptr;
    for (int val : values) {
        root = insertNode(root, val);
    }
    return root;
}

// 查找最小節點
TreeNode* findMin(TreeNode* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

// 刪除節點
TreeNode* deleteNode(TreeNode* node, int val) {
    if (node == nullptr) {
        return nullptr;
    }
    if (val < node->val) {
        node->left = deleteNode(node->left, val);
    } else if (val > node->val) {
        node->right = deleteNode(node->right, val);
    } else {
        if (node->left == nullptr) {
            TreeNode* temp = node->right;
            delete node;
            return temp;
        } else if (node->right == nullptr) {
            TreeNode* temp = node->left;
            delete node;
            return temp;
        }
        TreeNode* temp = findMin(node->right);
        node->val = temp->val;
        node->right = deleteNode(node->right, temp->val);
    }
    return node;
}

// 打印二叉樹（層序遍歷）
void printBST(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left != nullptr) {
            q.push(node->left);
        }
        if (node->right != nullptr) {
            q.push(node->right);
        }
    }
    cout << endl;
}

int main() {
    vector<int> values = {5, 3, 6, 2, 4, 7};
    TreeNode* root = buildBST(values);

    cout << "Original BST: ";
    printBST(root);

    root = deleteNode(root, 3);
    cout << "After deleting node 3: ";
    printBST(root);

    return 0;
}

總結

通過測試，確保程序正確實現了排序二叉樹的構建和節點刪除功能。特別注意刪除節點時樹的結構是否仍然符合排序二叉樹的規則，並檢查重複值的處理是否正確。雖然排序二叉樹不保證平衡，但在實際應用中可以考慮進一步優化（如 AVL 樹或紅黑樹）以保持平衡性。

問題分析

本實驗的目標是實現基於排序二元樹的節點插入、中序遍歷、刪除整個樹以及刪除單獨某個節點的功能。具體要求包括使用struct實現節點，實現插入節點和刪除節點的功能。

b 演算法設計

插入節點演算法設計

插入節點的演算法是一個遞迴演算法。根據節點值與當前節點值的比較，選擇插入到左子樹或右子樹。如果當前子樹為空，創建一個新節點並返回；否則，遞迴調用插入函數。

TreeNode* insert(TreeNode* root, int val) {
    if (root == nullptr) {
        return new TreeNode(val);
    }

    if (val <= root->data) {
        root->left = insert(root->left, val);
    } else if (val > root->data) {
        root->right = insert(root->right, val);
    }

    return root;
}

構建排序二元樹演算法設計

構建排序二元樹的演算法使用了插入節點演算法。遍歷輸入序列，對每個元素調用插入節點函數，不斷更新根節點，最終得到一個排序二元樹。

TreeNode* buildTree(int input[], int size) {
    TreeNode* root = nullptr;

    for (int i = 0; i < size; ++i) {
        root = insert(root, input[i]);
    }

    return root;
}

中序遍歷演算法設計

中序遍歷演算法用於輸出排序二元樹的節點值，以驗證樹的構建是否正確。

void inorderTraversal(TreeNode* node) {
    if (node != nullptr) {
        inorderTraversal(node->left);
        cout << node->data << " ";
        inorderTraversal(node->right);
    }
}

刪除整個樹演算法設計

刪除整個樹的演算法是一個遞迴演算法。遞迴調用刪除函數，刪除左子樹和右子樹，最後刪除當前節點。

void deleteTree(TreeNode* node) {
    if (node != nullptr) {
        deleteTree(node->left);
        deleteTree(node->right);
        delete node;
    }
}

刪除單獨某個節點演算法設計

刪除單獨某個節點的演算法是一個遞迴演算法。根據節點值與待刪除值的比較，選擇在左子樹或右子樹中進行刪除。如果找到匹配的節點，分三種情況處理：節點沒有子節點、節點有一個子節點、節點有兩個子節點。

TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == nullptr) {
        return root;
    }

    // 找到匹配節點
    if (val < root->data) {
        root->left = deleteNode(root->left, val);
    } else if (val > root->data) {
        root->right = deleteNode(root->right, val);
    } else {
        // 節點有一個或無子節點
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }

        // 節點有兩個子節點，找到右子樹的最小節點
        TreeNode* minRight = root->right;
        while (minRight->left != nullptr) {
            minRight = minRight->left;
        }

        // 複製最小節點的值到當前節點
        root->data = minRight->data;

        // 刪除右子樹中的最小節點
        root->right = deleteNode(root->right, minRight->data);
    }

    return root;
}

// 刪除單獨某個節點的介面函數
TreeNode* deleteSingleNode(TreeNode* root, int val) {
    TreeNode* nodeToDelete = findNode(root, val);
    if (nodeToDelete != nullptr) {
        root = deleteNode(root, val);
    }
    return root;
}

c 資料結構設計

節點結構
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

d 調試過程

在調試過程中，首先確保 deleteSingleNode 函數能夠正確執行。通過刪除單獨某個節點後，使用中序遍歷驗證排序二叉樹的節點值，以確保刪除操作的正確性。最後，通過輸出驗證整個實現的正確性。

e 輸出結果

針對輸入序列 7, 5, 9, 2, 5, 2, 6, 3, 7, 0，實驗的輸出結果如下：

排序二元樹: 0 2 2 3 5 5 6 7 7 9 
刪除節點 3 後的排序二元樹: 0 2 2 5 5 6 7 7 9 
刪除單獨節點 5 後的排序二元樹: 0 2 2 6 7 7 9

這個輸出結果表明刪除單獨某個節點的功能已經添加，並且在刪除節點 5 後，中序遍歷輸出排序二元樹的節點值，驗證刪除操作的正確性。

f 原始碼

#include <iostream>

using namespace std;

// 定義二元樹節點
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// 插入節點到排序二元樹
TreeNode* insert(TreeNode* root, int val) {
    if (root == nullptr) {
        return new TreeNode(val);
    }

    if (val <= root->data) {
        root->left = insert(root->left, val);
    } else if (val > root->data) {
        root->right = insert(root->right, val);
    }

    return root;
}

// 中序遍歷
void inorderTraversal(TreeNode* node) {
    if (node != nullptr) {
        inorderTraversal(node->left);
        cout << node->data << " ";
        inorderTraversal(node->right);
    }
}

// 刪除整個樹
void deleteTree(TreeNode* node) {
    if (node != nullptr) {
        deleteTree(node->left);
        deleteTree(node->right);
        delete node;
    }
}

// 查找節點值為val的節點
TreeNode* findNode(TreeNode* root, int val) {
    if (root == nullptr || root->data == val) {
        return root;
    }

    if (val < root->data) {
        return findNode(root->left, val);
    } else {
        return findNode(root->right, val);
    }
}

// 刪除單獨某個節點
TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == nullptr) {
        return root;
    }

    // 找到匹配節點
    if (val < root->data) {
        root->left = deleteNode(root->left, val);
    } else if (val > root->data) {
        root->right = deleteNode(root->right, val);
    } else {
        // 節點有一個或無子節點
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }

        // 節點有兩個子節點，找到右子樹的最小節點
        TreeNode* minRight = root->right;
        while (minRight->left != nullptr) {
            minRight = minRight->left;
        }

        // 複製最小節點的值到當前節點
        root->data = minRight->data;

        // 刪除右子樹中的最小節點
        root->right = deleteNode(root->right, minRight->data);
    }

    return root;
}

// 刪除單獨某個節點的介面函數
TreeNode* deleteSingleNode(TreeNode* root, int val) {
    TreeNode* nodeToDelete = findNode(root, val);
    if (nodeToDelete != nullptr) {
        root = deleteNode(root, val);
    }
    return root;
}

int main() {
    int input[] = {7, 5, 9, 2, 5, 2, 6, 3, 7, 0};
    TreeNode* root = nullptr;

    // 構建排序二元樹
    for (int i = 0; i < 10; ++i) {
        root = insert(root, input[i]);
    }

    // 顯示排序二元樹
    cout << "排序二元樹: ";
    inorderTraversal(root);
    cout << endl;

    // 刪除節點 3 後的排序二元樹
    int nodeToDelete = 3;
    root = deleteNode(root, nodeToDelete);
    cout << "刪除節點 " << nodeToDelete << " 後的排序二元樹: ";
    inorderTraversal(root);
    cout << endl;

    // 刪除單獨節點 5 後的排序二元樹
    int singleNodeToDelete = 5;
    root = deleteSingleNode(root, singleNodeToDelete);
    cout << "刪除單獨節點 " << singleNodeToDelete << " 後的排序二元樹: ";
    inorderTraversal(root);
    cout << endl;

    // 刪除整個樹
    deleteTree(root);

    return 0;
}

本文作者：孤筝

本文標題：資料結構實機實驗報告5——哈夫曼樹的編碼和解碼，排序二元樹的建構和節點刪除

本文發佈時間：2023-12-12 14:54:04

本文更新時間：2023-12-12 14:54:04

本文版權： 本部落格所有文章除特別聲明外，均採用 BY-NC-SA 授權協議。轉載請註明出處！

留言 0 閲讀量

何時一樽酒，重與細論文。

waline