设一棵二叉树的中序遍历序列为： C E I F G B A D H ， 后序遍历序列为： E I C B G A H D F 求： （1）画出这棵二叉树。 （2）写出该二叉树的前序遍历序列。 （3）将这棵二叉树转换成对应的树（或森林）。

(1) 根据中序遍历序列和后序遍历序列可知根节点为F，因为后序遍历的最后一个元素为根节点，F在中序遍历中左侧的为左子树，右侧的为右子树；以此类推，递归构建整棵树，如下图所示：

         F
       /   \
     C      B
    / \     / \
  E    I   G   A
          /   \
         H     D

(2) 该二叉树的前序遍历序列为：F C E I B G A H D

(3) 将该二叉树转换成对应的树（或森林）如下图所示：

       F                B
     /   \            /   \
    C     D          G     A
   / \             /   \     \
  E   I           H     F     D
       \
        B
       / \
      G   A 
         /
        H

相关问题

建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。（假设序列为：ABD##E#H##CF##G##）请使用java回答

以下是使用Java实现二叉树的建立和三种遍历方式的代码：

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;

    TreeNode(char x) {
        val = x;
    }
}

public class BinaryTree {
    int index = 0;

    public TreeNode buildTree(char[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        return build(arr);
    }

    private TreeNode build(char[] arr) {
        if (index >= arr.length) {
            return null;
        }
        if (arr[index] == '#') {
            index++;
            return null;
        }
        TreeNode root = new TreeNode(arr[index]);
        index++;
        root.left = build(arr);
        root.right = build(arr);
        return root;
    }

    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");        preOrder(root.left);
        preOrder(root.right);    }

    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    public static void main(String[] args) {
        char[] arr = {'A', 'B', 'D', '#', '#', 'E', '#', 'H', '#', '#', 'C', 'F', '#', '#', 'G', '#', '#'};
        BinaryTree bt = new BinaryTree();
        TreeNode root = bt.buildTree(arr);
        System.out.print("前序遍历：");
        bt.preOrder(root);
        System.out.println();
        System.out.print("中序遍历：");
        bt.inOrder(root);
        System.out.println();
        System.out.print("后序遍历：");
        bt.postOrder(root);
    }
}

输出结果为：

前序遍历：A B D E H C F G 
中序遍历：D B H E A F C G 
后序遍历：D H E B F G C A 

利用扩展二叉树的中序遍历序列创建一棵二叉树，创建的二叉树可能不唯一，用C语言实现这一代码

在C语言中，我们可以使用递归的方式来实现从扩展二叉树的中序遍历序列重建二叉树。首先，我们需要了解中序遍历的特点，对于二叉搜索树，它的中序遍历结果是升序的节点值。

以下是基本的C语言函数实现：

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

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

// 创建一个新的节点
TreeNode* createNode(int val) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 用于构建二叉树的辅助函数
TreeNode* buildTreeUtil(int start[], int end[], int inOrder[], int i, int j) {
    if (i > j)
        return NULL;

    int index = -1;
    for (int k = i; k <= j; k++) {
        if (inOrder[k] == start[j]) {
            index = k;
            break;
        }
    }

    TreeNode* node = createNode(start[j]);
    node->left = buildTreeUtil(start, end, inOrder, i, index - 1);
    node->right = buildTreeUtil(start, end, inOrder, index + 1, j);

    return node;
}

// 中序遍历序列重构二叉树
TreeNode* buildTree(int inOrder[], int n) {
    // 获取根节点位置
    int start[2] = {0, n};
    return buildTreeUtil(start, start, inOrder, 0, n - 1);
}

// 打印二叉树
void printInorder(TreeNode* root) {
    if (root != NULL) {
        printInorder(root->left);
        printf("%d ", root->val);
        printInorder(root->right);
    }
}

int main() {
    int inOrder[] = {4, 2, 5, 1, 6, 3}; // 示例的中序遍历序列
    int n = sizeof(inOrder) / sizeof(inOrder[0]);

    TreeNode* root = buildTree(inOrder, n);
    printf("Reconstructed binary tree using Inorder traversal:\n");
    printInorder(root);

    return 0;
}

这个程序首先定义了一个二叉树节点结构体和一些辅助函数，然后在`main`函数中调用`buildTree`函数，传入中序遍历序列，得到重建后的二叉树。注意，因为给定的中序遍历序列可能有多种对应的不同二叉树，所以重建的结果并不唯一。