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

好的，下面我来介绍一下建立二叉树和遍历的方法。

建立二叉树：

以左右孩子链接结构表示的二叉树，可以通过定义一个结构体来表示二叉树中的每个节点，包含该节点的值和左右子树的指针。

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;
}

遍历二叉树：

先序遍历：

先访问根节点，再遍历左子树，最后遍历右子树。

递归实现：

void preOrder(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    printf("%d ", root->val);  //先输出根节点的值
    preOrder(root->left);  //递归遍历左子树
    preOrder(root->right);  //递归遍历右子树
}

非递归实现：

使用栈来实现非递归遍历。先将根节点入栈，然后弹出栈顶元素，输出值，并将右子树和左子树入栈（右子树先入栈，左子树后入栈，保证弹出的时候左子树先出栈）。

void preOrderNonRecursive(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    struct TreeNode* stack[100];  //定义一个栈，用来存储节点
    int top = -1;  //栈顶指针
    stack[++top] = root;  //根节点入栈
    while(top != -1){
        struct 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 inOrder(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    inOrder(root->left);  //递归遍历左子树
    printf("%d ", root->val);  //输出节点的值
    inOrder(root->right);  //递归遍历右子树
}

非递归实现：

使用栈来实现非递归遍历。将所有左子树入栈，然后弹出栈顶元素，输出值，再将右子树入栈。

void inOrderNonRecursive(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    struct TreeNode* stack[100];  //定义一个栈，用来存储节点
    int top = -1;  //栈顶指针
    struct TreeNode* node = root;
    while(top != -1 || node != NULL){
        while(node != NULL){  //将所有左子树入栈
            stack[++top] = node;
            node = node->left;
        }
        node = stack[top--];  //栈顶元素弹出
        printf("%d ", node->val);  //输出节点的值
        node = node->right;  //将右子树入栈
    }
}

后序遍历：

先遍历左子树，再遍历右子树，最后访问根节点。

递归实现：

void postOrder(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    postOrder(root->left);  //递归遍历左子树
    postOrder(root->right);  //递归遍历右子树
    printf("%d ", root->val);  //输出节点的值
}

非递归实现：

使用栈来实现非递归遍历。利用两个栈，先将根节点入栈1，然后从栈1弹出栈顶元素，将其左子树和右子树依次入栈1，然后将该节点入栈2。最后从栈2依次弹出元素，输出值即可。

void postOrderNonRecursive(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    struct TreeNode* stack1[100];  //定义两个栈，用来存储节点
    struct TreeNode* stack2[100];
    int top1 = -1;  //栈1的栈顶指针
    int top2 = -1;  //栈2的栈顶指针
    stack1[++top1] = root;  //根节点入栈1
    while(top1 != -1){  //栈1不为空
        struct TreeNode* node = stack1[top1--];  //栈1的栈顶元素弹出
        stack2[++top2] = node;  //弹出的元素入栈2
        if(node->left != NULL){  //左子树入栈1
            stack1[++top1] = node->left;
        }
        if(node->right != NULL){  //右子树入栈1
            stack1[++top1] = node->right;
        }
    }
    while(top2 != -1){  //栈2不为空
        printf("%d ", stack2[top2--]->val);  //栈2的栈顶元素弹出并输出值
    }
}

分层遍历：

使用队列来实现分层遍历。先将根节点入队列，然后弹出队首元素，输出值，并将其左右子树入队列。重复以上操作，直到队列为空。

void levelOrder(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    struct TreeNode* queue[100];  //定义一个队列，用来存储节点
    int front = 0;  //队首指针
    int rear = 0;  //队尾指针
    queue[rear++] = root;  //根节点入队列
    while(front != rear){  //队列不为空
        struct TreeNode* node = queue[front++];  //队首元素弹出
        printf("%d ", node->val);  //输出节点的值
        if(node->left != NULL){  //左子树入队列
            queue[rear++] = node->left;
        }
        if(node->right != NULL){  //右子树入队列
            queue[rear++] = node->right;
        }
    }
}

统计树的高度：

树的高度等于左右子树中高度较大的值加1。因此可以通过递归方式来求解。

int getHeight(struct TreeNode* root){
    if(root == NULL){
        return 0;
    }
    int left = getHeight(root->left);  //递归求解左子树的高度
    int right = getHeight(root->right);  //递归求解右子树的高度
    return (left > right ? left : right) + 1;  //返回左右子树中高度较大的值加1
}

二叉排序树中进行结点的插入和删除操作：

二叉排序树是一种特殊的二叉树，满足每个节点的左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。因此可以通过比较节点的值和根节点的值来判断该节点应该插入左子树还是右子树。

插入操作：

struct TreeNode* insert(struct TreeNode* root, int val){
    if(root == NULL){  //如果根节点为空，直接创建新节点
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->val = val;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    if(val < root->val){  //如果插入的值小于根节点的值，插入左子树
        root->left = insert(root->left, val);
    }
    else if(val > root->val){  //如果插入的值大于根节点的值，插入右子树
        root->right = insert(root->right, val);
    }
    return root;
}

删除操作：

删除操作分为三种情况：

1. 要删除的节点没有子节点，直接删除。

2. 要删除的节点只有一个子节点，将子节点替换为要删除的节点。

3. 要删除的节点有两个子节点，将要删除的节点替换为其右子树中最小的节点。

struct TreeNode* delete(struct TreeNode* root, int val){
    if(root == NULL){  //如果根节点为空，直接返回NULL
        return NULL;
    }
    if(val < root->val){  //如果要删除的值小于根节点的值，递归删除左子树
        root->left = delete(root->left, val);
    }
    else if(val > root->val){  //如果要删除的值大于根节点的值，递归删除右子树
        root->right = delete(root->right, val);
    }
    else{  //找到要删除的节点
        if(root->left == NULL){  //如果要删除的节点没有左子节点，直接将其右子节点替换为要删除的节点
            struct TreeNode* tmp = root->right;
            free(root);
            return tmp;
        }
        else if(root->right == NULL){  //如果要删除的节点没有右子节点，直接将其左子节点替换为要删除的节点
            struct TreeNode* tmp = root->left;
            free(root);
            return tmp;
        }
        else{  //如果要删除的节点有两个子节点，将其替换为其右子树中最小的节点
            struct TreeNode* tmp = root->right;
            while(tmp->left != NULL){  //找到右子树中最小的节点
                tmp = tmp->left;
            }
            root->val = tmp->val;  //将找到的节点的值赋给要删除的节点
            root->right = delete(root->right, tmp->val);  //递归删除右子树中找到的节点
        }
    }
    return root;
}