二叉樹的基本操作實驗報告

一、概述

二叉樹是數據結構中的一種，相較於線性結構，具有更為靈活的存儲方式和更為方便的遍歷方式。本實驗的目的是通過實現二叉樹的基本操作，深入理解該數據結構的原理和實現方式。

二、數據結構

二叉樹是一種樹形結構，它的每個節點最多有兩個子節點，左子節點和右子節點。它的結構可以用一組如下的遞歸定義來描述：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

在該結構中，每個節點都包含一個值和兩個指向其左右子樹的指針。如果一個節點沒有子節點，則其指針為空。

三、基本操作

1. 創建二叉樹

創建二叉樹的過程可以通過遞歸的方式實現。首先讀入根節點的值，然後分別遞歸創建左右子樹。具體代碼實現如下：

TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) { // 若讀入的值為-1，則表示該節點為空
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

2. 遍歷二叉樹

遍歷二叉樹包括三種方式：前序遍歷、中序遍歷和後序遍歷。前序遍歷的過程是：先訪問根節點，再訪問左子樹，最後訪問右子樹。中序遍歷和後序遍歷類似，只不過訪問根節點的位置不同。代碼實現如下：

void preorder(TreeNode* root) { // 前序遍歷
    if (!root) {
        return;
    }
    cout <val <left);
    preorder(root->right);
}

void inorder(TreeNode* root) { // 中序遍歷
    if (!root) {
        return;
    }
    inorder(root->left);
    cout <val <right);
}

void postorder(TreeNode* root) { // 後序遍歷
    if (!root) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    cout <val << " ";
}

3. 插入節點

插入節點的過程和創建二叉樹類似，只不過需要找到要插入的節點的位置。具體代碼實現如下：

void insert(TreeNode* root, int val) {
    if (!root) {
        root = new TreeNode(val);
        return;
    }
    if (val val) {
        insert(root->left, val);
    } else {
        insert(root->right, val);
    }
}

4. 查找節點

查找節點的過程也是遞歸的，如果節點存在則返回指向該節點的指針，否則返回空。具體代碼實現如下：

TreeNode* search(TreeNode* root, int val) {
    if (!root) {
        return NULL;
    }
    if (root->val == val) {
        return root;
    }
    if (val val) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }
}

四、實驗結果

通過本次實驗，我進一步深入理解了二叉樹的原理和實現方式，並掌握了二叉樹的四種基本操作：創建、遍歷、插入和查找。在實現的過程中，我發現遞歸是一種非常重要的思維工具，能夠幫助我們更加簡潔和清晰地描述問題。