二叉树基本操作重要算法的实现代码c语言和算法的时间复杂度和空间复杂度

二叉树基本操作包括：创建二叉树、遍历二叉树、查找节点、插入节点、删除节点等。下面是这些操作的实现代码和时间/空间复杂度分析。

1. 创建二叉树

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* createTree() {
    int val;
    scanf("%d", &val);
    if (val == -1) { // -1表示该节点为空
        return NULL;
    }
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = val;
    root->left = createTree();
    root->right = createTree();
    return root;
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(n)，即为递归栈的深度，最坏情况下为树的高度，即n。

2. 遍历二叉树

（1）前序遍历

void preorder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    preorder(root->left);
    preorder(root->right);
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。

（2）中序遍历

void inorder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->val);
    inorder(root->right);
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。

（3）后序遍历

void postorder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->val);
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。

3. 查找节点

struct TreeNode* find(struct TreeNode *root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    }
    struct TreeNode *left = find(root->left, val);
    struct TreeNode *right = find(root->right, val);
    return left == NULL ? right : left;
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。

4. 插入节点

void insert(struct TreeNode *root, int val) {
    if (root == NULL) {
        return;
    }
    if (root->left == NULL) {
        root->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
        root->left->val = val;
        root->left->left = NULL;
        root->left->right = NULL;
        return;
    }
    if (root->right == NULL) {
        root->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
        root->right->val = val;
        root->right->left = NULL;
        root->right->right = NULL;
        return;
    }
    insert(root->left, val);
    insert(root->right, val);
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。

5. 删除节点

struct TreeNode* delete(struct TreeNode *root, int val) {
    if (root == NULL) {
        return NULL;
    }
    if (root->val == val) {
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        if (root->left == NULL) {
            struct TreeNode *right = root->right;
            free(root);
            return right;
        }
        if (root->right == NULL) {
            struct TreeNode *left = root->left;
            free(root);
            return left;
        }
        struct TreeNode *min = root->right;
        while (min->left != NULL) {
            min = min->left;
        }
        root->val = min->val;
        root->right = delete(root->right, min->val);
    } else if (root->val > val) {
        root->left = delete(root->left, val);
    } else {
        root->right = delete(root->right, val);
    }
    return root;
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。