中序和后续能建立二叉树吗

是的，中序遍历序列和后序遍历序列也可以唯一地确定一棵二叉树。具体构建方法如下：

1. 后序遍历序列的最后一个结点为根节点；
2. 在中序遍历序列中找到根节点，可以将中序遍历序列分为左子树和右子树两个部分；
3. 根据左子树和右子树的长度，可以将后序遍历序列分为左子树和右子树两个部分；
4. 递归处理左子树和右子树，即可构建整棵二叉树。

需要注意的是，如果中序遍历序列和后序遍历序列不合法，即无法构建成二叉树，那么上述方法也无法构建正确的二叉树。此外，如果一棵二叉树中存在相同的结点值，那么就无法唯一地确定这棵二叉树。

相关问题

二叉树C语言，要求输入为结点个数，结点的值，输出先序遍历建立的二叉树，中序遍历建立的二叉树（递归方式）。中序遍历建立的二叉树（非递归方式），后续遍历建立的二叉树

好的，以下是二叉树C语言代码：

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

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

// 先序遍历建立二叉树
TreeNode* createTreeByPreorder(int* preorder, int size, int* index) {
    if (*index >= size || preorder[*index] == -1) { // 判断是否到达数组末尾或者该节点为空节点
        (*index)++; // 指针下移
        return NULL; // 返回NULL
    }
    // 创建节点
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = preorder[*index];
    node->left = NULL;
    node->right = NULL;
    (*index)++; // 指针下移
    // 递归创建左子树和右子树
    node->left = createTreeByPreorder(preorder, size, index);
    node->right = createTreeByPreorder(preorder, size, index);
    return node;
}

// 中序遍历建立二叉树（递归方式）
TreeNode* createTreeByInorderRecursive(int* inorder, int inStart, int inEnd, int* preorder, int* preIndex) {
    if (inStart > inEnd) { // 判断是否到达叶子节点
        return NULL;
    }
    // 创建节点
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = preorder[(*preIndex)++];
    node->left = NULL;
    node->right = NULL;
    int inIndex;
    // 找到该节点在中序遍历中的位置
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == node->val) {
            inIndex = i;
            break;
        }
    }
    // 递归创建左子树和右子树
    node->left = createTreeByInorderRecursive(inorder, inStart, inIndex - 1, preorder, preIndex);
    node->right = createTreeByInorderRecursive(inorder, inIndex + 1, inEnd, preorder, preIndex);
    return node;
}

// 中序遍历建立二叉树（非递归方式）
TreeNode* createTreeByInorderIterative(int* inorder, int size, int* preorder) {
    TreeNode* stack[size]; // 栈
    int top = -1; // 栈顶指针
    int preIndex = 0; // 先序遍历数组指针
    // 创建根节点
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = preorder[preIndex++];
    root->left = NULL;
    root->right = NULL;
    TreeNode* node = root;
    // 遍历先序遍历数组
    while (preIndex < size) {
        // 左子树
        if (node->val != inorder[top + 1]) {
            // 创建节点并入栈
            node->left = (TreeNode*)malloc(sizeof(TreeNode));
            node->left->val = preorder[preIndex++];
            node->left->left = NULL;
            node->left->right = NULL;
            stack[++top] = node;
            node = node->left;
        }
        // 右子树
        else {
            top++;
            // 创建节点并出栈
            while (top <= size - 2 && inorder[top] == stack[top + 1]->val) {
                top++;
            }
            node = stack[top];
            node->right = (TreeNode*)malloc(sizeof(TreeNode));
            node->right->val = preorder[preIndex++];
            node->right->left = NULL;
            node->right->right = NULL;
            node = node->right;
        }
    }
    return root;
}

// 后序遍历建立二叉树
TreeNode* createTreeByPostorder(int* postorder, int size, int* index) {
    if (*index < 0 || postorder[*index] == -1) { // 判断是否到达数组末尾或者该节点为空节点
        (*index)--; // 指针下移
        return NULL; // 返回NULL
    }
    // 创建节点
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = postorder[*index];
    node->left = NULL;
    node->right = NULL;
    (*index)--; // 指针下移
    // 递归创建右子树和左子树（注意顺序）
    node->right = createTreeByPostorder(postorder, size, index);
    node->left = createTreeByPostorder(postorder, size, index);
    return node;
}

// 先序遍历打印二叉树
void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 中序遍历打印二叉树
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

// 后序遍历打印二叉树
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->val);
}

int main() {
    int n; // 结点个数
    printf("请输入结点个数：");
    scanf("%d", &n);
    int preorder[n]; // 先序遍历数组
    int inorder[n]; // 中序遍历数组
    int postorder[n]; // 后序遍历数组
    printf("请输入先序遍历数组：");
    for (int i = 0; i < n; i++) {
        scanf("%d", &preorder[i]);
    }
    printf("请输入中序遍历数组：");
    for (int i = 0; i < n; i++) {
        scanf("%d", &inorder[i]);
    }
    printf("请输入后序遍历数组：");
    for (int i = 0; i < n; i++) {
        scanf("%d", &postorder[i]);
    }
    int index = 0; // 先序遍历数组指针
    printf("先序遍历建立的二叉树：");
    TreeNode* root1 = createTreeByPreorder(preorder, n, &index); // 先序遍历建立二叉树
    preorderTraversal(root1); // 先序遍历打印二叉树
    printf("\n");
    int preIndex = 0; // 先序遍历数组指针
    printf("中序遍历建立的二叉树（递归方式）：");
    TreeNode* root2 = createTreeByInorderRecursive(inorder, 0, n - 1, preorder, &preIndex); // 中序遍历建立二叉树（递归方式）
    inorderTraversal(root2); // 中序遍历打印二叉树
    printf("\n");
    printf("中序遍历建立的二叉树（非递归方式）：");
    TreeNode* root3 = createTreeByInorderIterative(inorder, n, preorder); // 中序遍历建立二叉树（非递归方式）
    inorderTraversal(root3); // 中序遍历打印二叉树
    printf("\n");
    int index2 = n - 1; // 后序遍历数组指针
    printf("后序遍历建立的二叉树：");
    TreeNode* root4 = createTreeByPostorder(postorder, n, &index2); // 后序遍历建立二叉树
    postorderTraversal(root4); // 后序遍历打印二叉树
    printf("\n");
    return 0;
}

其中，`createTreeByPreorder`函数用于先序遍历建立二叉树；`createTreeByInorderRecursive`函数用于中序遍历建立二叉树（递归方式）；`createTreeByInorderIterative`函数用于中序遍历建立二叉树（非递归方式）；`createTreeByPostorder`函数用于后序遍历建立二叉树。`preorderTraversal`函数用于先序遍历打印二叉树；`inorderTraversal`函数用于中序遍历打印二叉树；`postorderTraversal`函数用于后序遍历打印二叉树。

二叉树C语言，要求输入为结点个数，以及各节点的值，输出先序遍历建立的二叉树，中序遍历建立的二叉树（递归方式）。中序遍历建立的二叉树（非递归方式），后续遍历建立的二叉树，

以下是一份C语言的二叉树代码，满足您的要求：

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

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

// 先序遍历建立二叉树
TreeNode* createTreeByPreorder() {
    printf("请输入节点个数：");
    int n;
    scanf("%d", &n);
    if (n == 0) {  // 空二叉树
        return NULL;
    }
    printf("请输入节点的值：");
    int val;
    scanf("%d", &val);
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = val;
    root->left = createTreeByPreorder();
    root->right = createTreeByPreorder();
    return root;
}

// 中序遍历建立二叉树（递归）
TreeNode* createTreeByInorder(int* inorder, int inorderSize) {
    if (inorderSize == 0) {  // 空二叉树
        return NULL;
    }
    int rootIndex = inorderSize / 2;  // 中间节点为根节点
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = inorder[rootIndex];
    root->left = createTreeByInorder(inorder, rootIndex);
    root->right = createTreeByInorder(inorder + rootIndex + 1, inorderSize - rootIndex - 1);
    return root;
}

// 中序遍历建立二叉树（非递归）
TreeNode* createTreeByInorderNonrecursion(int* inorder, int inorderSize) {
    if (inorderSize == 0) {  // 空二叉树
        return NULL;
    }
    int rootIndex = inorderSize / 2;  // 中间节点为根节点
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = inorder[rootIndex];
    TreeNode* stack[inorderSize];
    int top = -1;
    stack[++top] = root;
    int i = 0;
    TreeNode* cur = root;
    while (i < inorderSize) {
        if (cur->left == NULL && i < rootIndex) {  // 左子树未建立
            cur->left = (TreeNode*)malloc(sizeof(TreeNode));
            cur->left->val = inorder[--rootIndex];
            cur = cur->left;
            stack[++top] = cur;
        } else if (cur->right == NULL && i > rootIndex) {  // 右子树未建立
            cur->right = (TreeNode*)malloc(sizeof(TreeNode));
            cur->right->val = inorder[++rootIndex];
            cur = cur->right;
            stack[++top] = cur;
        } else {  // 左右子树都已建立，弹出栈顶
            cur = stack[--top];
            i++;
        }
    }
    return root;
}

// 后序遍历建立二叉树
TreeNode* createTreeByPostorder() {
    printf("请输入节点个数：");
    int n;
    scanf("%d", &n);
    if (n == 0) {  // 空二叉树
        return NULL;
    }
    printf("请输入节点的值：");
    int val;
    scanf("%d", &val);
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->left = createTreeByPostorder();
    root->right = createTreeByPostorder();
    root->val = val;
    return root;
}

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

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

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

int main() {
    // 先序遍历建立二叉树
    printf("先序遍历建立二叉树：\n");
    TreeNode* root1 = createTreeByPreorder();
    printf("先序遍历结果：");
    preorderTraversal(root1);
    printf("\n");

    // 中序遍历建立二叉树（递归）
    printf("中序遍历建立二叉树（递归）：\n");
    int inorder1[] = {1, 2, 3, 4, 5};
    TreeNode* root2 = createTreeByInorder(inorder1, 5);
    printf("中序遍历结果：");
    inorderTraversal(root2);
    printf("\n");

    // 中序遍历建立二叉树（非递归）
    printf("中序遍历建立二叉树（非递归）：\n");
    int inorder2[] = {1, 2, 3, 4, 5};
    TreeNode* root3 = createTreeByInorderNonrecursion(inorder2, 5);
    printf("中序遍历结果：");
    inorderTraversal(root3);
    printf("\n");

    // 后序遍历建立二叉树
    printf("后序遍历建立二叉树：\n");
    TreeNode* root4 = createTreeByPostorder();
    printf("后序遍历结果：");
    postorderTraversal(root4);
    printf("\n");

    return 0;
}

其中，输入先序遍历和后序遍历建立二叉树的代码部分，采用了递归方式。