已知一棵二叉树的便利序列如下画出据此构造的二叉树 中根次序便利序列CDBEGFHANMOLKPQSRJIT 后根次序便利序列 DCGHFEBNOMLSRQPKJTIA
时间: 2023-11-23 21:11:58 浏览: 133
根据中根次序便利序列,我们可以确定二叉树的结构,再根据后根次序便利序列,我们可以确定每个节点的位置。具体步骤如下:
1. 中根次序便利序列为 CDBEGFHANMOLKPQSRJIT。根据中根次序便利序列,我们可以确定根节点为I。将中根次序便利序列分为左子树和右子树两部分:
左子树:CDBEGFHANMOLKPQSR
右子树:JT
2. 后根次序便利序列为DCGHFEBNOMLSRQPKJTIA。根据后根次序便利序列,最后一个节点为根节点I,倒数第二个节点为右子树的节点T。将后根次序便利序列分为左子树和右子树两部分:
左子树:DCGHFEBNOMLSRQPK
右子树:TIA
3. 对于左子树,它的后根次序便利序列为DCGHFEBNOMLSRQPK,最后一个节点为K,倒数第二个节点为Q,因此K为左子树的根节点。将左子树的中根次序便利序列和后根次序便利序列分为左子树和右子树两部分:
左子树:DCGHFEBNOMLSR
右子树:QPK
4. 对于左子树的左子树,它的后根次序便利序列为DCGHFEBNOMLSR,最后一个节点为R,倒数第二个节点为S,因此R为左子树的左子树的根节点。将左子树的左子树的中根次序便利序列和后根次序便利序列分为左子树和右子树两部分:
左子树:DCGHFEBNO
右子树:LSR
5. 对于左子树的左子树的右子树,它的后根次序便利序列为LSR,最后一个节点为R,倒数第二个节点为S,因此R为左子树的左子树的右子树的根节点。将左子树的左子树的右子树的中根次序便利序列和后根次序便利序列分为左子树和右子树两部分:
左子树:L
右子树:SR
6. 对于左子树的左子树的右子树的右子树,它的后根次序便利序列为SR,最后一个节点为R,倒数第二个节点为S,因此R为左子树的左子树的右子树的右子树的根节点。
7. 对于左子树的右子树,它的后根次序便利序列为QPK,最后一个节点为K,倒数第二个节点为P,因此K为左子树的右子树的根节点。将左子树的右子树的中根次序便利序列和后根次序便利序列分为左子树和右子树两部分:
左子树:Q
右子树:PK
8. 对于左子树的右子树的右子树,它的后根次序便利序列为PK,最后一个节点为K,倒数第二个节点为P,因此K为左子树的右子树的右子树的根节点。
9. 对于右子树,它的后根次序便利序列为TIA,最后一个节点为A,倒数第二个节点为I,因此A为右子树的根节点。将右子树的中根次序便利序列和后根次序便利序列分为左子树和右子树两部分:
左子树:T
右子树:I
因此,据此构造的二叉树如下图所示:
```
I
/ \
/ \
K A
/ \ \
C Q T
\ /
E J
/ \ / \
D G M S
/ \
B R
\
P
```
阅读全文