已知二叉树中序遍历序列为CBDFEGAMLNKJOPRQIHS, 后序遍历序列为CFGEDBMNLKRQPOJISHA,试画出此二叉树
时间: 2023-11-23 20:13:06 浏览: 184
数据结构C++二叉树的先序遍历、中序遍历和后序遍历实现
5星 · 资源好评率100%
根据二叉树遍历的特点,可以确定该二叉树的根节点为序列中的最后一个节点 "A"。然后在中序遍历中找到根节点的位置,根节点左边的序列为左子树的中序遍历序列,右边的序列为右子树的中序遍历序列。同样,在后序遍历中,根节点左边的序列为左子树的后序遍历序列,右边的序列为右子树的后序遍历序列。然后递归构造左右子树即可。
构造过程如下:
1. 根据中序遍历序列,确定根节点为 "A",并找到 "A" 在中序遍历序列中的位置。
2. 根据后序遍历序列,确定根节点为 "A",并找到 "A" 在后序遍历序列中的位置。
3. 根据中序遍历序列和后序遍历序列,确定左子树的中序遍历序列为 "CBDFEGM",左子树的后序遍历序列为 "CFGEDBM"。
4. 根据中序遍历序列和后序遍历序列,确定右子树的中序遍历序列为 "LNKJOPRQIHS",右子树的后序遍历序列为 "NLKRQPOJISH".
5. 递归构造左右子树,得到完整的二叉树。
最终的二叉树如下图所示:
```
A
/ \
/ \
/ \
/ \
C L
/ \ / \
/ \ / \
B D K N
/ \ / \
/ \ / \
F E J O
/ \ \
/ \ \
G M I
\
\
S
```
其中,节点的左子树在上方,右子树在下方。
阅读全文