c语言建立以左右孩子链接结构表示的二叉树,实现二叉树的先序、中序、后序的递归和非递归方式遍历,分层遍历、统计树的高度。 选做内容: 在二叉排序树中进行结点的插入和删除操作。

以下是基于左右孩子链接结构的二叉树的C语言代码实现：

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

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

// 创建二叉树
TreeNode* createTree() {
    int val;
    scanf("%d", &val);
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = val;
    root->left = createTree();
    root->right = createTree();
    return root;
}

// 先序递归遍历
void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    preOrder(root->left);
    preOrder(root->right);
}

// 中序递归遍历
void inOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%d ", root->val);
    inOrder(root->right);
}

// 后序递归遍历
void postOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->val);
}

// 先序非递归遍历
void preOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[100];
    int top = -1;
    stack[++top] = root;
    while (top >= 0) {
        TreeNode* node = stack[top--];
        printf("%d ", node->val);
        if (node->right != NULL) {
            stack[++top] = node->right;
        }
        if (node->left != NULL) {
            stack[++top] = node->left;
        }
    }
}

// 中序非递归遍历
void inOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[100];
    int top = -1;
    TreeNode* p = root;
    while (p != NULL || top >= 0) {
        if (p != NULL) {
            stack[++top] = p;
            p = p->left;
        } else {
            p = stack[top--];
            printf("%d ", p->val);
            p = p->right;
        }
    }
}

// 后序非递归遍历
void postOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[100];
    int top1 = -1;
    int top2 = -1;
    stack[++top1] = root;
    while (top1 >= 0) {
        TreeNode* node = stack[top1--];
        stack[++top2] = node;
        if (node->left != NULL) {
            stack[++top1] = node->left;
        }
        if (node->right != NULL) {
            stack[++top1] = node->right;
        }
    }
    while (top2 >= 0) {
        printf("%d ", stack[top2--]->val);
    }
}

// 分层遍历
void levelOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* queue[100];
    int front = 0;
    int rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode* node = queue[front++];
        printf("%d ", node->val);
        if (node->left != NULL) {
            queue[rear++] = node->left;
        }
        if (node->right != NULL) {
            queue[rear++] = node->right;
        }
    }
}

// 统计树的高度
int getHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 二叉排序树中插入节点
TreeNode* insertNode(TreeNode* root, int val) {
    if (root == NULL) {
        TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
        node->val = val;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    if (val < root->val) {
        root->left = insertNode(root->left, val);
    } else if (val > root->val) {
        root->right = insertNode(root->right, val);
    }
    return root;
}

// 二叉排序树中删除节点
TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == NULL) {
        return NULL;
    }
    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) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        TreeNode* minNode = root->right;
        while (minNode->left != NULL) {
            minNode = minNode->left;
        }
        root->val = minNode->val;
        root->right = deleteNode(root->right, minNode->val);
    }
    return root;
}

int main() {
    TreeNode* root = createTree();
    printf("先序递归遍历：");
    preOrder(root);
    printf("\n中序递归遍历：");
    inOrder(root);
    printf("\n后序递归遍历：");
    postOrder(root);
    printf("\n先序非递归遍历：");
    preOrderNonRecursive(root);
    printf("\n中序非递归遍历：");
    inOrderNonRecursive(root);
    printf("\n后序非递归遍历：");
    postOrderNonRecursive(root);
    printf("\n分层遍历：");
    levelOrder(root);
    printf("\n树的高度：%d\n", getHeight(root));
    root = insertNode(root, 10);
    root = insertNode(root, 5);
    root = insertNode(root, 15);
    printf("插入节点后的中序遍历：");
    inOrder(root);
    root = deleteNode(root, 10);
    printf("\n删除节点后的中序遍历：");
    inOrder(root);
    return 0;
}