一棵二叉树的中序序列为 BDAECF ,后序序列为 DBEFCA ,请画出该二叉树。
时间: 2023-10-30 12:21:22 浏览: 139
根据二叉树的遍历顺序,我们可以确定该二叉树的根节点为 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语言编写的非递归遍历算法,实现给定一棵二叉树的先序遍历序列和中序遍历序列,创建这棵二叉树,并且实现上述的五个操作。
```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。
具体实现可以写一个递归函数,代码如下:
```python
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']
```
阅读全文