利用先序遍历创建二叉树,并给出相应二叉树的中序遍历结果
时间: 2024-01-23 22:04:48 浏览: 56
假设先序遍历的结果为: A B D # # E # # C # #
其中 # 表示空节点。
根据先序遍历的规律,我们先创建根节点 A,然后按照先序遍历的顺序依次创建左子树和右子树。
A 的左子树是 B,B 的左子树是 D,而 D 没有子节点,于是我们在 B 的右子树上创建空节点,即 #。B 的右子树是 E,E 没有子节点,于是我们也在 E 的右子树上创建空节点,即 #。此时 B 的子树创建完成。
回到 A,A 的右子树是 C,C 没有子节点,于是我们在 C 的左右子树上分别创建空节点,即 #。此时整棵树创建完成。
根据中序遍历的规律,对于任意一棵二叉树,其中序遍历的结果都是将左子树、根节点和右子树依次遍历。因此,该二叉树的中序遍历结果为: D B E A C。
相关问题
利用先序遍历创建二叉树,并给出相应二叉树的中序遍历结果。
假设先序遍历结果为:A B D G E C F H
根据先序遍历的规则,我们可以知道根节点是A,因此我们可以创建一个以A为根节点的二叉树。
接下来我们需要确定A的左右子树。我们可以通过查看中序遍历结果来确定。中序遍历结果为:G D B E A F H C
我们可以发现,A的左子树中的所有节点在中序遍历结果中都在A的左边,而A的右子树中的所有节点在中序遍历结果中都在A的右边。
因此,我们可以将中序遍历结果拆分为左右子树的部分:G D B E为左子树,F H C为右子树。
接下来,我们可以利用同样的方法递归的创建左右子树。左子树的先序遍历结果为:B D G E,中序遍历结果为:G D B E。右子树的先序遍历结果为:C F H,中序遍历结果为:F H C。
最终得到的二叉树如下所示:
```
A
/ \
B C
/ \ \
D E F
\ \
G H
```
中序遍历结果为:G D B E A F H C。
c++利用先序遍历创建二叉树,并给出相应二叉树的中序遍历结果。
下面是利用先序遍历创建二叉树的 C++ 代码:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(NULL), right(NULL) {}
};
TreeNode* createTree() {
int val;
cin >> val;
if (val == -1) {
return NULL;
}
TreeNode* root = new TreeNode(val);
root->left = createTree();
root->right = createTree();
return root;
}
void inorderTraversal(TreeNode* root) {
if (!root) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
cout << "Input the preorder of binary tree (-1 means NULL):" << endl;
TreeNode* root = createTree();
cout << "The inorder of binary tree is:" << endl;
inorderTraversal(root);
cout << endl;
return 0;
}
```
输入先序遍历序列,其中 -1 表示空节点,程序会自动构建对应的二叉树,并输出中序遍历结果。
例如输入序列:1 2 -1 -1 3 4 -1 -1 5 -1 -1,则输出中序遍历结果为 2 1 4 3 5。
阅读全文