用C语言表示二叉树的递归函数

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

// 定义二叉树结点的结构体
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 递归函数：用于创建二叉树
struct TreeNode* createBinaryTree(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 递归函数：用于插入结点到二叉树中
struct TreeNode* insertNode(struct TreeNode* root, int val) {
    if (root == NULL) {
        return createBinaryTree(val);
    }
    if (val < root->val) {
        root->left = insertNode(root->left, val);
    } else {
        root->right = insertNode(root->right, val);
    }
    return root;
}

// 递归函数：用于在二叉树中查找指定值的结点
struct TreeNode* searchNode(struct TreeNode* root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    }
    if (val < root->val) {
        return searchNode(root->left, val);
    } else {
        return searchNode(root->right, val);
    }
}

// 递归函数：用于删除二叉树中指定值的结点
struct TreeNode* deleteNode(struct TreeNode* root, int val) {
    if (root == NULL) {
        return root;
    }
    if (val < root->val) {
        root->left = deleteNode(root->left, val);
    } else if (val > root->val) {
        root->right = deleteNode(root->right, val);
    } else {
        if (root->left == NULL) {
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        struct TreeNode* temp = root->right;
        while (temp->left != NULL) {
            temp = temp->left;
        }
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

// 递归函数：用于销毁二叉树
void destroyBinaryTree(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    destroyBinaryTree(root->left);
    destroyBinaryTree(root->right);
    free(root);
}

// 递归函数：用于中序遍历二叉树
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

int main() {
    struct TreeNode* root = NULL;
    root = insertNode(root, 5);
    insertNode(root, 3);
    insertNode(root, 7);
    insertNode(root, 2);
    insertNode(root, 4);
    insertNode(root, 6);
    insertNode(root, 8);

    printf("中序遍历结果：");
    inorderTraversal(root);
    printf("\n");

    struct TreeNode* searchResult = searchNode(root, 4);
    if (searchResult != NULL) {
        printf("找到了值为4的结点\n");
    } else {
        printf("未找到值为4的结点\n");
    }

    root = deleteNode(root, 5);
    printf("删除结点后的中序遍历结果：");
    inorderTraversal(root);
    printf("\n");

    destroyBinaryTree(root);
    return 0;
}