二叉树前序和中序知道
时间: 2023-11-10 17:07:02 浏览: 48
已知前序和中序遍历序列,可以确定唯一的二叉树。推导流程如下:
1. 首先确定根节点(前序的第一个元素,也是中序的分割点),根据根节点将中序序列分为左子树和右子树。
2. 根据左子树的长度,将前序序列也分为左子树和右子树。
3. 递归地对左子树和右子树进行步骤1和步骤2的操作,直到序列长度为1或为空。
4. 重复以上步骤,直到构建完整的二叉树。
例如,给定前序序列为 [E, H, B, C, F, A, D, G],中序序列为 [B, H, F, C, A, E, D, G]。根据前序序列的第一个元素 E,可以将中序序列分为 [B, H, F, C, A] 和 [D, G],也将前序序列分为 [H, B, C, F, A] 和 [D, G]。对左子树的递归操作,将前序序列 [H, B, C, F, A] 和中序序列 [B, H, F, C, A] 作为输入,可以得到左子树。对右子树的递归操作,将前序序列 [D, G] 和中序序列 [D, G] 作为输入,可以得到右子树。最终,将左子树和右子树连接到根节点 E 上,即可得到完整的二叉树。
相关问题
二叉树前序后序中序排列区别
二叉树的前序、中序、后序遍历是指以根节点为基准,按照某一顺序遍历二叉树并输出节点值的过程。它们的区别在于访问根节点的时机和顺序不同。
- 前序遍历:先访问根节点,然后按照前序遍历的顺序递归访问左子树和右子树,即 根-左-右 的顺序。
- 中序遍历:先按照中序遍历的顺序递归访问左子树,然后访问根节点,最后按照中序遍历的顺序递归访问右子树,即 左-根-右 的顺序。
- 后序遍历:先按照后序遍历的顺序递归访问左子树和右子树,然后访问根节点,即 左-右-根 的顺序。
以一个二叉树为例:
```
A
/ \
B C
/ \ / \
D E F G
```
它的前序遍历、中序遍历和后序遍历的结果分别为:
- 前序遍历:A B D E C F G
- 中序遍历:D B E A F C G
- 后序遍历:D 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;
//前序遍历
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() {
// 构建一棵二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
TreeNode* left = (TreeNode*)malloc(sizeof(TreeNode));
left->val = 2;
TreeNode* right = (TreeNode*)malloc(sizeof(TreeNode));
right->val = 3;
TreeNode* left_left = (TreeNode*)malloc(sizeof(TreeNode));
left_left->val = 4;
TreeNode* left_right = (TreeNode*)malloc(sizeof(TreeNode));
left_right->val = 5;
TreeNode* right_left = (TreeNode*)malloc(sizeof(TreeNode));
right_left->val = 6;
TreeNode* right_right = (TreeNode*)malloc(sizeof(TreeNode));
right_right->val = 7;
root->left = left;
root->right = right;
left->left = left_left;
left->right = left_right;
right->left = right_left;
right->right = right_right;
printf("前序遍历结果: ");
preorderTraversal(root);
printf("\n中序遍历结果: ");
inorderTraversal(root);
printf("\n后序遍历结果: ");
postorderTraversal(root);
printf("\n");
return 0;
}
```
以上代码可以测试输出一棵二叉树的前序、中序和后序遍历结果。