设某树的先序遍历序列为sacefbdghijk,后序遍历序列为cfeabhgikjds,画出这棵树。
时间: 2023-03-25 17:05:05 浏览: 215
把先序遍历序列和后序遍历序列分别写成根节点、左子树和右子树的形式:
先序遍历序列:s a c e f b d g h i j k
后序遍历序列:c f e a b h g i k j d s
根据先序遍历序列,我们可以知道根节点是s,然后在后序遍历序列中找到s,可以把后序遍历序列分成两部分:
左子树的后序遍历序列:c f e a b h g i k j
右子树的后序遍历序列:d
接下来,我们可以根据左子树的后序遍历序列和先序遍历序列,递归地构建左子树。左子树的先序遍历序列是:
a c e f b
左子树的后序遍历序列是:
c f e a b h g i k j
根据左子树的先序遍历序列,我们可以知道左子树的根节点是a。在左子树的后序遍历序列中找到a,可以把左子树的后序遍历序列分成两部分:
左子树的左子树的后序遍历序列:c f e
左子树的右子树的后序遍历序列:b h g i k j
接下来,我们可以根据左子树的左子树的后序遍历序列和先序遍历序列,递归地构建左子树的左子树。左子树的左子树的先序遍历序列是:
c e f
左子树的左子树的后序遍历序列是:
c f e
根据左子树的左子树的先序遍历序列,我们可以知道左子树的左子树的根节点是c。在左子树的左子树的后序遍历序列中找到c,可以把左子树的左子树的后序遍历序列分成两部分:
左子树的左子树的左子树的后序遍历序列:无
左子树的左子树的右子树的后序遍历序列:f e
左子树的左子树已经构建完成,接下来我们可以根据左子树的右子树的后序遍历序列和先序遍历序列,递归地构建左子树的右子树。左子树的右子树的先序遍历序列是:
b h g i k j
左子树的右子树的后序遍历序列是:
b h g i k j
根据左子树的右子树的先序遍历序列,我们可以知道左子树的右子树的根节点是b。在左子树的右子树的后序遍历序列中找到b,可以把左子树的右子树的后序遍历序列分成两部分:
左子树的右子树的左子树的后序遍历序列:h g i k j
左子树的右子树的右子树的后序遍历序列:无
左子树的右子树已经构建完成,接下来我们可以根据右子树的后序遍历序列和先序遍历序列,递归地构建右子树。右子树的先序遍历序列是:
d
右子树的后序遍历序列是:
d
根据右子树的先序遍历序列,我们可以知道右子树的根节点是d。因为右子树只有一个节点,所以右子树已经构建完成。
最终,我们得到了如下的树:
```
s
/ \
a d
/ \
c b
/ \
f h
/ \
g i
\
j
```