以前参加NOI时自己摸索出来的方法。
已知序列画树:
已知后序与中序排前序:
由后序最后一位得知根节点,然后以此元素为基准将序列分为左、右子树,其中左子树的中序为上一层中序的左半部分,其后序为中序中的元素以上一层后序的顺序排列;右子树的中序为上一层中序的右半部分,其后序为中序中的元素以上一层后序的顺序排列。接着再根据此方法分别对每个子树中的中、后序继续分解,最后即可依次写出整棵二叉树的图,再通过描点法写出前序。
已知中序与前序排后序:
由前序第一位得知根节点,然后以此元素为基准将序列分为左、右子树,其中左子树的中序为上一层中序的左半部分,其前序为中序中的元素以上一层前序的顺序排列;右子树的中序为上一层中序的右半部分,其前序为中序中的元素以上一层前序的顺序排列。接着再根据此方法分别对每个子树中的中、前序继续分解,最后即可依次写出整棵二叉树的图,再通过描点法写出后序。
已知序列画树:
Quotation
已知后序与中序排前序:
由后序最后一位得知根节点,然后以此元素为基准将序列分为左、右子树,其中左子树的中序为上一层中序的左半部分,其后序为中序中的元素以上一层后序的顺序排列;右子树的中序为上一层中序的右半部分,其后序为中序中的元素以上一层后序的顺序排列。接着再根据此方法分别对每个子树中的中、后序继续分解,最后即可依次写出整棵二叉树的图,再通过描点法写出前序。
已知中序与前序排后序:
由前序第一位得知根节点,然后以此元素为基准将序列分为左、右子树,其中左子树的中序为上一层中序的左半部分,其前序为中序中的元素以上一层前序的顺序排列;右子树的中序为上一层中序的右半部分,其前序为中序中的元素以上一层前序的顺序排列。接着再根据此方法分别对每个子树中的中、前序继续分解,最后即可依次写出整棵二叉树的图,再通过描点法写出后序。











