一颗二叉树先序序列为ABDECF中序序列为DBEACF，求该二叉树的后序序列

根据二叉树的遍历顺序，我们知道先序遍历的第一个元素为根节点，即A为根节点。然后在中序遍历中找到A的位置，A的左侧为左子树的中序遍历序列，右侧为右子树的中序遍历序列。可以得出左子树的先序遍历序列为BDE，右子树的先序遍历序列为CF。

接下来，我们可以通过递归的方式求出左右子树的后序序列，最终得到整个二叉树的后序序列。

左子树的后序序列为：DEB

右子树的后序序列为：FC

因此，该二叉树的后序序列为：DEBFC A

相关问题

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

假设给定的二叉树先序遍历序列为：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']

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