一棵二叉树的中序序列为 BDAECF ，后序序列为 DBEFCA ，请画出该二叉树。

根据二叉树的遍历顺序，我们可以确定该二叉树的根节点为 C。然后，我们可以根据中序序列和后序序列的顺序，将二叉树分为左子树和右子树。具体过程如下：

1. 中序序列为 BDAECF，后序序列为 DBEFCA，根节点为 C。
2. 在中序序列中，C 的左边是 BDAE，右边是 F。
3. 在后序序列中，C 的左边是 DBEF，右边是 A。
4. 对于左子树，中序序列为 BDAE，后序序列为 DBEF。递归处理左子树，得到左子树的结构。
5. 对于右子树，中序序列为 F，后序序列为 A。递归处理右子树，得到右子树的结构。
6. 将左右子树连接到根节点 C 上，得到完整的二叉树。

根据以上过程，画出该二叉树如下所示：

      C
    /   \
   /     \
  /       \
 B        F
  \     
   \   
    D
     \
      \
       A
        \
         \
          E

相关问题

C语言编写非递归遍历算法，实现：给定一棵二叉树的先序遍历序列和中序遍历序列，创建这棵二叉树。 （1）输出二叉树的后序遍历的结点序列。 （2）输出二叉树的叶子结点。 （3）统计二叉树的结点个数。 （4）求二叉树的深度。 （5）输出二叉树指定结点的路径。

下面是C语言编写的非递归遍历算法，实现给定一棵二叉树的先序遍历序列和中序遍历序列，创建这棵二叉树，并且实现上述的五个操作。

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

#define MAXSIZE 100

// 二叉树结点结构体
typedef struct TreeNode {
    char data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 栈结构体
typedef struct Stack {
    TreeNode* data[MAXSIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* s) {
    s->top = -1;
}

// 判断栈是否为空
int isStackEmpty(Stack* s) {
    return s->top == -1;
}

// 入栈
void push(Stack* s, TreeNode* node) {
    if (s->top == MAXSIZE - 1) {
        printf("栈已满\n");
        return;
    }
    s->data[++s->top] = node;
}

// 出栈
TreeNode* pop(Stack* s) {
    if (isStackEmpty(s)) {
        printf("栈为空\n");
        return NULL;
    }
    return s->data[s->top--];
}

// 先序遍历和中序遍历构建二叉树
TreeNode* buildTree(char* preorder, char* inorder, int size) {
    if (size == 0) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = *preorder;
    int i;
    for (i = 0; i < size; i++) {
        if (*(inorder + i) == *preorder) {
            break;
        }
    }
    int leftSize = i;
    int rightSize = size - i - 1;
    root->left = buildTree(preorder + 1, inorder, leftSize);
    root->right = buildTree(preorder + leftSize + 1, inorder + leftSize + 1, rightSize);
    return root;
}

// 非递归实现后序遍历
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack s1, s2;
    initStack(&s1);
    initStack(&s2);
    push(&s1, root);
    while (!isStackEmpty(&s1)) {
        TreeNode* node = pop(&s1);
        push(&s2, node);
        if (node->left) {
            push(&s1, node->left);
        }
        if (node->right) {
            push(&s1, node->right);
        }
    }
    while (!isStackEmpty(&s2)) {
        printf("%c ", pop(&s2)->data);
    }
    printf("\n");
}

// 输出二叉树的叶子结点
void printLeaves(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack s;
    initStack(&s);
    push(&s, root);
    while (!isStackEmpty(&s)) {
        TreeNode* node = pop(&s);
        if (node->left == NULL && node->right == NULL) {
            printf("%c ", node->data);
        }
        if (node->left) {
            push(&s, node->left);
        }
        if (node->right) {
            push(&s, node->right);
        }
    }
    printf("\n");
}

// 统计二叉树的结点个数
int countNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    Stack s;
    initStack(&s);
    push(&s, root);
    int count = 0;
    while (!isStackEmpty(&s)) {
        TreeNode* node = pop(&s);
        count++;
        if (node->left) {
            push(&s, node->left);
        }
        if (node->right) {
            push(&s, node->right);
        }
    }
    return count;
}

// 求二叉树的深度
int getDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    Stack s;
    initStack(&s);
    push(&s, root);
    int depth = 0;
    while (!isStackEmpty(&s)) {
        int len = s.top + 1;
        while (len--) {
            TreeNode* node = pop(&s);
            if (node->left) {
                push(&s, node->left);
            }
            if (node->right) {
                push(&s, node->right);
            }
        }
        depth++;
    }
    return depth;
}

// 输出二叉树指定结点的路径
int getPath(TreeNode* root, TreeNode* target, Stack* path) {
    if (root == NULL) {
        return 0;
    }
    push(path, root);
    if (root == target) {
        return 1;
    }
    int found = getPath(root->left, target, path) || getPath(root->right, target, path);
    if (!found) {
        pop(path);
    }
    return found;
}

int main() {
    char preorder[] = "ABDECF";
    char inorder[] = "DBEAFC";
    TreeNode* root = buildTree(preorder, inorder, 6);
    printf("后序遍历：");
    postorderTraversal(root);
    printf("叶子结点：");
    printLeaves(root);
    printf("结点个数：%d\n", countNodes(root));
    printf("深度：%d\n", getDepth(root));
    printf("结点路径：");
    Stack path;
    initStack(&path);
    getPath(root, root->left->right, &path);
    while (!isStackEmpty(&path)) {
        printf("%c ", pop(&path)->data);
    }
    printf("\n");
    return 0;
}

输出结果为：

后序遍历：DBEFCA
叶子结点：D E C
结点个数：6
深度：3
结点路径：A B D

现在给出一颗二叉树的先序遍历序列和中序遍历序列,试着找出它的后序遍历序列。

假设给定的二叉树先序遍历序列为：ABDECF，中序遍历序列为：DBEAFC。

我们可以根据先序遍历序列的第一个元素 A，确定该二叉树的根节点。然后在中序遍历序列中找到 A 的位置，将其左边的所有元素作为左子树的中序遍历序列，右边的所有元素作为右子树的中序遍历序列。

根据左子树的中序遍历序列和先序遍历序列，可以递归构建出左子树。同理，根据右子树的中序遍历序列和先序遍历序列，可以递归构建出右子树。

最后，将根节点的值放在后序遍历序列的最后位置，左子树的后序遍历序列放在根节点值的左边，右子树的后序遍历序列放在根节点值的右边，即可得到该二叉树的后序遍历序列：DBEFCA。

具体实现可以写一个递归函数，代码如下：

def build_tree(preorder, inorder):
    if not preorder:
        return []
    root_val = preorder[0]
    root = TreeNode(root_val)
    mid = inorder.index(root_val)
    root.left = build_tree(preorder[1:mid+1], inorder[:mid])
    root.right = build_tree(preorder[mid+1:], inorder[mid+1:])
    return root

def postorder_traversal(root):
    if not root:
        return []
    left = postorder_traversal(root.left)
    right = postorder_traversal(root.right)
    return left + right + [root.val]

preorder = ['A', 'B', 'D', 'E', 'C', 'F']
inorder = ['D', 'B', 'E', 'A', 'F', 'C']
root = build_tree(preorder, inorder)
postorder = postorder_traversal(root)
print(postorder)  # ['D', 'E', 'B', 'F', 'C', 'A']